学部・大学院区分
Undergraduate / Graduate

情報・博前

時間割コード
Registration Code

2550049

科目区分
Course Category

主専攻科目

科目名　【日本語】
Course Title

ソフトウェア基礎論特論A

科目名　【英語】
Course Title

Advanced Lectures on Foundations of Software A

コースナンバリングコード
Course Numbering Code

GSI156041J

担当教員　【日本語】
Instructor

関浩之 ○

担当教員　【英語】
Instructor

SEKI Hiroyuki ○

単位数
Credits

開講期・開講時間帯
Term / Day / Period

秋１期月曜日３時限
Fall1 Mon 3

対象学年
Year

１年
1

授業形態
Course style

開講系（学部）・開講専攻（大学院）
Subject

情報システム学専攻

必修・選択
Required / Selected

授業の目的　【日本語】
Goals of the Course(JPN)

問題の難しさをはかる尺度として，特に重要な考え方であるNP完全性等について説明する。まず，時間計算量と領域計算量等の概念を定義した後，NP完全性を定義する。次に，問題の難しさを相対化する技法である還元法を用いてNP完全性を証明する方法を具体例に即して説明する。さらに，クラスco-NPとPSPACE，ランダム計算，交代計算，対話証明系についても説明する。

授業の目的　【英語】
Goals of the Course

到達目標　【日本語】
Objectives of the Course(JPN)

計算機で問題を解くときの問題の難しさを計る尺度についての体系である計算複雑さの理論の基本概念と方法論を修得する。NP完全性の還元法による証明技法を例題を通して身につける。PSPACE，BPP, IP等，その他の計算量クラスとそれらの相互関係を理解する。

到達目標　【英語】
Objectives of the Course

Computational complexity theory provides mathematical concepts and tools for representing the computational hardness of problems. Students are expected to understand the basic definitions and methodologies of the theory such as NP-completeness, to be able to use the reduction method for proving NP-completeness through examples, and to grasp other important complexity classes such as PSPACE, BPP and IP as well as their relationships.

授業の内容や構成
Course Content / Plan

Basic concepts on computation such as time and space complexities are introduced and NP-completeness is defined. Then we learn reduction technique, which can compare hardness of two problems and is useful for proving that a problem is NP-complete. PSPACE and co-NP are also explained. In the latter part, some other computation models including randomized computation, alternation and interactive proof systems are explained.

[Schedule]
1. Introduction
2. Complexity Classes, Cook's Theorem
3. NP-complete Problems
4. Co-NP and PSPACE
5. Randomized Computation
6. Alternation
7. Interactive Proof Systems
8. Summary and Exercise

履修条件・関連する科目
Course Prerequisites and Related Courses

数理情報学専攻所属の学生は受講できない。（同専攻の学生さんは「計算量理論特論1.2」を受講してください。）

成績評価の方法と基準
Course Evaluation Method and Criteria

演習課題の評価２０％，試験８０％，合計１００点満点で６０点以上を合格とする。

Examination 80% and assignment 30%. Credit is given if the total score >= 60%.

教科書・参考書
Textbook/Reference book

主にスライドを用いるが，定理等の詳細な証明および練習問題を加えた講義録も配布する。
教科書は指定しない。テキスト類を授業中に配布する。
参考文献：
（参考書）
1. J.E.Hopcroft, R.Motwani and J.D.Ullman: Introduction to Automata Theory, Languages, and Computation (second edition), Addison-Wesley, 2001.
2. M.R.Garey and D.S.Johnson: Computers and Intractability - A Guide to the Theory of NP-Completeness, W.H.Freeman and Company, 1979.
3. M. Sipser: Introduction to the Theory of Computation, PWS Publishing, 1997.
4. C.H.Papadimitriou: Computational Complexity, Addison-Wesley, 1994.
5. J.L.Balcazar, J.Diaz and J.Gabarro: Structural Complexity I, Springer, 1988.
J1. 岩間一雄：オートマトン・言語と計算理論，コロナ社，2003。
J2. 丸岡章：計算理論とオートマトン言語理論，サイエンス社, 2005。
J3. 渡辺治：計算可能性・計算複雑さ入門，近代科学社，1992。

No specific textbook is used. Slides are mainly used in a class. Handouts including formal proofs and exercises will be delivered.

References
1. J.E.Hopcroft, R.Motwani and J.D.Ullman: Introduction to Automata Theory, Languages, and Computation (second edition), Addison-Wesley, 2001.
2. M.R.Garey and D.S.Johnson: Computers and Intractability - A Guide to the Theory of NP-Completeness, W.H.Freeman and Company, 1979.
3. M. Sipser: Introduction to the Theory of Computation, PWS Publishing, 1997.
4. C.H.Papadimitriou: Computational Complexity, Addison-Wesley, 1994.
5. J.L.Balcazar, J.Diaz and J.Gabarro: Structural Complexity I, Springer, 1988.
(To be announced in the class.)

課外学習等（授業時間外学習の指示）
Study Load(Self-directed Learning Outside Course Hours)

講義において説明した理論を理解するために課題を与える。

Assignments will be given.

授業開講形態等
Lecture format, etc.

遠隔授業（オンデマンド型）で行う場合の追加措置
Additional measures for remote class (on-demand class)