情報科学講究２

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

授業計画
1	ガイダンス（準備：特に必要なし）
2	組合せ最適化問題（１）組合せ最適化問題の定式化（準備：前回の授業内容の復習）
3	組合せ最適化問題（２）ナップサック問題（準備：前回の授業内容の復習）
4	分枝限定法（１）ナップサック問題（準備：前回の授業内容の復習）
5	分枝限定法（２）実行可能領域の分割（準備：前回の授業内容の復習）
6	分枝限定法（３）演習問題（準備：前回の授業内容の復習）
7	動的計画法（１）ナップサック問題　定式化１（準備：前回の授業内容の復習）
8	動的計画法（２）ナップサック問題　定式化２（準備：前回の授業内容の復習）
9	動的計画法（３）ビンパッキング問題（準備：前回の授業内容の復習）
10	動的計画法（４）演習問題（準備：前回の授業内容の復習）
11	解法の枠組みの適用（１）貪欲アルゴリズム（準備：前回の授業内容の復習）
12	解法の枠組みの適用（２）分岐限定法（準備：前回の授業内容の復習）
13	解法の枠組みの適用（３）動的計画法（準備：前回の授業内容の復習）
14	解法の枠組みの適用（４）演習問題（準備：前回の授業内容の復習）
15	まとめ（準備：前回の授業内容の復習）

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

授業計画
1	ガイダンス（準備：特に必要なし）
2	組合せ最適化問題（１）組合せ最適化問題の定式化（準備：前回の授業内容の復習）
3	組合せ最適化問題（２）ナップサック問題（準備：前回の授業内容の復習）
4	分枝限定法（１）ナップサック問題（準備：前回の授業内容の復習）
5	分枝限定法（２）実行可能領域の分割（準備：前回の授業内容の復習）
6	分枝限定法（３）演習問題（準備：前回の授業内容の復習）
7	動的計画法（１）ナップサック問題　定式化１（準備：前回の授業内容の復習）
8	動的計画法（２）ナップサック問題　定式化２（準備：前回の授業内容の復習）
9	動的計画法（３）ビンパッキング問題（準備：前回の授業内容の復習）
10	動的計画法（４）演習問題（準備：前回の授業内容の復習）
11	解法の枠組みの適用（１）貪欲アルゴリズム（準備：前回の授業内容の復習）
12	解法の枠組みの適用（２）分岐限定法（準備：前回の授業内容の復習）
13	解法の枠組みの適用（３）動的計画法（準備：前回の授業内容の復習）
14	解法の枠組みの適用（４）演習問題（準備：前回の授業内容の復習）
15	まとめ（準備：前回の授業内容の復習）