計算の理論、PとNP、近似アルゴリズム

"「アルゴリズムとデータ構造」で学んだ、コンピュータで問題を解くためのモデル化・アルゴリズム・データ構造の知識を前提として、情報系の学生として知っておくべき「コンピュータで計算するということの意味」を深く考え、より応用性の高いアルゴリズムについて学んでいく。特にPとNP、NP完全等については、

・計算の理論: チューリングマシンと判定可能性
・PとNP
・NP完全とNP困難
・近似アルゴリズム
・乱択アルゴリズム
・オンラインアルゴリズム"

"・計算理論の基礎を身につける: 特にチューリングマシンとクラスPおよびNP、そしてNP完全・NP困難について理解する
・プログラムを用いた問題解決力を向上させる: 各種の高度なアルゴリズムを理解し、プログラミング言語を用いて実装できるようになる"

"以下を予定している。
1. はじめに
2. チューリングマシン
3. 判定可能性
4. PとNP
5. NP完全とは
6. 様々なNP完全問題
7. NP困難とは
8. NP完全・困難問題のサーベイ　　　　　　　　　
9. 近似アルゴリズム(PTAS)　　　　　　
10. 近似アルゴリズム(FPTAS)　　
11. グラフ構造と近似アルゴリズム
12. 乱択アルゴリズム
13. オンラインアルゴリズム　　　　　
14. まとめと今後の展望
"

各自がオンライン教材を用いた予習・復習を行うことを前提に実施します。

各回のトピックに対応した課題に、講義外の時間を活用して取り組むことが必須です。

試験の結果と、課題の提出内容により評価を行います。なお5回以上欠席した場合には、理由の如何を問わず、単位は習得できません。

「コンピュータサイエンス概論1」「コンピュータサイエンス概論2」「アルゴリズムとデータ構造」の単位を取得済みであることが必要です。

各回の講義に対応したオンライン教材を事前に提供します。

授業中に紹介します。

受講要件を参照のこと。