学部・大学院区分
Undergraduate / Graduate		情報学部
時間割コード
Registration Code		1001329
科目区分
Course Category
専門科目(コンピュータ科)関連専門科目(自然，人社)
科目名　【日本語】
Course Title		計算理論
科目名　【英語】
Course Title		Computation Theory
コースナンバリングコード
Course Numbering Code		SIS-13-3032-J
担当教員　【日本語】
Instructor		関 浩之 ○
担当教員　【英語】
Instructor		SEKI Hiroyuki ○
単位数
Credits		1
開講期・開講時間帯
Term / Day / Period		春２期 火曜日 ２時限
Spring2 Tue 2
対象学年
Year		３年
3
授業形態
Course style		講義
Lecture
開講系（学部）・開講専攻（大学院）
Subject
CS共通
必修・選択
Required / Selected
ＣＳ(情報)必修


授業の目的　【日本語】
Goals of the Course(JPN)
「問題を計算機で解くことができる，または効率良く解くことができるとは？」という素朴で本質的な問いに答える計算理論の基本を学ぶ。
授業の目的　【英語】
Goals of the Course
This course aims at explaining 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.
到達目標　【日本語】
Objectives of the Course(JPN)
まず，計算機の代表的モデルであるチューリング機械について学び，多テープ化，非決定性の導入などの拡張を行ってもその計算能力は変化しないことを学ぶ。次に，チューリング機械によって解くことのできない問題を表す判定不能性の概念を理解し，実際にそのような問題が存在することの対角線論法による証明を理解する。さらに，複数の問題間の難しさの関連づけを表す還元可能性という概念を学ぶ。
　最後に，計算機によって問題を解くときに要する時間やメモリ量を表す計算複雑さの基本概念を学び，特に，重要なクラスであるPとNPおよび，NP完全性とその証明法について学ぶ。
到達目標　【英語】
Objectives of the Course
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 deterministic Turing machine (DTM) as a formal model of computer. We also learn the variations of DTM such as multi-tape DTMs and nondeterministic Turing machines. Next, the definitions of decidability and undecidability will be given. Then we will learn the diagonal method and the 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.
授業の内容や構成
Course Content / Plan
計算理論の基礎について以下の授業計画に沿って学ぶ。
1. 決定性チューリング機械(DTM)
2. DTMの様々な拡張
3. 判定不能性
4. 還元による証明法
5. ポストの対応問題
6. 計算複雑さ
7. NP完全性
8. 総合演習
1. Deterministic Turing Machine (DTM)
2. Variations and Extensions of DTM
3. Undecidability
4. Reduction Method
5. Post's Correspondence Problem
6. Computational Complexity
7. NP-completeness
8. Summary and Exercises
履修条件・関連する科目
Course Prerequisites and Related Courses
自然情報学科学生の受講は認めない（「数理情報学1, 9」を受講してください）。
成績評価の方法と基準
Course Evaluation Method and Criteria
演習課題の評価約20％，期末試験約80％，合計100点満点で60点以上を合格とする。
教科書・参考書
Textbook/Reference book
資料を配布する。参考文献は授業中に示す。「離散数学及び演習」，「オートマトン・形式言語及び演習」，「アルゴリズム1,2」の内容を理解していること。
課外学習等（授業時間外学習の指示）
Study Load(Self-directed Learning Outside Course Hours)
講義の内容を理解し，補完するために課題を与える。
授業開講形態等
Lecture format, etc.
遠隔授業（オンデマンド型）で行う場合の追加措置
Additional measures for remote class (on-demand class)