学部・大学院区分
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		秋２期 火曜日 １時限
Fall2 Tue 1
対象学年
Year		３年
3
授業形態
Course style		講義
Lecture
開講系（学部）・開講専攻（大学院）
Subject
CS共通
必修・選択
Required / Selected
ＣＳ(情報)必修


授業の目的　【日本語】
Goals of the Course(JPN)
問題を計算機で解くことができる，または効率良く解くことができるとはいかなることなのかという素朴で本質的な問いに答える計算理論の基本を学ぶ。まず計算機の代表的な数理モデルであるチューリング機械とその基本的性質を学ぶ。これに基づき，決定不能性という概念を理解し，対角線論法および還元法による決定不能性の証明法を学ぶ。さらに，問題の計算複雑さに関する基本概念と，代表的な計算複雑さのクラスであるPとNPについて学び，NP完全性の概念を理解する。
授業の目的　【英語】
Goals 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 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.
到達目標　【日本語】
Objectives of the Course(JPN)
計算機に能力の限界があるのだろうか，という基本的だが重要な問いに答えるために発展してきた，計算理論の基礎について学ぶ。
到達目標　【英語】
Objectives of the Course
授業の内容や構成
Course Content / Plan
まず，計算機の代表的モデルであるチューリング機械について学び，非決定性，多テープなどの拡張を行ってもその計算能力は変化しないことを学ぶ。次に，チューリング機械によって解くことのできない問題を表す判定不能性の概念を理解し，実際にそのような問題が存在することを対角線論法によって証明する。さらに，複数の問題間の難しさの関連づけを表す還元可能性という概念を学ぶ。後半では，計算機によって問題を解くときに要する時間や記憶域を表す計算複雑さの基本概念を学び，特に，重要なクラスであるPとNPおよび，NP完全性とその証明法について学ぶ。

1. チューリング機械
2. 能力が等価なモデル
3. 判定不能性
4. 還元による証明法
5. ポストの対応問題
6. 計算複雑さ
7. NP完全性
8. 総合演習
履修条件・関連する科目
Course Prerequisites and Related Courses
自然情報学科学生の受講は認めない。
成績評価の方法と基準
Course Evaluation Method and Criteria
演習課題の評価20％，期末試験80％，合計100点満点で60点以上を合格とする。
教科書・参考書
Textbook/Reference book
資料を配布する。参考文献は授業中に示す。「離散数学及び演習」，「アルゴリズム」の内容を理解していること。
課外学習等（授業時間外学習の指示）
Study Load(Self-directed Learning Outside Course Hours)
講義の内容を理解し，補完するために課題を与える。
授業開講形態等
Lecture format, etc.
遠隔授業（オンデマンド型）で行う場合の追加措置
Additional measures for remote class (on-demand class)