理工学部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 | 2022 |
| 授業コードClass code | H6531 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 秋学期授業/Fall |
| 曜日・時限Day/Period | 月4/Mon.4 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 |
| 教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
| 配当年次Grade | |
| 単位数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, based on efficient data structures and foundation for algorithms, we learn typical graph/network algorithms and the theory underlying those algorithms.
The goals of this course are to (1) learn typical problems on networks; (2) understand algorithms to solve them; and (3) learn how to implement such algorithms using C language.
After each class, students will be expected to spend four hours to understand the course content.
Your overall grade in the class will be decided based on term-end examination: 100%.
授業で使用する言語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. ）
講義形式で授業は進行するが、必要に応じて演習・課題を行う。課題に対しては、適宜講評する。演習・課題は学期末試験の対策になる。さらに、講義で説明したアルゴリズムのコードをPC上で実行することを通して、アルゴリズムの理解を深める。
アクティブラーニング（グループディスカッション、ディベート等）の実施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
浅野孝夫：「アルゴリズムの基礎とデータ構造：数理とCプログラム」（近代科学社）。
J.Kleinberg and E. Tardos 著（浅野孝夫、浅野泰仁、他、訳）：「アルゴリズムデザイン」（共立出版）。
浅野孝夫、今井浩:「計算とアルゴリズム」（オーム社）。
浅野孝夫：「情報の構造（上）データ構造とグラフアルゴリズム (情報数学セミナー) 」（日本評論社）。
浅野孝夫：「情報の構造（下）ネットワークアルゴリズムとデータ構造 (情報数学セミナー) 」（日本評論社）。
浅野孝夫：「離散数学：グラフ・束・デザイン・離散確率」（サイエンス社）。
成績評価の方法と基準Grading criteria
学期末試験の成績(100%)によって評価する。
学生の意見等からの気づきChanges following student comments
ソースコードの説明を増やす。
学生が準備すべき機器他Equipment student needs to prepare
必要に応じて、貸与ノートパソコンを利用する。