理工学部Faculty of Science and Engineering
PRI200XF（情報学基礎 / Principles of informatics 200）ネットワーク論Network programming
千葉 英史Eishi CHIBA
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学部Faculty of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2024 |
| 授業コードClass code | H6859 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 秋学期授業/Fall |
| 曜日・時限Day/Period | 月4/Mon.4 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 |
| 教室名称Classroom name | 小西館‐W203 |
| 配当年次Grade | 2年 |
| 単位数Credit(s) | |
| 備考（履修条件等）Notes | |
| 他学部公開科目Open Program | |
| 他学部公開（履修条件等）Open Program (Notes) | |
| グローバル・オープン科目Global Open Program | |
| 成績優秀者の他学部科目履修制度対象Interdepartmental class taking system for Academic Achievers | |
| 成績優秀者の他学部科目履修（履修条件等）Interdepartmental class taking system for Academic Achievers (Notes) | |
| 実務経験のある教員による授業科目Class taught by instructors with practical experience | |
| SDGsCPSDGs CP | |
| アーバンデザインCPUrban Design CP | |
| ダイバーシティCPDiversity CP | |
| 未来教室CPLearning for the Future CP | |
| カーボンニュートラルCPCarbon Neutral CP | |
| 千代田コンソ単位互換提供（他大学向け）Chiyoda Campus Consortium | |
| カテゴリー＜理工学部＞Category |
経営システム工学科 学科専門科目 |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
In this course, we will delve into typical graph/network algorithms and the theory underlying these algorithms, all grounded in efficient data structures and fundamental algorithmic concepts.
The objectives of this course are to:
1. Explore typical problems encountered within networks.
2. Gain a comprehensive understanding of the algorithms designed to address these problems.
Students are expected to dedicate four hours after each class to fully comprehend the course material.
The overall grade for this course will be determined solely by the term-end examination, which accounts for 100% of the final grade.
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
インターネット、電子回路網、通信網、輸送網など、グラフ構造を有する情報システムの効率的な設計、運用、解析には、ネットワーク理論、アルゴリズムの基礎、そして効率的なデータ構造に基づくグラフ・ネットワークアルゴリズムが非常に有用である。この講義では、アルゴリズムの基礎と効率的なデータ構造を基盤として、代表的なグラフ・ネットワークアルゴリズム及びその基礎となる理論について学ぶ。
到達目標Goal
到達目標は、ネットワーク上で遭遇する様々な問題を定式化し、その定式化した問題に対する解法と、それらの解法を効率的に実行するためのアルゴリズム、さらにはそれらのアルゴリズムを効率的に実現するためのデータ構造を理解することです。
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち、「DP1」と「DP2」と「DP4」に関連
授業で使用する言語Default language used in class
日本語 / Japanese
授業の進め方と方法Method(s)（学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. ）
講義形式で授業は進行するが、必要に応じて演習も行う。これらの演習は学期末の試験対策に役立つ。
アクティブラーニング（グループディスカッション、ディベート等）の実施Active learning in class (Group discussion, Debate.etc.)
なし / No
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
第1回[対面/face to face]：グラフの基礎概念
グラフに関する基本的な用語と概念を解説する。
第2回[対面/face to face]：グラフ・ネットワーク表現のデータ構造
ネットワークの基礎構造であるグラフをコンピューター内で効率的に処理するためのデータ構造を、そのために必要とする記憶領域を含めて解説する。
第3回[対面/face to face]：グラフとネットワークの探索アルゴリズム（１）
グラフとネットワークの様々な問題を効率的に処理するための下準備となる、探索アルゴリズムについて解説する。具体的には、第2回の講義で用いたデータ構造を用いて、有向グラフに対する深さ優先探索と幅優先探索を解説する。
第4回[対面/face to face]：グラフとネットワークの探索アルゴリズム（２）
無向グラフに対する深さ優先探索と幅優先探索を解説する。さらに、グラフの様々な性質を調べるための、深さ優先探索と幅優先探索の応用例を解説する。
第5回[対面/face to face]：トポロジカルソートと最短パスと最長パス
グラフやネットワーク問題の代表的な問題である最短パス問題と最長パス問題を取り上げる。そこで、有向閉路のないグラフに対して、ネットワークの頂点に、どの辺においても、始点のラベルが終点のラベルより小さくなるように頂点にラベルをつける（トポロジカルソートと呼ばれる）。このトポロジカルソートは、ネットワーク探索アルゴリズムで効率的にできる。そしてそのラベルの小さい順に計算して、ネットワークの最短パスと最長パスを効率的に求めるアルゴリズムを解説する。
第6回[対面/face to face]：オイラーグラフと一筆書き
グラフやネットワーク問題の代表的な問題であるオイラーグラフ（一筆書き可能グラフ）の特徴付けを与え、その特徴付けと第2-4回の講義で説明したデータ構造と探索アルゴリズムを用いて、効率的な一筆書きアルゴリズムを解説する。
第7回[対面/face to face]：最短パスとダイクストラ法
カーナビや乗り換え経路案内等のシステムで用いられているネットワークの最短パス問題を取り上げる。第5回の講義では、有向閉路のないグラフに対しての最短パスを取り上げたが、ここで取り上げている最短パス問題では、より一般的な有向閉路が存在することもあるネットワークを対象としている。そして、負の長さの辺のないネットワークに対する代表的な最短パスアルゴリズムのダイクストラ法を解説する。さらに、そのアルゴリズムを高速化するデータ構造についても解説する。
第8回[対面/face to face]：全点間の最短パスと動的計画法
ネットワークのすべての２点間の最短パスを効率的に求める全点間の最短パス問題を取り上げる。そして、効率的なアルゴリズムの代表的な設計手法である動的計画法に基づいて、全点間の最短パス問題を効率的に求めるアルゴリズムを解説する。
第9回[対面/face to face]：最小全点木とグリーディ法
通信ネットワークや送電線ネットワークでの代表的な問題である最小全点木問題に対して、その特徴付けを与え、それと効率的アルゴリズムの代表的設計手法のグリーディ法に基づいて、ネットワークの最小全点木を効率的に求めるアルゴリズムを解説する。さらに、そのアルゴリズムを高速化するデータ構造についても解説する。
第10回[対面/face to face]：最大フローと最小カットとフォード-ファルカーソンのアルゴリズム
道路交通網やインターネットや水道網で問題になる流れ（フロー）の問題を取り上げる。ネットワークの回線（辺、パイプ）に容量（単位時間当たりに流せる最大流量）が付随するとき、ネットワーク内で要求されるフローをできるだけ多くする問題（最大フロー問題）とその限界（最小カット問題）を解説する。そして、それらを効率的に解決するフォード-ファルカーソンのアルゴリズムを解説する。
第11回[対面/face to face]：ディニッツの最大フローアルゴリズム
第10回の講義で取り上げた最大フローと最小カットに対するフォード-ファルカーソンのアルゴリズムをより高速化する、ディニッツの最大フローアルゴリズムを解説する。これは、第3回の講義で与えた深さ優先探索と幅優先探索を用いて実装できることも解説する。
第12回[対面/face to face]：最大フローアルゴリズムの応用
ネットワークの様々な問題が最大フローと最小カットを用いて定式化できることを解説する。これに基づいて、最大フローと最小カットを求めるアルゴリズムは、ネットワークで起こる多くの問題に広く応用できることを、具体的な例を取り上げて解説する。
第13回[対面/face to face]：最小費用フローアルゴリズムとダイクストラ法の適用
ネットワークの各回線に容量のみならず、使用コストが付随するときのフローの問題である、最小費用フロー問題を取り上げる。これは、最短パス問題や最大フロー問題を一般化した問題で、その意味では、多岐にわたる応用を有するものである。ここでは、最短パスを求めるダイクストラ法に基づいて、最小費用フロー問題を解くアルゴリズムを解説する。
第14回[対面/face to face]：試験・まとめと解説
理解度の確認をする。
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
【本授業の準備・復習等の授業時間外学習は、4時間を標準とする】アルゴリズムに関する基本的な知識を前提として、授業が進められる。そのため、必要に応じて自ら学習することが求められる。
テキスト（教科書）Textbooks
浅野孝夫：「グラフ・ネットワークアルゴリズムの基礎：数理とCプログラム」（近代科学社）、2017。
参考書References
特になし。
成績評価の方法と基準Grading criteria
学期末試験の成績(100%)によって評価する。
学生の意見等からの気づきChanges following student comments
演習を通じて、理解度を向上させることを目指す。