計算量理論特論1

更新日:2016-12-09

時間割コード

2501413

ナンバリングコード

GSI-11-6029-J

科目区分

主専攻科目

単位数

選択1単位

授業形態

特論

対象学年

修士1・2年

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

春1期火曜2限目

講義室

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

開講専攻

数理情報学専攻

担当教員 所属

西村治道

所属

数理情報学専攻

メールアドレス

hnishimura@is.nagoya-u.ac.jp


授業概要


◆講義目的

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

◆授業内容

まず計算量理論の基本的概念であるP,NP,NP完全,乱択アルゴリズムなどを復習するとともに,これらの概念についてより高度な具体例や解析技法などを習得する。
さらにNPの拡張概念である多項式階層,数え上げ問題の計算量クラス,対話型証明の概念とその基本的な性質や関係について学習する。

〔計画〕
1. イントロダクション
2. P,NP
3. NP完全
4. 乱択アルゴリズム
5. 多項式階層
6. 数え上げ問題
7. 対話型証明

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

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

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

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

成績評価方法・基準

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

Course Title

Computational Complexity 1

Class Timetable Code

2501413

Numbering Code

GSI-11-6029-J

Course Category

Main majors

Credits

Elective1

Class Format

Advanced Lecture

Grade

Master1-2

Semester, Day and Period

Spring 1 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 computational complexity broadly and deeply, so that students can deal with developed topics.

Course Contents

First, I will review basic concepts in computational complexity; P, NP, NP-complete, randomized algorithm. Students are required to acquire high-level examples and analytic techniques on these topics. Moreover, students should be able to learn the basic properties and relations on following extended concepts of NP; polynomial hierarchy, counting complexity classes, interactive proof. The plan of the course is the following.

1. Introduction
2. P,NP
3. NP-complete
4. randomized algorithm
5. polynomial hierarchy
6. counting complexity classes
7. interactive proof

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.

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.