| 授業の目的 【日本語】 | | | 数理情報学4では，数理情報学3に続く科目として，グラフ理論に関連するテーマの中から，とくにネットワークに関する基本的な問題に対するアルゴリズムに関連する話題を取り上げる。グラフ・ネットワークは，道路ネットワーク，石油やガスのパイプライン，送電網など，さまざまな対象に応用を持つ。本科目では，ネットワーク最適化に関連する話題の中から，最短路，最小木，最大流，最小カットについて，それらの基本的な性質とアルゴリズムおよびその計算量と正当性について学ぶ。 |
|
|
| 授業の目的 【英語】 | | | Mathematical Informatics 4, is a subject following Mathematical Informatics 3, which will take up some topics related to graph theory, especially algorithm regarding basic problems. Graph networks have applications to various objects such as road networks, oil and gas pipelines, and power grids. In this lecture, students learn about the basic properties of shortest paths, minimum trees, maximum flows, and minimum cuts, as well as their computational complexity and correctness from topics related to network optimization and continue learning about algorithm. |
|
|
| 到達目標 【日本語】 | | | グラフ・ネットワークは情報学の諸分野に現れる基本構造であり，道路ネットワーク，石油やガスのパイプライン，送電網など，さまざまな対象に応用を持つ。本科目では，数理情報学3に続く科目として，グラフ理論に関連するテーマの中からとくにネットワークに関する基本的な問題に対するアルゴリズムに関連する話題を学び，グラフ・ネットワークにおける基礎的な問題を解決するアルゴリズムを修得することを目的とする。 |
|
|
| 到達目標 【英語】 | | |
|
| 授業の内容や構成 | | グラフ・ネットワークを理解するうえで必要となる基礎的な性質やネットワークの応用について紹介したのち，ネットワーク最適化に関連する話題の中から，最短路，最小木，最大流，最小カットについて，それらの基本的な性質とアルゴリズムおよびその計算量と正当性について学ぶ。
1. ガイダンス
2. グラフ・ネットワークの定義と基礎用語
3. 最短路問題の性質
4. 最短路問題を解くアルゴリズム
5. 最小木問題の性質
6. 最小木問題を解くアルゴリズム
7. 最大流と最小カットの関係
8. 最大流問題を解くアルゴリズム
9. 総括 | |
|
|
| 履修条件・関連する科目 | | |
|
| 成績評価の方法と基準 | | | 講義中に与える演習課題の評価40％，期末試験60％，合計100点満点で60点以上を合格とする。 | |
|
|
| 教科書・参考書 | | | 必ず数理情報学3も併せて履修すること。参考資料は必要に応じて配布する。 | |
|
|
| 課外学習等（授業時間外学習の指示） | | | 講義において説明した理論を理解するために課題を与える。 | |
|
|
| 授業開講形態等 | | |
|
| 遠隔授業（オンデマンド型）で行う場合の追加措置 | | |
|