情報科学講究２

授業テーマ	組合せ最適化問題とネットワーク最適化問題
授業のねらい・到達目標	組合せ最適化問題とネットワーク最適化を学習する。
授業の方法	教科書から各自の分担部分を決め，授業内に発表する。適宜レポートを課す。
事前学修・事後学修，授業計画コメント	前回授業の復習および予習

授業計画
1	ガイダンス（授業のテーマや到達目標及び授業の方法について説明する）（準備：特に必要なし）
2	分枝限定法：ナップサック問題（準備：前回の授業内容の復習）
3	動的計画法（１）ナップサック問題（準備：前回の授業内容の復習）
4	動的計画法（２）ビンパッキング問題（準備：前回の授業内容の復習）
5	近似解法（準備：前回の授業内容の復習）
6	まとめと総合演習：組合せ最適化問題（準備：前回までの授業内容の復習）
7	最短路問題（１）準備（準備：前回の授業内容の復習）
8	最短路問題（２）ラベル確定法とラベル修正法（準備：前回の授業内容の復習）
9	最小費用流問題（１）準備（準備：前回の授業内容の復習）
10	最小費用流問題（２）閉路消去法（準備：前回の授業内容の復習）
11	最小費用流問題（３）最短路繰り返し法（準備：前回の授業内容の復習）
12	最大流問題（１）準備（準備：前回の授業内容の復習）
13	最大流問題（２）増加道法（準備：前回の授業内容の復習）
14	最大流問題（３）2部グラフの最大マッチング問題（準備：前回の授業内容の復習）
15	まとめと総合演習：ネットワーク最適化問題（準備：前回までの授業内容の復習）

その他
参考書	久野誉人，繁野麻衣子，後藤順哉『数理最適化』オーム社 2012年第1版 G.M. ツィーグラー；八森正泰，岡本吉央（翻訳）『凸多面体の数学』シュプリンガー・フェアラーク東京 2003年第1版
成績評価の方法及び基準	発表，レポート，授業参画度をもとに総合的に判定します。(100%)
オフィスアワー	授業終了時

授業計画
1	ガイダンス（授業のテーマや到達目標及び授業の方法について説明する）（準備：特に必要なし）
2	分枝限定法：ナップサック問題（準備：前回の授業内容の復習）
3	動的計画法（１）ナップサック問題（準備：前回の授業内容の復習）
4	動的計画法（２）ビンパッキング問題（準備：前回の授業内容の復習）
5	近似解法（準備：前回の授業内容の復習）
6	まとめと総合演習：組合せ最適化問題（準備：前回までの授業内容の復習）
7	最短路問題（１）準備（準備：前回の授業内容の復習）
8	最短路問題（２）ラベル確定法とラベル修正法（準備：前回の授業内容の復習）
9	最小費用流問題（１）準備（準備：前回の授業内容の復習）
10	最小費用流問題（２）閉路消去法（準備：前回の授業内容の復習）
11	最小費用流問題（３）最短路繰り返し法（準備：前回の授業内容の復習）
12	最大流問題（１）準備（準備：前回の授業内容の復習）
13	最大流問題（２）増加道法（準備：前回の授業内容の復習）
14	最大流問題（３）2部グラフの最大マッチング問題（準備：前回の授業内容の復習）
15	まとめと総合演習：ネットワーク最適化問題（準備：前回までの授業内容の復習）