| 授業の目的 【日本語】 | | | 問題を計算機で解くことができる，または効率良く解くことができるとはいかなることなのかという素朴で本質的な問いに答える計算理論の基本を学ぶ。まず計算機の代表的な数理モデルであるチューリング機械とその基本的性質を学ぶ。これに基づき，決定不能性という概念を理解し，対角線論法および還元法による決定不能性の証明法を学ぶ。さらに，問題の計算複雑さに関する基本概念と，代表的な計算複雑さのクラスであるPとNPについて学び，NP完全性の概念を理解する。 |
|
|
| 授業の目的 【英語】 | | | We will learn basic concepts on computability, which will give us an answer to the question: what it means when we say that a computer can solve a problem. We first learn the definition and properties of Turing machine as a formal model of computer. We also learn the variations of Turing machines such as nondeterministic Turing machines. Next, the definitions of decidability and undecidability will be given. Then we will learn diagonal method and reduction method as important proof techniques to show the undecidability of problems. Lastly, basic concepts on computational complexity such as time and space complexities will be given and NP-complete problems will be defined as one of the most important classes of problems in complexity theory. |
|
|
| 到達目標 【日本語】 | | | 計算機に能力の限界があるのだろうか，という基本的だが重要な問いに答えるために発展してきた，計算理論の基礎について学ぶ。 |
|
|
| 到達目標 【英語】 | | |
|
| 授業の内容や構成 | | まず，計算機の代表的モデルであるチューリング機械について学び，非決定性，多テープなどの拡張を行ってもその計算能力は変化しないことを学ぶ。次に，チューリング機械によって解くことのできない問題を表す判定不能性の概念を理解し，実際にそのような問題が存在することを対角線論法によって証明する。さらに，複数の問題間の難しさの関連づけを表す還元可能性という概念を学ぶ。後半では，計算機によって問題を解くときに要する時間や記憶域を表す計算複雑さの基本概念を学び，特に，重要なクラスであるPとNPおよび，NP完全性とその証明法について学ぶ。
1. チューリング機械
2. 能力が等価なモデル
3. 判定不能性
4. 対角線論法による証明
5. 還元法
6. 計算複雑さ
7. NP完全性の定義
8. NP完全問題の例 | |
|
|
| 履修条件・関連する科目 | | |
|
| 成績評価の方法と基準 | | | 演習課題の評価20％，期末試験80％，合計100点満点で60点以上を合格とする。 | |
|
|
| 教科書・参考書 | | | 資料を配布する。参考文献は授業中に示す。「離散数学及び演習」，「アルゴリズム」の内容を理解していること。 | |
|
|
| 課外学習等（授業時間外学習の指示） | | |
|
| 授業開講形態等 | | |
|
| 遠隔授業（オンデマンド型）で行う場合の追加措置 | | |
|