グラフ・ネットワーク理論
| 授業目的 |
|---|
| グラフ理論とネットワーク理論から，基礎的かつ重要な話題を選んで，数学的な基本事項を理解し，代表的なアルゴリズムを学ぶ．これらは情報科学のあらゆる分野で必要とされる基礎知識であるので，本講義を通じて理解を深めておくことが求められる． |
| 到達目標 |
| グラフやネットワークを用いた問題の定式化ができるようになる．基本的なグラフやネットワークの用語を理解する．グラフに関する基本的な最適化問題とその解法を理解する． |
| 授業計画 | |
|---|---|
| 第1回 | グラフと関連する概念 |
| 第2回 | グラフを歩く 【授業外学修】以降，資料をLUNAにあげるので，復習すること |
| 第3回 | 木とグラフの探索 【授業外学修】復習問題 |
| 第4回 | 迷路を解こう 【授業外学修】復習問題 |
| 第5回 | グラフ上の最適化問題 【授業外学修】疑似コード作成 |
| 第6回 | グラフ彩色と4色問題 【授業外学修】復習問題 |
| 第7回 | 平面グラフと幾何学 【授業外学修】復習問題 |
| 第8回 | 中間試験もしくは中間レポートの作成 【授業外学修】復習問題 |
| 第9回 | 最小全域木とそのアルゴリズム 【授業外学修】復習問題 |
| 第10回 | 動的計画法と最短路 【授業外学修】復習問題 |
| 第11回 | ダイクストラアルゴリズムとデータ構造 【授業外学修】復習問題 |
| 第12回 | グラフのカットとフロー 【授業外学修】復習問題 |
| 第13回 | フローとマッチング 【授業外学修】復習問題 |
| 第14回 | グラフ問題と線形代数・線形計画法 【授業外学修】復習問題 |
| 第15回 | 定期試験もしくは期末レポート 【授業外学修】なし |