検索したい科目／教員名／キーワードを入力し「検索開始｣ボタンをクリックしてください。
※教員名では姓と名の間に１文字スペースを入れずに、検索してください。
情報科学講究２
| 科目名 | 情報科学講究２ | ||||
|---|---|---|---|---|---|
| 教員名 | 森山園子 | ||||
| 単位数 | 2 | 学年 | 3 | 開講区分 | 文理学部 |
| 科目群 | 情報科学科 | ||||
| 学期 | 後期 | 履修区分 | 必修 | ||
| 授業概要 | 組合せ最適化問題の解法とネットワーク最適化問題とその解法を学ぶ。 |
|---|---|
| 授業のねらい・到達目標 | 教科書「数理最適化」の輪読を通じて，組合せ最適化問題の解法とネットワーク最適化問題とその解法を学び，数理計画の発展的な能力を身に付ける。 この科目は文理学部（学士（理学））のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応しています。 |
| 授業の方法 | 教科書から各自の分担部分を決め，授業内に発表する。適宜レポートを課す。 本授業の事前・事後学習は，各２時間の学習を目安とする。 |
| 授業計画 | |
|---|---|
| 1 |
線形計画問題および単体法の復習 【事前学習】前期科目「数理計画」の復習 【事後学習】線形計画問題および単体法の習熟 |
| 2 |
分枝限定法 【事前学習】ナップサック問題の確認 【事後学習】分枝限定法の復習および演習問題 |
| 3 |
動的計画法（１）ナップサック問題 【事前学習】ナップサック問題の確認 【事後学習】動的計画法による２つの定式化の習熟 |
| 4 |
動的計画法（２）ビンパッキング問題 【事前学習】ビンパッキング問題の確認 【事後学習】動的計画法の復習および演習問題 |
| 5 |
近似解法 【事前学習】分枝限定法および動的計画法の習熟 【事後学習】近似解法の復習 |
| 6 |
まとめと総合演習：組合せ最適化問題 【事前学習】組合せ最適化問題の３つの解法の習熟 【事後学習】授業の復習および演習問題 |
| 7 |
最短路問題（１）準備 【事前学習】グラフに関する基礎知識の確認 【事後学習】数理計画問題への定式化の確認 |
| 8 |
最短路問題（２）ラベル確定法とラベル修正法 【事前学習】最短路問題の確認 【事後学習】最短路問題を解く２つの手法の習熟 |
| 9 |
最大流問題（１）準備 【事前学習】最大流問題の理解 【事後学習】数理計画問題への定式化の確認 |
| 10 |
最大流問題（２）増加道法 【事前学習】最大流問題の予習 【事後学習】増加道法の習熟および演習問題 |
| 11 |
最大流問題（３）2部グラフの最大マッチング問題 【事前学習】最大流問題の理解 【事後学習】数理計画問題への定式化の確認 |
| 12 |
最小費用流問題（１）準備 【事前学習】最小費用流問題の理解 【事後学習】数理計画問題への定式化の確認 |
| 13 |
最小費用流問題（２）閉路消去法 【事前学習】閉路消去法の予習 【事後学習】閉路消去法の習熟および演習問題 |
| 14 |
最小費用流問題（３）最短路繰り返し法 【事前学習】最短路繰り返し法の予習 【事後学習】最短路繰り返し法の習熟および演習問題 |
| 15 |
まとめと総合演習：ネットワーク最適化問題 【事前学習】３つのネットワーク最適化問題とその解法の習熟 【事後学習】授業の復習および演習問題 |
| その他 | |
|---|---|
| 教科書 | 久野誉人，繁野麻衣子，後藤順哉 『数理最適化』 オーム社 2012年 |
| 参考書 | 使用しない |
| 成績評価の方法及び基準 | 授業参画度(100%) 授業参画度は，発表および授業内の演習により評価する。 |
| オフィスアワー | 授業終了時 |