オペレーションズ・リサーチ第二

Google Classroomを使用

主な講義内容は以下のとおりである. オペレーションズ・リサーチの基盤技術である「離散最適化」について, 板書を用いる講義形式の授業を行う. トピックとして
・最小全域木問題
・最短路問題
・ネットワークフロー問題
・集合被覆問題
・ナップサック問題
などの基礎的な問題を題材に, 理論解析およびアルゴリズム設計の手法を扱う. 教科書は指定しない. 板書を配布する.

とくになし.

とくになし.

とくになし.

英語タイプII(Cc)により講義を実施
Type II:Japanese-based course with Japanese materials

以下のトピック含む内容について15回に分けて講義する.

1. ガイダンスと双対問題の導出
2. 混合整数計画問題
3. キャリア懇談会(土曜補講)
4. 最短路問題
5. マッチング問題:整数計画法
6. マッチング問題:頂点カバー問題
7. 研究紹介(土曜補講)
8. マッチング問題:Hallの結婚定理
9. ネットワークフロー問題:最大フロー問題
10. ネットワークフロー問題:最小カット問題
11. ネットワークフロー問題:フォード・ファルカーソンのアルゴリズム
12. 最小全域木問題:整数計画法
13. 最小全域木問題:クラスカルのアルゴリズム
14. 近似アルゴリズム:頂点被覆問題
15. 期末レポート出題

進め方:a)曜日時限指定なしオンデマンドですが、原則木曜3限に対面講義(一部遠隔を含む)を実施します。
Instruction: The course will be conducted on-demand. However, face-to-face lectures (including some remote lectures) will be provided. Details will be explained during the lecture.

特になし.

レポートにより評価します.

オンラインで対応しますので, アポを取るようにお願いします.
As we will be handling it online, please make an appointment in advance.

オペレーションズ・リサーチにおける離散最適化の重要性はよく知られていますが, Googleのキーワード広告オークションの成功などにより, ゲーム理論への応用が大変注目されています. 実際, GoogleやMicrosoftなどのテックカンパニーでは, ゲーム理論ができる計算機科学者, そして経済学者が多数雇用されています. 本講義では, 離散最適化の基礎を中心に学んで頂くとともに, その応用の最先端をご紹介します.

特になし