計算量理論特論2

更新日:2016-12-09

時間割コード

2501414

ナンバリングコード

GSI-11-6030-J

科目区分

主専攻科目

単位数

選択1単位

授業形態

特論

対象学年

修士1・2年

学期 曜日 時間 集中講義の有無

春2期火曜2限目

講義室

情報科学研究科棟1階第3講義室

開講専攻

数理情報学専攻

担当教員 所属

西村治道

所属

数理情報学専攻

メールアドレス

hnishimura@is.nagoya-u.ac.jp


授業概要


◆講義目的

計算量理論は理論計算機科学における中心的な理論の一つであり,暗号理論や符号理論など様々な分野でその考え方は応用されている。
本講義では,計算量理論について発展的な話題を扱うことで,計算量理論特有の考え方や使い方を応用する方法の習得を目指す。

◆授業内容

計算量理論特論1で修得した内容をもとに計算量理論についての発展的な話題を学ぶ。
ゼロ知識証明,確率検査証明とその近似アルゴリズムの困難性への応用,擬似乱数の計算量理論的側面などについて具体例を交えつつ学習する。
また,量子計算をもとにした計算量理論(量子計算量理論)についても学習する。
とくに,量子計算の従来の計算に対する計算量的優位性や量子計算の計算限界を理解する。

〔計画〕
1. イントロダクション
2. ゼロ知識証明
3. 確率検査証明
4. 疑似乱数
5. 量子計算の基礎
6. 量子アルゴリズム
7. 量子計算量理論

◆教科書・参考文献・履修条件等

教科書を使用する代わりに講義プリントを配布する。
参考書としては例えば以下の文献が挙げられる。
C.H.Papadimitriou著, ComputationalComplexity, Addison-Wesley, 1994.
S.Arora,B.Barak著, ComputationalComplexity, Cambridge, 2009.
M.A.Nielsen, I.L.Chuang, Quantum Computation and Quantum Information, Cambridge, 2000.

◆授業期間中の課題・宿題等

何度か授業で学んだことやその発展事項に関するレポート課題を提出する。

成績評価方法・基準

レポート100%で評価し,合計100点満点で60点以上を合格とする。

Course Title

Computational Complexity 2

Class Timetable Code

2501414

Numbering Code

GSI-11-6030-J

Course Category

Main majors

Credits

Elective1

Class Format

Advanced Lecture

Grade

Master1-2

Semester, Day and Period

Spring 2 semester Tuesday 2

Instructor(s)

NISHIMURA Harumichi

Affiliation

Department of Mathematical Informatics

Mailaddress

hnishimura@is.nagoya-u.ac.jp


Course Topics


Course Purpose

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.

Course Contents

Students are required to study developed topics in computational complexity, based on the contents which they acquire in Computational Complexity 1. They should be able to learn the following topics with examples; zero-knowledge, probabilistic checkable proof and its applications to hardness of approximation algorithms, and computational pseudo-random generator. Moreover, they should be able to learn complexity theory based on quantum mechanics (quantum computational complexity), in particular, computational advance of quantum computation compared to standard computation (based on classical mechanics) and the limit of quantum computation. The plan of the course is the following.

1. Introduction
2. zero-knowledge
3. probabilistic checkable proof
4. pseudo-random generator
5. basic of quantum computation
6. quantum algorithm
7. quantum complexity theory

Textbooks, Reference Materials and Requirements

In this course, I will distribute lecture notes.
References are, for example:
C.H.Papadimitriou, ComputationalComplexity, Addison-Wesley, 1994.
S.Arora, B.Barak, ComputationalComplexity, Cambridge, 2009.
M.A.Nielsen, I.L.Chuang, Quantum Computation and Quantum Information, Cambridge, 2000.

Assignment

I will assign reports on what students study in the class and more several times.

Grading Criteria

Your final grade will be decided based on reports (100%). To pass, students must earn at least 60 points out of 100.