授業の目的 【日本語】
Goals of the Course(JPN) | | | 計算量理論は理論計算機科学における中心的な理論の一つであり，暗号理論や符号理論など様々な分野でその考え方は応用されている。本講義では，計算量理論について発展的な話題を扱うことで，計算量理論特有の考え方や使い方を応用する方法の習得を目指す。 |
|
|
授業の目的 【英語】
Goals of the Course | | | Computational complexity is one of core theories in theoretical computer science. Its concept is applied to various fields such as cryptography and coding theory. The aim of this course is to help students acquire the concept and usage of computational complexity by understanding developed topics in computational complexity. |
|
|
到達目標 【日本語】
Objectives of the Course(JPN) | | この授業では，受講者が授業終了時に，以下の知識・能力を身に着けていることを目標とする。
1. 対話型証明の応用であるゼロ知識証明や確率検査証明の概念を説明でき，技術的な内容が理解できる。
2. 通信計算量理論や量子計算量理論の基礎概念を説明でき，技術的な内容を理解できる。 |
|
|
到達目標 【英語】
Objectives of the Course | | |
|
授業の内容や構成
Course Content / Plan | | 計算量理論特論１で修得した内容をもとに計算量理論についての発展的な話題を学ぶ。ゼロ知識証明，確率検査証明とその近似アルゴリズムの困難性への応用などについて具体例を交えつつ学習する。また，計算の限界を示す手法である通信計算量理論や量子計算をもとにした計算量理論（量子計算量理論）についても学習する。
〔計画〕
1. イントロダクション
2. 対話型証明（発展）
3. ゼロ知識証明
4. 確率検査証明
5. 決定性通信計算量
6. 乱択通信計算量
7. 通信計算量理論の応用
8. 量子計算量理論 | |
|
|
履修条件・関連する科目
Course Prerequisites and Related Courses | | | 履修条件はないが，計算量理論特論１と併せて受講することが望ましい。 | |
|
|
成績評価の方法と基準
Course Evaluation Method and Criteria | | | レポート課題で評価します。レポートは到達目標に達していることが確認できるようなものを最低限の合格基準とします。100点満点で60点以上を合格とします。 | |
|
|
教科書・参考書
Textbook/Reference book | | 参考書としては例えば以下の文献が挙げられる。
C. H. Papadimitriou 著, Computational Complexity, Addison-Wesley, 1994.
S. Arora, B. Barak 著, Computational Complexity, Cambridge, 2009.
E. Kushilevitz, N. Nisan 著, Communication Complexity, Cambridge University Press, 1997.
M. A. Nielsen, I. L. Chuang 著, Quantum Computation and Quantum Information, Cambridge University Press, 2000. | |
|
|
課外学習等（授業時間外学習の指示）
Study Load(Self-directed Learning Outside Course Hours) | | | 授業後に毎回学んだ内容を復習すること。宿題が出たときは（他の学生と相談してもよいので）解いておくこと。 | |
|
|
授業開講形態等
Lecture format, etc. | | |
|
遠隔授業（オンデマンド型）で行う場合の追加措置
Additional measures for remote class (on-demand class) | | |
|