Language:

2021年度 アルゴリズム設計論 (4093)

授業科目基本情報PDFダウンロード

科目区分 専門科目 教職科目 情報
単位数 1 選択・必修・自由 選択
授業形態 講義 主な使用言語 英語
開講時期 履修登録システム 使用する
履修登録期間 2021/04/13~2021/05/14 履修取消期限 2021/05/14

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

プログラム名 IS CB BS BN MS CP DS
履修区分
コア科目
履修方法 ・修士論文研究又は特別課題研究を履修する場合は、基盤科目及び専門科目から12単位以上履修すること。
・課題研究を履修する場合は、基盤科目及び専門科目から14単位以上履修すること。

授業科目概要

担当責任教員 井上 美智子
担当教員 井上美智子、大下 福仁
教育目的/学修到達目標 【教育目的】
現実に直面する組合せ最適化問題には、実用的な時間で最適解を求められそうにないものが多いことが知られている。本講義では、そのような計算困難問題に対する現実的なアルゴリズムの設計手法を学習する。また、計算困難さを計る尺度として重要な概念であるNP完全性についても学習する。さらに、量子コンピューティングや分散コンピューティングなど様々な計算理論を学習する。これにより、現実に直面する問題に対して、計算困難さを見積もり、さまざまなアプローチでアルゴリズムを設計できるようになることを目的とする。

【学修到達目標】
1) 組合せ最適化問題、計算困難性、量子コンピューティング、分散コンピューティングについて説明、記述できる。
2) 組合せ最適化問題、計算困難性、量子コンピューティング、分散コンピューティングについて整理、議論ができる。
3) 組合せ最適化問題、計算困難性、量子コンピューティング、分散コンピューティングについて俯瞰、表現できる。
授業概要/指導方針 【授業概要/指導方針】
計算複雑性理論の根幹をなすNP完全性と理論計算機科学で近年多くの成果が発表されているアルゴリズム設計手法について解説する。本講義では、さまざまなアルゴリズム設計手法を、具体的なアルゴリズムとその性能解析とともに解説する。さらに、量子コンピューティング、分散コンピューティングのための計算モデル、代表的な設計パラダイム、アルゴリズムの設計・解析手法について解説する。演習を交えながら講義を行い、履修生の理解を深めるための課題を与える。

【授業時間外学修(予習・復習等)の目安】
各回毎に授業内で与えられたAssignmentの予習2時間
各回毎に復習2時間程度

クラス情報



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

授業計画

[1限目 9:20-10:50] [2限目 11:00-12:30] [3限目 13:30-15:00] [4限目 15:10-16:40] [5限目 16:50-18:20] [6限目 18:30-20:00]
回数 日付 [時間] 担当教員 テーマ 内容
1 4/23 [2] 井上 美智子 クラスP、クラスNPとNP完全 クラスP、クラスNP、多項式時間帰着、NP困難、NP完全の概念について学習する。
2 5/14 [2] 大下 福仁 厳密アルゴリズム NP完全問題に対する現実的なアプローチとして、厳密アルゴリズム(擬多項式時間アルゴリズム、高速な指数時間アルゴリズム)を学習する。
3 5/21 [2] 大下 福仁 近似アルゴリズム NP完全問題に対する現実的なアプローチとして、近似アルゴリズムを学習する。
4 6/4 [2] 大下 福仁 乱択アルゴリズム 乱数を用いたアルゴリズム(乱択アルゴリズム)の設計手法について学習する。
5 6/11 [2] 井上 美智子 量子コンピューティング 量子コンピューティング、量子アルゴリズムに関する基礎を学習する。
6 6/18 [2] 大下 福仁 コンジェストモデルとアルゴリズム 同期分散システムの計算モデルであるコンジェストモデルと代表的なアルゴリズムに関して学習する。
7 6/22 [2] 井上 美智子 自己安定分散アルゴリズム システム内に故障が発生しても、システムが自律的に正常な状況に回復し安定する自己安定アルゴリズムに関して学習する。
8 6/25 [2] 井上 美智子 無待機共有メモリアルゴリズム 共有メモリシステムのための分散コンピューティング計算モデルと強い故障耐性である無待機性、および、無待機共有メモリアルゴリズムを学習する。

授業日程

[1限目 9:20-10:50] [2限目 11:00-12:30] [3限目 13:30-15:00] [4限目 15:10-16:40] [5限目 16:50-18:20] [6限目 18:30-20:00]
回数 日付 時間 講義室 備考
1 4/23 2 エーアイ大講義室[L1](IS)
2 5/14 2 エーアイ大講義室[L1](IS)
3 5/21 2 エーアイ大講義室[L1](IS)
4 6/4 2 エーアイ大講義室[L1](IS)
5 6/11 2 エーアイ大講義室[L1](IS)
6 6/18 2 エーアイ大講義室[L1](IS)
7 6/22 2 エーアイ大講義室[L1](IS)
8 6/25 2 エーアイ大講義室[L1](IS)

テキスト・参考書

テキスト 特に指定しない、講義資料を用意する。
参考書 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.)
4. H. Attiya, J. Welch : Distributed Computing: Fundamentals, Simulations and Advanced Topics, John Wiley & Sons, 2004.
5. M. A. Nielsen, I. L. Chuang: Quantum Computation and Quantum Information (10th Anniversary Edition), Cambridge University Press, 2010. (訳本: 木村: 量子コンピュータと量子通信, オーム社.)

その他

履修条件 アルゴリズムとデータ構造に関する基礎知識があることが望ましい。
オフィスアワー Eメールで連絡の上、日時を決める。
メールアドレス:kounoe@is.nait.jp(井上)、f-oosita@is.naist.jp(大下)
成績評価の方法と基準 ・5段階(秀・優・良・可・不可)で評価する。
・レポートにより評価する。
関連科目 特になし
関連学位 工学
注意事項 特になし

授業関連URL



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

配布資料



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