| 授業の目的 【日本語】 | | | 本講義は数理情報学1で学習した計算複雑さの概念をもとに，計算量理論の根幹を成す基本事項を修得する。PとNP，多項式時間帰着，NP完全，NP困難の概念を具体例とともに学習し，様々な問題の持つ計算複雑さを体系的に理解する。また，乱択アルゴリズムなど発展的なアルゴリズムを定式化する計算モデルと，それらのアルゴリズムで効率的に解ける問題の持つ特徴や基本的性質を修得する。さらに計算量理論の現在暗号へのつながりなど応用的な話題も学習する。 |
|
|
| 授業の目的 【英語】 | | | In this lecture, based on the concept of computational complexity learned in Mathematical Informatics 1, students will learn the basic items that form the basis of computational complexity theory. They will learn the concepts of P and NP, polynomial-time reduction, NP-completeness, and NP-hardness with concrete examples to systematically understand the computational complexity of various problems. In addition, they will learn the computational models that formulate advanced algorithms such as randomized algorithms, and the characteristics and basic properties of problems that can be efficiently solved by those algorithms. In addition, students will learn applied topics such as the connection of computational complexity theory to current cryptography. |
|
|
| 到達目標 【日本語】 | | | 計算量理論は今日のコンピュータ科学において必要不可欠な基礎理論である。本講義は数理情報学1で学習した計算複雑さの概念をもとに，計算量理論の根幹を成す基本事項を修得する。 |
|
|
| 到達目標 【英語】 | | |
|
| 授業の内容や構成 | | PとNP，多項式時間帰着，NP完全，NP困難の概念を具体例とともに学習し，様々な（計算）問題の持つ計算複雑さを体系的に理解する。また，乱択アルゴリズムなど発展的なアルゴリズムを定式化する計算モデルと，それらのアルゴリズムで効率的に解ける問題の持つ特徴や基本的性質を修得する。さらに計算量理論の現在暗号へのつながりなど応用的な話題も学習する。
1. ガイダンス
2. P
3. NP
4. 多項式時間帰着
5. NP完全，NP困難
6. 乱択アルゴリズム
7. 計算量理論の応用
8. まとめ | |
|
|
| 履修条件・関連する科目 | | |
|
| 成績評価の方法と基準 | | | 講義中に与える課題の評価40％，期末試験60％，合計100点満点で60点以上を合格とする． | |
|
|
| 教科書・参考書 | | | 必要に応じて講義プリントを配布する。参考文献等は講義中に紹介する。履修条件は特にないが，数理情報学１を履修していた方が望ましい。 | |
|
|
| 課外学習等（授業時間外学習の指示） | | | 講義において説明した理論を理解するために課題を与える． | |
|
|
| 授業開講形態等 | | |
|
| 遠隔授業（オンデマンド型）で行う場合の追加措置 | | |
|