科目ナンバー

SG-EL5-5C34

履修条件・関連科目等

なし

授業で使用する言語

日本語

授業で使用する言語（その他の言語）

授業の概要

　回路の問題にグラフとネットワーク理論を用いたり、ネットワーク上の最短路や最小木をプログラミングにより求めることは、しばしば現われる。この授業では、基本的なグラフとネットワーク理論の結果と解を求める効率的なアルゴリズムを紹介し、その原理を講述する。また、ネットワーク上の諸問題は、距離に関するものの他、インターネットの発展に伴い流せるものの量（容量）に関するものが重要となっている．このような歴史的背景も含め、最近の話題を紹介する。

科目目的

グラフとネットワーク理論は、回路の解析や最短路問題等しばしば現われる。この授業では、グラフとネットワークに関する基本的な理論について歴史的背景も含めて学ぶ。さらに、近年の情報通信の発展に伴って、重要となるグラフとネットワークの理論について学ぶ。

到達目標

　グラフとネットワーク理論は、回路の解析や最短路問題等しばしば現われる。この授業では、グラフとネットワークに関する基本的な理論について歴史的背景も含めて学ぶ。さらに、近年の情報通信の発展に伴って、重要となるグラフとネットワークの理論について学ぶ。
(1)最短路や最小木を求める際の基本的なアルゴリズムへの理論的な理解
(2)ネットワークアルゴリズムの高速化の手法についての理解
(3)最近のインターネット等情報通信における課題と対応するネットワークにおける問題についての理解

授業計画と内容

第１回　グラフとネットワーク理論の必要性の概説
第２回　グラフに関する諸問題とその計算量
第３回　最小木を求めるアルゴリズムとその周辺の話題
第４回　最短路を求めるアルゴリズム とその周辺の話題
第５回　最大マッチングを求めるアルゴリズムとその周辺の話題
第６回　最大流の概念の一般化とその性質
第７回　最大流を求めるアルゴリズムとその周辺の話題
第８回　最大流を求めるアルゴリズムの高速化について
第９回　最小費用流についての考察
第10回　最小費用循環流と割当問題
第11回　ロケーション問題についての概説
第12回　ロケーション問題とその周辺の話題
第13回　被覆問題と辺連結度に関する問題
第14回　被覆問題とインターネット上の課題との関連

授業時間外の学修の内容

授業終了後の課題提出

授業時間外の学修の内容（その他の内容等）

前提となる知識を確実にしておく．授業での演習問題が確実に解けるようにしておくとともに関連研究について調べ、結果をまとめる。

授業時間外の学修に必要な時間数／週

・毎週１回の授業が半期（前期または後期）または通年で完結するもの。１週間あたり４時間の学修を基本とします。
・毎週２回の授業が半期（前期または後期）で完結するもの。１週間あたり８時間の学修を基本とします。

成績評価の方法・基準

成績評価の方法・基準（備考）

　到達目標の知識と能力を実際に身につけているかのレポート試験による評価（60％）、授業時の演習（４０％）と出席を加味して評価する．70％以上出席がなければ不合格。

課題や試験のフィードバック方法

授業時間内で講評・解説の時間を設ける

課題や試験のフィードバック方法（その他の内容等）

アクティブ・ラーニングの実施内容

実施しない

アクティブ・ラーニングの実施内容（その他の内容等）

授業におけるICTの活用方法

実施しない

授業におけるICTの活用方法（その他の内容等）

実務経験のある教員による授業

いいえ

【実務経験有の場合】実務経験の内容

【実務経験有の場合】実務経験に関連する授業内容

テキスト・参考文献等

テキスト：適宜資料を配布

その他特記事項

参考URL