アルゴリズム設計論 (4002)

授業科目基本情報

科目区分 専門科目 教職科目 指定なし
単位数 1 選択・必修・自由 選択
授業形態 講義 主な使用言語 日本語
開講時期 履修登録システム 使用する
履修登録期間 2018/05/25~2018/06/07 履修取消期限 2018/06/07

教育プログラム別の履修区分

プログラム名 IS CB BS BN MS CP DS
履修区分
コア科目
履修方法 ・基盤科目及び専門科目から12単位以上履修すること。

授業科目概要

担当責任教員 井上 美智子
担当教員 井上美智子、大下 福仁
教育目的/授業目標 現実に直面する組合せ最適化問題には、実用的な時間で最適解を求められそうにないものが多いことが知られている。本講義では、そのような計算困難問題に対する現実的なアルゴリズムの設計手法を学習する。また、計算困難さを計る尺度として重要な概念であるNP完全性についても学習する。
指導方針 計算複雑性理論の根幹をなすNP完全性と理論計算機科学で近年多くの成果が発表されているアルゴリズム設計手法について解説する。本講義では、さまざまなアルゴリズム設計手法を、具体的なアルゴリズムとその性能解析とともに解説する。これにより、現実に直面する問題に対して、計算困難さを見積もり、さまざまなアプローチでアルゴリズムを設計できるようになることを目指す。

クラス情報



表示可能なデータがありません。

授業計画

回数 日付 [時間] テーマ 内容
1 6/5 [2] クラスPと多項式時間アルゴリズム クラスPについて学習する。クラスPを定義したうえで、クラスPに含まれる問題をいくつか解説する。また、アルゴリズム設計手法の一つである貪欲法について解説する。
2 6/7 [2] クラスNPとNP完全 クラスNPについて学習する。クラスNPを定義したうえで、多項式時間帰着、NP困難、NP完全の概念を解説する。組合せ最適化問題がNP完全である場合、全ての入力インスタンスに対して、多項式時間で、最適解を出力するアルゴリズムが存在しそうにないことを解説する。
3 6/11 [2] 厳密アルゴリズム1 NP完全問題に対する現実的なアプローチとして、制限された入力インスタンスに対して、多項式時間で、最適解を出力するアルゴリズムの設計手法を学ぶ。とくに、擬多項式時間アルゴリズム、固定パラメータアルゴリズムについて解説する。
4 6/13 [2] 厳密アルゴリズム2 NP完全問題に対する現実的なアプローチとして、全ての入力インスタンスに対して、比較的小さい指数時間で、最適解を出力するアルゴリズムの設計手法を学ぶ。とくに、分割統治法、包除原理を用いた指数時間アルゴリズム設計手法について解説する。
5 6/15 [2] 近似アルゴリズム1 NP完全問題に対する現実的なアプローチとして、全ての入力インスタンスに対して、多項式時間で、近似解を出力するアルゴリズム(近似アルゴリズム)の設計手法を学ぶ。TSPを例として、近似アルゴリズムの設計手法と近似困難性について解説する。
6 6/19 [2] 近似アルゴリズム2 第5回に引き続き、近似アルゴリズムの設計手法について解説する。とくに、線形計画問題を用いた近似アルゴリズム設計手法、PTAS、FPTASについて解説する。
7 6/26 [2] 乱択アルゴリズム 乱数を用いたアルゴリズム(乱択アルゴリズム)の設計手法について解説する。乱択アルゴリズムの分類を解説したうえで、乱択クイックソート、乱択素数判定アルゴリズムなど、基礎的かつ重要な乱択アルゴリズムについて解説する。
8 6/28 [2] まとめと試験 講義のまとめを行ない、試験によって受講者の習熟度を判定する。

授業日程

回数 日付 時間 講義室 備考
1 6/5 2 L3
2 6/7 2 L3
3 6/11 2 L3
4 6/13 2 L3
5 6/15 2 L3
6 6/19 2 L3
7 6/26 2 L3
8 6/28 2 L3

テキスト・参考書

テキスト 特に指定しない。本ページで資料を配布する。
参考書 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.)

その他

履修条件 アルゴリズムとデータ構造、グラフに関する基礎知識があることが望ましい。
オフィスアワー Eメールで連絡の上、日時を決める
成績評価の方法と基準 ・5段階(秀・優・良・可・不可)で評価する。
・試験(60%)およびレポート(40%)により評価する。
・アルゴリズム設計手法の理解、基礎知識の習得を基準とする。
関連科目 特になし
関連学位 工学
注意事項 特になし

授業関連URL



表示可能なデータがありません。

配布資料

  資料名 備考 公開期限
ALG-1 2019/03/31 ダウンロード
ALG-2 2019/03/31 ダウンロード
SUB-1 第1回演習課題の解答 2019/03/31 ダウンロード
ALG-3 2019/03/31 ダウンロード
ALG-4 2019/03/31 ダウンロード
ALG-5 2019/03/31 ダウンロード
ALG-6 2019/03/31 ダウンロード
ANS-1 レポート課題1,2の解答例 2019/03/31 ダウンロード
ALG-7 2019/03/31 ダウンロード
ANS-2 レポート課題3,4の解答例 2019/03/31 ダウンロード
ANS-3 レポート課題5,6の解答例 2019/03/31 ダウンロード