Language:

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

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

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

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

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

授業科目概要

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

クラス情報



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

授業計画

[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/24 [2] 井上 美智子 クラスP、クラスNPとNP完全 クラスP、クラスNP、多項式時間帰着、NP困難、NP完全の概念について学習する。
2 4/28 [2] 大下 福仁 厳密アルゴリズム NP完全問題に対する現実的なアプローチとして、厳密アルゴリズム(擬多項式時間アルゴリズム、高速な指数時間アルゴリズム)を学習する。
3 5/15 [2] 大下 福仁 近似アルゴリズム NP完全問題に対する現実的なアプローチとして、近似アルゴリズムを学習する。
4 5/22 [2] 大下 福仁 乱択アルゴリズム 乱数を用いたアルゴリズム(乱択アルゴリズム)の設計手法について学習する。
5 6/8 [4] 井上 美智子 量子コンピューティング 量子コンピューティング、量子アルゴリズムに関する基礎を学習する。
6 6/12 [2] 井上 美智子 コンジェストモデルとアルゴリズム 同期分散システムの計算モデルであるコンジェストモデルと代表的なアルゴリズムに関して学習する。
7 6/19 [2] 井上 美智子 自己安定分散アルゴリズム システム内に故障が発生しても、システムが自律的に正常な状況に回復し安定する自己安定アルゴリズムに関して学習する。
8 6/26 [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/24 2 エーアイ大講義室[L1](IS) ビデオ公開日5月8日.レポート〆切5月12日(火).
2 4/28 2 エーアイ大講義室[L1](IS) ビデオ公開日5月12日.第2回から第4回のミニレポートをまとめて,6月12日までに提出.(5/7変更.ビデオ・スライド内の締切は無視してください)
3 5/15 2 エーアイ大講義室[L1](IS) ビデオ公開日5月22日.第2回から第4回のミニレポートをまとめて,6月12日までに提出.
4 5/22 2 エーアイ大講義室[L1](IS) ビデオ公開日5月29日.第2回から第4回のミニレポートをまとめて,6月12日までに提出.
5 6/8 4 エーアイ大講義室[L1](IS) ビデオ公開日は6月12日。課題提出〆切は6月19日(金)。課題、およびその提出方法は講義内で説明します。
6 6/12 2 エーアイ大講義室[L1](IS) ビデオ公開日は6月19日。課題提出〆切は6月26日(金)。課題、およびその提出方法は講義内で説明します。
7 6/19 2 エーアイ大講義室[L1](IS) ビデオ公開日は6月26日。課題提出〆切は7月3日(金)。課題、およびその提出方法は講義内で説明します。
8 6/26 2 エーアイ大講義室[L1](IS) ビデオ公開日は7月3日。課題提出〆切は7月10日(金)。課題、およびその提出方法は講義内で説明します。

テキスト・参考書

テキスト 特に指定しない、講義資料を用意する。
参考書 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



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

配布資料

  資料名 備考 公開期限
AdvancedAlgorithm-4j 2020/08/20 学内専用
AdvancedAlgorithm-4e 2020/08/20 学内専用
AdvancedAlgorithm-5e 2020/09/05 学内専用
AdvancedAlgorithm-5j 2020/09/05 学内専用
AdvancedAlgorithm-6e 2020/09/09 学内専用
AdvancedAlgorithm-6j 2020/09/09 学内専用
AdvancedAlgorithm-7e 2020/09/16 学内専用
AdvancedAlgorithm-7j 2020/09/16 学内専用
AdvancedAlgorithm-8e 2020/09/23 学内専用
AdvancedAlgorithm-8j 2020/09/23 学内専用