計算の複雑さ特論

Advanced Computational Complexity

996D602

63CSALC602

入山　聖史

Satoshi Iriyama

2023年度後期

Semester 3rd and 4th

水曜3限

3rd, Wednesday

創域理工学研究科　情報計算科学専攻

Department of Information Sciences, Graduate School of Science and Technology

2.0単位

講義

Lecture

-

対面授業/On-site class

計算の複雑さの数理、計算モデルの数学的取り扱いについて深く理解する。アルゴリズムについての先進的な内容を学ぶ。

Mathematics of computational complexity and mathematical treatment with computational model are deeply understood. Advanced contents on algorithms is also discussed.

さまざまな言語クラスにおける問題に対してアルゴリズムを構成し、計算の複雑さの議論ができることを目指す。

We aim to construct efficient algorithms for problems in various language classes, and discuss about the computational complexity deeply.

1. 言語クラスの定義や、相互の関係について説明できるようになる。
2. さまざまな計算モデルにおける計算の複雑さを議論できるようになる。
3. 問題に対して効果的なアルゴリズムを構成できるようになる。
4. 計算の複雑さに関する先進的な研究を説明できるようになる。

1. To explain the definition of language classes and mutual relationship.
2. To discuss the computational complexity of various computational models.
3. To construct an efficient algorithm for various problems.
4. To explain advanced research on computational complexity.

計算の理論についての基礎的な知識があることが望ましい。

This class requires a fundamental knowledge of computational theory

-

-

各回ごとに必ず復習すること。

Require a review for every lecture.

レポートなどを通して、総合的に評価する。

Evaluated comprehensively through reports etc..

・S：到達目標を十分に達成し、極めて優秀な成果を収めている
・A：到達目標を十分に達成している
・B：到達目標を達成している
・C：到達目標を最低限達成している
・D：到達目標を達成していない
・-：学修成果の評価を判断する要件を欠格している

・S：Achieved outcomes, excellent result
・A：Achieved outcomes, good result
・B：Achieved outcomes
・C：Minimally achieved outcomes
・D：Did not achieve outcomes
・-：Failed to meet even the minimal requirements for evaluation

N

-

教科書および一部の参考書は、MyKiTS (教科書販売サイト) から検索・購入可能です。
It is possible to search for and purchase textbooks and certain reference materials at MyKiTS (online textbook store).
​https://gomykits.kinokuniya.co.jp/tokyorika/​​​

S.Arora, B.Barak, Computational Complexity, Cambridge.

第１回：序論、計算の理論の歴史を紹介し、数学的準備を行う．

第２回：計算モデル(1)、決定性チューリング機械の定義を説明する．

第３回：計算モデル(2)、非決定性チューリング機械の定義と例を説明する．

第４回：計算の複雑さ(1)、クラスPとそれに属する問題、アルゴリズムを説明する。

第５回：計算の複雑さ(2)、クラスNPとNP完全性について説明する。

第６回：計算の複雑さ(3)、領域計算量と、時間計算量との関係について説明する。

第７回：確率的計算(1)、確率的チューリング機械の定義を説明する。

第８回：確率的計算(2)、クラスBPPとその他の言語クラスについて説明する。

第９回：計算可能性、計算可能性と万能チューリング機械について説明する。

第１０回：暗号理論(1)、暗号理論と計算の複雑さとの関連を説明する。

第１１回：暗号理論(2)、擬似乱数と計算の複雑さとの関連を説明する。

第１２回：計算の複雑さについての先進的話題(1)，計算理論における先進的なテーマについて議論する．

第１３回：計算の複雑さについての先進的話題(2)，計算理論における先進的なテーマについて議論する．

第１４回：計算の複雑さについての先進的話題(3)，計算理論における先進的なテーマについて議論する．

第１５回：まとめ

The 1st: Introduction, introduces the history of computational theory and prepares mathematical.
The 2nd: Model of computation (1), Explain the definition of deterministic Turing machine.

The 3rd: Model of computation (2), Explain the definition and examples of non-deterministic Turing machine.

The 4th: Complexity of computation (1), Explain the class P and its problems and algorithms.

The 5th: Complexity of computation (2), Explain the class NP and NP-completeness.

The 6th: Complexity of computation (3), Explain the relationship between space complexity and time complexity

The 7th: Probabilistic algorithm (1), Explain the definition of probabilistic Turing machine.

The 8th: Probabilistic algorithm (2), Explain class BPP and other language classes.

The 9th: Explain computability, computability and universal Turing machine.

The 10th: Cryptographic theory (1), Explain the relationship between cryptographic theory and computational complexity.

The 11th: Cryptographic theory (2), Explain the relationship between pseudo random number and computational complexity.

The 12th: Advanced topics on computational complexity (1), Discuss advanced themes in computational theory.

The 13th: Advanced topics on computational complexity (2), discuss advanced themes in computational theory.

The 14th: Advanced Topics on Complexity of Computation (3), Discuss advanced themes in computational theory.

The 15th: Conclusion

-

-

-

なし

None