授業の目的 【日本語】
Goals of the Course(JPN) | | 本講義の目的は、情報処理の根幹となる「計算」という行為について数学的に洞察し、計算機の能力の限界について正しい認識を習得することにある。
高度に情報化の進んだ現代では、もはやコンピュータに解けない問題は存在しないかのように錯覚することも多い。しかしそれは致命的な間違いであり、どれだけ性能が向上しても計算機には絶対に解けない問題が存在することが示されている。また，我々の身近なところにも、計算機では効率的に解けないであろうと強く予想されている問題が多数存在している。それら計算機の能力の限界を正しく理解しておくことは、今後ますます活用の進む計算機と向き合ううえで必須の要件である。そのために必要となる重要な概念を学び、基本的な証明技法を身につけることが本講義「計算理論」の目的である。 |
|
|
授業の目的 【英語】
Goals of the Course | | This lecture aims to learn the inherent limits of computers through mathematical investigation on “computation.”
Today’s information-driven society may lead us to misunderstand that computers can solve any problem. This is crucially false, as there are problems that computers cannot solve by any means. There are also problems, some very familiar to our daily lives, that are strongly conjectured not to be efficiently solvable by computers. In this “Computation Theory” course, students learn essential concepts and proof techniques necessary to recognize computers' inherent limits, which will be especially important as computers will be used in broader applications. |
|
|
到達目標 【日本語】
Objectives of the Course(JPN) | | 本講義では、チューリング機械、判定不能性、計算複雑さ、NP完全性といった重要な概念を理解し、それら概念を現実世界に展開していくための基本的な証明技法を学ぶ。
はじめに代表的な計算モデルである決定性チューリング機械について学び、多テープ化、非決定性の導入等の拡張を行っても、その計算能力が変化しないことを理解する。次に、チューリング機械では解くことのできない判定不能性の概念を学び、判定不能な問題が実際に存在することを対角線論法による証明を通じて確認する。さらに、複数の異なる問題を関連付ける還元可能性の概念を学び、ある問題が判定不能であることを証明するための技法を習得する。講義の終盤では、計算機により問題を解くのに要する時間の長さやメモリの量に基づいて計算複雑さが定義されることを学び、とくに重要な計算複雑さのクラスとしてPとNPが存在すること、NP完全性とその証明法について学ぶ。 |
|
|
到達目標 【英語】
Objectives of the Course | | This course teaches students essential concepts such as Turing machines, undecidability, computational complexity, and NP-completeness. It also introduces basic proof techniques to apply the learned concepts to real-world problems.
After the introduction of deterministic Turing machines, students learn that the Turing machine's capability is not affected by expansions such as multi-tape usage and the introduction of non-determinism. We also introduce the concept of undecidability and confirm through a diagonal argument that an undecidable problem exists. The idea of the reducibility of problems is then introduced, and we acquire the technique to show the undecidability of a problem. At the end of the course, we learn that complexity classes are defined by the time and memory used by a Turing machine. Two important classes of P and NP are introduced, and we learn the concept of NP-completeness and related proof techniques. |
|
|
授業の内容や構成
Course Content / Plan | | 計算理論の基礎について以下の授業計画に沿って学ぶ。
1. 決定性チューリング機械(DTM)
2. DTMの様々な拡張
3. 判定不能性
4. 還元による証明法
5. ポストの対応問題
6. 計算複雑さ
7. NP完全性
8. 総合演習 | |
|
|
履修条件・関連する科目
Course Prerequisites and Related Courses | | | 自然情報学科学生の受講は認めない（「数理情報学1, 2, 9」を受講してください） | |
|
|
成績評価の方法と基準
Course Evaluation Method and Criteria | | | 中間レポートの評価30％，期末試験70％，合計100点満点で60点以上を合格とする。 | |
|
|
教科書・参考書
Textbook/Reference book | | | 資料をTACT，Teamsで配布する。参考文献は授業中に示す。「離散数学及び演習」，「オートマトン・形式言語及び演習」，「アルゴリズム1,2」の内容を理解していること。 | |
|
|
課外学習等（授業時間外学習の指示）
Study Load(Self-directed Learning Outside Course Hours) | | |
|
授業開講形態等
Lecture format, etc. | | 教室での受講を原則とするが、講義の様子はオンライン中継する予定である。
体調等に不安のある学生は、中継画像の視聴による講義参加も認める。 |
|
|
遠隔授業（オンデマンド型）で行う場合の追加措置
Additional measures for remote class (on-demand class) | | | 機構アカウントにより参加できるチーム（Microsoft Teams）を作成し、講義中継、講義資料や講義録画ビデオ等をチーム参加者に提供する。 |
|
|