アルゴリズム設計論 (130004) Advanced Algorithm Design (130004)
 
◇ 担当教員 Instructor : 大下 福仁(Fukuhito Ooshita / おおした ふくひと)、 井上 美智子(Michiko Inoue / いのうえ みちこ)
◇ 単位数 Credits : 1単位 ◇ 選択・必修 Required/Elective : 選択 ◇ 講義室 Room : L2
◇ 講義スタイル Style : 講義/公開
◇ 開講時期 Quarter : Ⅱ期 金曜1限

◇ 授業目的 Course goals : 現実に直面する組合せ最適化問題には、実用的な時間で最適解を求められそうにないものが多いことが知られている。本講義では、そのような計算困難問題に対する現実的なアルゴリズムの設計手法を学習する。また、計算困難さを計る尺度として重要な概念であるNP完全性についても学習する。

We face many combinatorial optimization problems in daily life, but it is known that most of them cannot be solved in practical time. In this lecture, we study several techniques to design practical algorithms for such hard problems. In addition, we study the theory of NP-completeness to understand hardness of problems.
◇ 授業内容 Course description : 1. クラスPと多項式時間アルゴリズム (Class P and Polynomial-Time Algorithms)
2. クラスNPとNP完全 (Class NP and NP-Completeness)
3. 擬多項式時間アルゴリズムとパラメータ化計算量 (Pseudo-Polynomial-Time Algorithms and Parameterized Complexity)
4. 指数時間アルゴリズム (Exact Exponential Algorithms)
5. 近似アルゴリズム (Approximation Algorithms)
6. 線形計画法を用いた近似アルゴリズム (Approximation Algorithms Based on Linear Programming)
7. 乱択アルゴリズム (Randomized Algorithms)
8. まとめと試験 (Conclusions and Examination)

◇ 教科書 Textbook : 特に指定しない。本ページで資料を配布する。
No designated textbook. The handouts are available from this page.
◇ 参考書 Reference materials : 1. J. Hromkovic, Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics (2nd Edition), Springer Berlin Heidelberg, 2010.
(訳本:和田,増澤,元木,計算困難問題に対するアルゴリズム理論,丸善出版,2012.)
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (3rd Edition), The MIT Press, 2009.
(訳本:浅野,岩野,梅尾,山下,和田,アルゴリズムイントロダクション第3版,近代科学社,2013.)
3. D. P. Williamson, D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.
(訳本:浅野,近似アルゴリズムデザイン,共立出版,2015.)

◇ 履修条件 Prerequisites : アルゴリズムとデータ構造、グラフに関する基礎知識があることが望ましい。
Students are desired to have basic knowledge on algorithms, data structures, and graphs.
◇ 成績評価 Grading : 試験(60%)およびレポート(40%)により評価する。
Students are evaluated by examinations (60%) and reports (40%).
◇ オフィスアワー Office Hours : 金曜日 16:50 - 18:20 (オフィス B412(2)室)。その他、アポイントを取ればいつでも。
Every Friday of the second semester 16:50 - 18:20 at Rooms B412(2), or anytime if appointed.
◇ 配布資料 Handouts :
種類 公開日 教材名 備 考

PDF
2016-06-01 アルゴリズム設計論 第1回

PDF
2016-06-03 アルゴリズム設計論 第1回 補足・練習問題の解答

PDF
2016-06-08 アルゴリズム設計論 第2回

PDF
2016-06-17 アルゴリズム設計論 第3回 6/16 P39を修正、レポート課題は7/1に提出してください

PDF
2016-06-22 アルゴリズム設計論 第4回

PDF
2016-06-22 レポート課題 1・2の解答例

PDF
2016-06-29 アルゴリズム設計論 第5回

PDF
2016-07-09 レポート課題 3・4の解答例

PDF
2016-07-13 アルゴリズム設計論 第6回

PDF
2016-07-27 アルゴリズム設計論 第7回

PDF
2016-07-29 レポート課題 5・6の解答例
※アイコンをクリックし【対象をファイルに保存】を選択し教材をダウンロードしてください。