ネットワーク理論 |
Network thory |
開講部 | 工学部 |
開講学科 | 通信工学科 |
開講学年 | 3年次 |
開講時期 | 前期 |
単位数 | 2 |
単位区分 | 選択必修 |
系列区分 | 専門 |
講義区分 | 講義 |
教育目標 | D1 |
| 准教授 | 森野博章 |
| 1. | 解析対象をグラフで表現し，リンクへのコスト付与，容量付与等の問題設定ができるようになる． |
| 2. | 最短経路探索，信頼性評価，最大フロー探索の概念を理解し，その解法に習熟する． |
| 3. | 線形計画問題とその代表的な解法であるシンプレクス法の概念を理解し，問題の定式化と求解に習熟する． |
| 【授業計画】 | 【授業時間外課題（予習および復習を含む）】 | |
| 1. | グラフ理論の基礎（１） ・イントロダクション - グラフ理論とは，ケーニヒスベルグの橋問題，集合によるグラフの表記 ・リンクに対するコスト設定 - 通信ネットワークにおけるリンクコストの設定法 | 情報通信ネットワーク1の全配付資料を復習する． |
| 2. | グラフ理論の基礎（２） ・最短経路探索問題の求解 ダイクストラ法 ・最小全域木の構築 プリム法 ・グラフの連結性からみたネットワークの信頼性評価 - 点連結度，枝連結度 | 事前配付資料を予習する． |
| 3. | グラフ理論の基礎（３） ・ネットワークの経路信頼性評価 ・リンク独立経路とノード独立経路 ・メンガーの定理 | 事前配付資料を予習する． |
| 4. | グラフ理論の基礎（４） ・ネットワークフローとは ・リンクが容量をもつグラフにより解かれる問題の例 − 回路網，道路網，，， ・フローの定義 ・最大フロー問題とその解法 | 事前配付資料を予習する． |
| 5. | グラフ理論の基礎（５） ・有向グラフのカットと最小カット ・最大フロー・最小カット定理 | 事前配付資料を予習する． |
| 6. | ネットワーク理論 応用 複雑ネットワーク | 事前配付資料を予習する． |
| 7. | 中間試験および解説 | 第一回〜第六回の配付資料を復習する． |
| 8. | 線形計画問題とその解法(1) ・線形計画問題とは ・ネットワークフロー問題を線形計画問題として定式化する． ・図式解法 | 事前配付資料を予習する． |
| 9. | 線形問題とその解法(2) シンプレックス法 | 事前配付資料を予習する． |
| 10. | 問題演習 | 事前配付資料を予習する． |
| 11. | 線形計画法(3) 双対問題，感度分析 | 事前配付資料を予習する． |
| 12. | 線形計画法応用 〜ゲーム理論〜 | 事前配付資料を予習する． |
| 13. | 線形計画法応用 〜整数線形計画法〜 | 事前配付資料を予習する． |
| 14. | 総合問題演習 | 第八回〜第十三回の配付資料を復習する． |
| 15. | 期末試験および解説 | 第八回〜第十四回の配付資料を復習する． |
| ・ | 毎回の授業終了後 |
| ・ | 対課題基礎力を育成する科目 |