情報通信ネットワーク，ソーシャルネットワークなど，「ネットワーク」で表される種々のシステムの基本的な性質を理解する上で重要かつ強力なツールの一つであるグラフ理論の基礎を学ぶ． また，ネットワークフロー問題を始めとする各種の最適化問題を解くツールとして線形計画法の基礎を学ぶ．後者は3年後期に開講される「パターン認識」を学ぶ上での基礎にもなる．
- Understanding the principle of modelling communication networks with graphs and being able to solve some optimization problems using graphs.
- Understanding problem formulation and solving of linear programming.
- Understanding overview of mathematical analysis using game theory for solving autonomous and decentralized network resource allocation problem.
| Class schedule | HW assignments (Including preparation and review of the class.) | Amount of Time Required | |
|---|---|---|---|
| 1. | Graph theory （Part I) - Introduction - Konigsberg bridge problem - Definitions of notations - Walk, path, loop，closed path, cycle - Eulerian path and semi-Eulerian graph - Eulerian cycle and Eulerian graph |
Reading the handout delivered in advance entitled "Graph theory (Part I)" | 190minutes |
| 2. | Graph theory （Part II) - Graphs where cost is given to each edge - Shortest path tree problem - Dijkstra algorithm - Minimum spanning tree problem - Prim algorithm |
Reading the handout delivered in advance entitled "Graph theory (Part II)" | 190minutes |
| 3. | Graph theory （Part III) - Connectivity for analyzing reliability - Metrics of connectivity - Vertex (Node) connectivity - Edge (Link) connectivity - Disjoint path - Menger's theorem |
事前配布資料の「グラフ理論の基礎（３）」を予習する | 270minutes |
| 4. | Graph theory （Part IV) - Flow network - Maximum flow problem |
Reading the handout delivered in advance entitled "Graph theory (Part IV)" | 270minutes |
| 5. | Graph theory （Part V) - Cut and minimum cut in directed graphs - Max-flow min-cut theorem |
Reading the handout delivered in advance entitled "Graph theory (Part V)" | 190minutes |
| 6. | Advanced graph theory - Complex networks - Analyzing social networks using complex networks |
Reading the handout delivered in advance entitled "Advanced graph theory" | 190minutes |
| 7. | Mid-term examination and a lecture on the answers | Reviewing handouts from the 1st to the 6th. | 270minutes |
| 8. | Linear Programming (Part I) - Overview - Model formulation example: for a maximum network flow problem - Graphical solution |
Reading the handout delivered in advance entitled "Linear Programming (Part I)" | 190minutes |
| 9. | Linear Programming (Part II) - Simplex method |
Reading the handout delivered in advance entitled "Linear Programming (Part III)" | 190minutes |
| 10. | Linear Programming (Part III) - Problem Practice |
Reviewing classes from the 8th to the 9th. | 190minutes |
| 11. | Linear Programming (Part IV) Dual Problem，Sensitivity analysis |
Reading the handout delivered in advance entitled "Linear Programming (Part IV)" | 190minutes |
| 12. | Advanced Linear Programming (Part IV) Game theory |
Reading the handout delivered in advance entitled "Advanced Linear Programming" | 270minutes |
| 13. | Problem practice | Reviewing classes from the 10th to the 12th. | 190minutes |
| 14. | End-term examination and a lecture on the answers | Reviewing classes from the 8th to the 13th. | 190minutes |
| Total. | - | - | 2980minutes |
| Mid-term examination | End-term examination | Total. | |
|---|---|---|---|
| 1. | 17% | 18% | 35% |
| 2. | 18% | 17% | 35% |
| 3. | 15% | 15% | 30% |
| Total. | 50% | 50% | - |
Mid-term examination(50%) and end-term examination(50%). You will take the credit when the total score is equal to or larger
than 60.out of 100. You will get the score of 60 when you will able to approximately 70% of problem practices delivered in
each class.
Recommended to take the course of "Information and Communication Networks I" in the 2nd grade.
- Course that cultivates a basic problem-solving skills
Last modified : Wed Oct 17 06:08:41 JST 2018