理工学部Faculty of Science and Engineering
COT200XE（計算基盤 / Computing technologies 200）計算量の理論Computational complexity
戸田 貴久Takahisa TODA
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学部Faculty of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2021 |
| 授業コードClass code | H6032 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 秋学期授業/Fall |
| 曜日・時限Day/Period | 金4/Fri.4 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 |
| 教室名称Classroom name | |
| 配当年次Grade | |
| 単位数Credit(s) | |
| 備考（履修条件等）Notes | |
| 他学部公開科目Open Program | |
| 他学部公開（履修条件等）Open Program (Notes) | |
| グローバル・オープン科目Global Open Program | |
| 成績優秀者の他学部科目履修制度対象Interdepartmental class taking system for Academic Achievers | |
| 成績優秀者の他学部科目履修（履修条件等）Interdepartmental class taking system for Academic Achievers (Notes) | |
| 実務経験のある教員による授業科目Class taught by instructors with practical experience | |
| SDGsCPSDGs CP | |
| アーバンデザインCPUrban Design CP | |
| ダイバーシティCPDiversity CP | |
| 未来教室CPLearning for the Future CP | |
| カーボンニュートラルCPCarbon Neutral CP | |
| 千代田コンソ単位互換提供（他大学向け）Chiyoda Campus Consortium | |
| カテゴリー＜理工学部＞Category |
応用情報工学科 学科専門科目 |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
In this lecture, we will study the theory of computational complexity to discuss the complexity to solve a given problem and its underlying theory of computability. For better understanding, the lecture begins with a focus on thinking about the difficulty of common problems.
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
地図上の2地点を結ぶ最短ルートを求める問題と、与えられた整数を素因数分解する問題を比較した場合、コンピュータにとってどちらが難しいだろうか？あるいは、これらの問題と将棋の最善手を発見する問題を比較するとどうだろう？実際にプログラムを作ってみて問題を解くために必要な時間を比較すればいい？しかし、地図も整数も将棋の局面も無数にあるし、解くプログラムだって無限に存在する。この講義では、それらを一般的に議論するための計算量の理論と，その基礎となる計算可能性の理論を学ぶ．
到達目標Goal
１．計算の一般的な概念を理解し、問題の難しさを定量化する方法を習得する。
２．代表的な計算量クラスと多項式時間還元性の概念を理解する。
３．計算可能性の概念を理解する。
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち、「DP1」と「DP2」と「DP4」に関連
授業で使用する言語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
※各回の授業形態は予定です。教員の指示に従ってください。
1：イントロダクション
講義全体の概要と目標を示す
2：計算の基本要素
計算の基本概念を導入し、問題の解法を記述する方法を学ぶ
3：計算時間の計り方
計算量の概念を導入し、四則演算など、主に算術演算に関する計算コストを具体的に求める
4：計算量の具体例
論理式の充足問題やグラフ問題に関する計算量を具体的に求める
5：クラスPとNP
代表的な計算量クラスとしてPとNPを導入し、それぞれのクラスに属する代表的な問題を紹介する
6：時間量クラス間の関係
NPよりも難しい問題のクラスを導入し、クラス間の関係を説明する
7：多項式時間還元可能性
問題の難しさを比較する方法を説明する
8：多項式時間還元可能性にもとづく完全性
計算量クラスで最も難しい問題について議論する
9：総合演習
総合演習
10：計算不可能性の証明と対角線論法
コンピュータで解くことのできない問題とその証明を示す
11：枚挙可能集合
停止性の保障されないアルゴリズムで解ける問題について考える
12：クラスRECとクラスRE
計算可能クラスの概念を導入する
13：算術階層
RECよりも難しい問題のクラスを導入、クラス間の関係を説明する
14：総合演習
総合演習
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
【本授業の準備・復習等の授業時間外学習は、4時間を標準とする】スライドを事前に読んでおくこと。毎回の授業で課題を出すので、授業の復習として取り組み、その結果をレポートにまとめて提出すること。
テキスト（教科書）Textbooks
なし
教材としてスライドなどを公開する
参考書References
渡辺治“計算可能性・計算の複雑さ入門”近代科学社, 1992年
Michael Sipser "計算理論の基礎3.複雑さの理論" 共立出版, 2008年
成績評価の方法と基準Grading criteria
成績は宿題などの課題の状況で評価する。期末試験は実施しない。
学生の意見等からの気づきChanges following student comments
難しい講義ですが、理解できたときの喜びは大きいです
学生が準備すべき機器他Equipment student needs to prepare
pdf を読める機器（パソコンなど）．
その他の重要事項Others
オンラインでの開講の場合、オンライン授業の方法や授業計画の変更、成績評価方法の変更などについては、学習支援システムでその都度提示する。担当教員から学習支援システムを通じた連絡がないか、日ごろからよく確認するようにしてください。