理工学研究科Graduate School of Science and Engineering
PRI500X3（情報学基礎 / Principles of informatics 500）理論計算機科学特論１Theoretical Computer Science 1
和佐 州洋Kunihiro WASA
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学研究科Graduate School of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2022 |
| 授業コードClass code | YB002 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 春学期授業/Spring |
| 曜日・時限Day/Period | 水2/Wed.2 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 |
| 教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
| 配当年次Grade | |
| 単位数Credit(s) | 2 |
| 備考（履修条件等）Notes | |
| 実務経験のある教員による授業科目Class taught by instructors with practical experience | |
| カテゴリーCategory | 応用情報工学専攻 |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
One of the essential questions in Theoretical Computer Science is as follows: Where is the boundary between easy problems and hard problems?
In this lecture, students learn the fundamental definitions and properties of the theory of computation. In particular, we focus on (un)decidability and several important complexity classes such as P, NP, PSPACE, NPSPACE, and so on.
By the end of this lecture, students should be able to do the following: Students can explain several important definitions introduced in the lecture, can explain theorems related to them, and can prove several basic problems in the theory of computation.
Before/after each class meeting, students will be expected to spend four hours to understand the course content.
Your overall grade in the class will be decided based on the following
Term-end report: 60%、Mid-term examination: 40%.
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
理論計算機科学における重要な問いは，P=NP問題をはじめとした「計算するのが簡単な問題と難しい問題の境い目はどこにあるか」である．では，そもそも計算とはなにか．本講義では，計算とは何かを理解するための種々の定義や性質について，計算理論の観点から焦点を当てる．とくに，判定（不）可能性やいくつかの重要な計算量クラスに関して，その基礎的な事項を学ぶことを目標とする．
到達目標Goal
本講義の到達目標は，計算理論における様々な問題に対する理論的な証明を自らで構成できる，また，正しさを検証できる能力を養うことである．したがって，具体的には，(1) 判定（不）可能性や，様々な計算量クラスに関する定義を説明できる，(2) これらにかかわる基本的な定理の概要を説明できる，さらに，(3) 計算理論においてよく見られる証明技法を実際に利用して証明を自ら構成できることを目標とする．
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち、「DP1」「DP2」「DP3」に関連
授業で使用する言語Default language used in class
日本語 / Japanese
授業の進め方と方法Method(s)（学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. ）
本講義は，一つ一つの概念に関して丁寧に定義などともに説明すると同時に，実際に学生自ら手を動かして証明等を再構成できるように授業をすすめていく．また，演習課題等を通じて自己の理解度の把握を促す．
アクティブラーニング（グループディスカッション、ディベート等）の実施Active learning in class (Group discussion, Debate.etc.)
なし / No
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
第1回[対面/face to face]：導入
講義概要説明，基本的な事項の復習
第2回[対面/face to face]：チューリングマシン
チューリングマシンの定義，チャーチチューリングのテーゼ
第3回[対面/face to face]：判定可能な言語
判定可能な言語の紹介
第4回[対面/face to face]：判定不可能な言語
判定不可能な言語の紹介，対角線論法，Rice の定理
第5回[対面/face to face]：帰着可能性
帰着を用いた証明について，写像帰着可能性
第6回[対面/face to face]：計算履歴を用いた帰着
PCP問題の証明
第7回[対面/face to face]：中間試験
前半の内容に関する試験
第8回[対面/face to face]：P と NP
多項式時間で解ける問題，多対一還元の復習
第9回[対面/face to face]：NP完全
Cook-Levin の定理
第10回[対面/face to face]：PSPACE とSavitch の定理
空間計算量の定義， Savitch の定理の証明
第11回[オンライン/online]：PSPACE 完全問題
ゲームの必勝戦略，一般化しりとり
第12回[対面/face to face]：L, NL, NL = coNL
対数領域で解ける問題，Immerman-Szelepcséyi の定理
第13回[対面/face to face]：階層定理
領域階層定理と時間階層定理
第14回[対面/face to face]：対話的証明系
IP, グラフ同型性問題
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
【本授業の準備・復習時間は、各４時間を標準とします。】
テキスト（教科書）Textbooks
教科書は指定しない．教員が配布する資料を参考にすること．
参考書References
教科書としては指定しないが，本講義は Michael Sipser, Introduction to the Theory of Computation, Third Edition, Cengage Learning, 2013. を土台に講義を構成している．
成績評価の方法と基準Grading criteria
中間試験 40 % ，レポート 60% で成績を評価する．到達目標に対して60%以上の評価を得た場合合格となる．
学生の意見等からの気づきChanges following student comments
本年度授業担当者変更によりフィードバックできません