離散最適化基礎論

電気通信大学大学院情報理工学研究科情報・ネットワーク工学専攻
2025年度後学期
火曜2限 (10:40-12:10)
教室：未定

岡本吉央

テーマ：高速指数時間アルゴリズム

注意：テーマは毎年変わります

実施形態

この授業はハイブリッド形式で行います．授業は教室からZoom配信します．スライドはZoomで共有し，板書も教室の黒板では行わず，Zoomで共有したスライドの上から行います．教室では，Zoomの画面をプロジェクタで投影します．そのため，教室で受講することのメリットは (1) ライブ感，時空間共有感覚を持てる，(2) 質問を口頭で即座にできる，(3) ネットワークトラブルに影響されない，などといった点にあります．授業は録画し，あとで公開します．

学生の皆さんの受講形態としては，「教室で授業を受ける」形を推奨しますが，自宅や研究室等からオンラインでリアルタイム受講しても構いませんし，オンデマンド型の受講をしても構いません．ただ，オンデマンド型では，質問をする機会が限られることにご注意ください．

内部シラバス (学務情報システムから見ることができるシラバス) で，Google Classroomのコードを確認し，参加をしてください．

講義資料

レポート課題

2回のレポート課題により評価を行う予定でいます．

公式シラバス

スケジュール (予定)

以下は仮の予定です．変更もありえます．

10/7 (1) 高速指数時間アルゴリズムの考え方
10/14 休み (体育祭)
10/21 (2) 分枝アルゴリズム：基礎
10/28 (3) 分枝アルゴリズム：高速化
11/4 (4) 分枝アルゴリズム：測度統治法
11/11 (5) 動的計画法：基礎
11/18 (6) 動的計画法：高速化
11/25 (7) 包除原理：原理
12/2 休み (秋ターム試験)
12/9 休み (出張)
12/16 (9) 包除原理：例
12/23 休み (出張)
12/30 休み (冬季休業)
1/6 (10) 集合たたみ込み：原理
1/13 (12) 集合たたみ込み：例
1/20 (13) 指数時間仮説：原理
1/27 (14) 指数時間仮説：証明
2/3 (15) 最近の話題

参考書，参考文献

この講義は以下の書籍・文献を参考にして構成されています．

Fedor V. Fomin, Dieter Kratsch, Exact Exponential Algorithms. Springer, 2010.
https://doi.org/10.1007/978-3-642-16533-7

他にも参考になるものはこちらに追加します．

過去の講義

離散最適化基礎論 (2024年度) テーマ：ジョブ・スケジューリングのアルゴリズム
離散最適化基礎論 (2023年度) テーマ：ネットワークフロー
離散最適化基礎論 (2022年度) テーマ：整数計画法
離散最適化基礎論 (2021年度) テーマ：グラフの準同型
離散最適化基礎論 (2020年度) テーマ：マッチング
離散最適化基礎論 (2019年度) テーマ：離散最適化における計算困難性
離散最適化基礎論 (2018年度) テーマ：理想グラフに対する組合せ最適化
離散最適化基礎論 (2017年度) テーマ：幾何的被覆問題
離散最適化基礎論 (2016年度) テーマ：グラフの木分解
離散最適化基礎論 (2015年度) テーマ：組合せ最適化におけるマトロイドの役割
離散最適化基礎論 (2014年度) テーマ：組合せ最適化における線形計画法の利用
離散最適化基礎論 (2013年度) テーマ：局所探索法の理論的側面
離散最適化基礎論 (2012年度) テーマ：ゲーム理論における離散構造とアルゴリズム

[Teaching Top] [Top]

okamotoy@uec.ac.jp