| 授業科目名 | グラフ・ネットワーク理論 |
|---|---|
| 履修期 秋 2単位 履修基準年度 2年 | |
| 担当者 | 西関 隆夫（NISHIZEKI TAKAO） |
| 授業目的 / Course Objectives |
|---|
| グラフ理論とネットワーク理論から、基礎的かつ重要な話題を選んで、数学的理解を図ると共に、代表的なアルゴリズムを紹介する。これらは情報科学のあらゆる分野で必要とされる基礎知識であるので、本講義を通じて理解を深めておくことが求められる。 |
| 到達目標 / Attainment Objectives |
| - |
| 授業時間外の学習 (準備学習等について) / Study Required Outside of Class (Preparation etc.) |
| 離散数理を履修しておくことが望ましい。 |
| 授業計画 / Class Overall Plan |
|
１．序論：グラフとネットワークの理論 ２．グラフの用語と基礎的事項 ３．ダイキストラアルゴリズム ４．最小木アルゴリズム ５．オイラー閉路の郵便配達順路への応用 ６．平面グラフのＶＬＳＩ一層配線への応用 ７．グラフの彩色とスケジュリング ８．グラフの辺彩色 ９．包含と排除の理の通信ネットワーク信頼性計算への応用 １０．ネットワークフロー １１．最大フロー問題 １２．最大フローと最小カット １３．マッチング問題 １４－１５．演習 |
| 教科書 / Textbook(s) |
| 斎藤・西関・千葉「離散数学」（朝倉書店 １９８９） |
| 参考文献 References Books |
| 茨木俊秀「Ｃによるアルゴリズムとデータ構造」(昭晃堂、１９９４年) |
| 授業方法 / Method of Instruction |
| 講義形式で行う |
| 学生による授業評価の方法 / Course Evaluation by Students |
| ネット利用(所定のフォーマット) |
| 成績評価 / Evaluation Criteria/Method |
| 定期試験(Final examination)/平常リポート(Ordinary paper) |
| 備考 / Note |
| - |
| 検索キーワード / Keywords |
| グラフ/ネットワーク/アルゴリズム/平面グラフ/最小木/最短路/彩色/ネットワークフロー/マッチング |