授業の目的 【日本語】
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 of computational complexity by understanding computational complexity broadly and deeply, so that students can deal with developed topics. |
|
|
到達目標 【日本語】
Objectives of the Course(JPN) | | この授業では，受講者が授業終了時に，以下の知識・能力を身に着けていることを目指す。
１．NPと乱択アルゴリズムを含む計算量理論の基本概念やその技術的な内容を説明できる。
2. 多項式階層や対話型証明などのNPおよび乱択アルゴリズムの拡張概念を説明でき，技術的な内容を理解できる。 |
|
|
到達目標 【英語】
Objectives of the Course | | |
|
授業の内容や構成
Course Content / Plan | | まず計算量理論の基本的概念であるP，NP，NP完全，乱択アルゴリズムなどを復習するとともに，これらの概念についてより高度な具体例や解析技法などを習得する。さらにNPの拡張概念である多項式階層，数え上げ問題の計算量クラス，対話型証明の概念とその基本的な性質や関係について学習する。
〔計画〕
1. イントロダクション
2. 時間計算量
3. 空間計算量
4. NP
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 University Press, 2009.
O. Goldreich 著，Computational Complexity, Cambridge University Press, 2008. | |
|
|
課外学習等（授業時間外学習の指示）
Study Load(Self-directed Learning Outside Course Hours) | | | 授業後に毎回学んだ内容を復習すること。宿題が出たときは（他の学生と相談してもよいので）解いておくこと。 | |
|
|
授業開講形態等
Lecture format, etc. | | |
|
遠隔授業（オンデマンド型）で行う場合の追加措置
Additional measures for remote class (on-demand class) | | |
|