学部・大学院区分情報・博前
時間割コード2550049
科目区分
主専攻科目
科目名　【日本語】ソフトウェア基礎論特論A
科目名　【英語】
コースナンバリングコードGSI156041J
担当教員　【日本語】関　浩之 ○
担当教員　【英語】SEKI Hiroyuki ○
単位数1
開講期・開講時間帯秋１期 月曜日 ３時限
Fall1 Mon 3
対象学年１年
1
授業形態
開講系（学部）・開講専攻（大学院）
情報システム学専攻
必修・選択


授業の目的　【日本語】
問題の難しさをはかる尺度として，特に重要な考え方であるNP完全性等について説明する。まず，時間計算量と領域計算量等の概念を定義した後，NP完全性を定義する。次に，問題の難しさを相対化する技法である還元法を用いてNP完全性を証明する方法を具体例に即して説明する。さらに，クラスco-NPとPSPACE，ランダム計算，交代計算，対話証明系についても説明する。
授業の目的　【英語】
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.
到達目標　【日本語】
計算機で問題を解くときの問題の難しさを計る尺度についての体系である計算複雑さの理論の基本概念と方法論を修得する。NP完全性の還元法による証明技法を例題を通して身につける。PSPACE，BPP, IP等，その他の計算量クラスとそれらの相互関係を理解する。
到達目標　【英語】
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.
授業の内容や構成
問題の難しさをはかる尺度として，特に重要な考え方であるNP完全性等について説明する。まず，時間計算量と領域計算量等の概念を定義した後，NP完全性を定義する。次に，問題の難しさを相対化する技法である還元法を用いてNP完全性を証明する方法を具体例に即して説明する。さらに，クラスco-NPとPSPACE，ランダム計算，交代計算，対話証明系についても説明する。
〔計画〕
1. 導入
2. 計算量クラス
3. NP完全問題
4. co-NPとPSPACE
5. ランダム計算
6. 交代計算
7. 対話証明系
8. 総括と演習
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
3. NP-complete Problems
4. Co-NP and PSPACE
5. Randomized Computation
6. Alternation
7. Interactive Proof Systems
8. Summary and Exercise
履修条件・関連する科目
成績評価の方法と基準
演習課題の評価２０％，試験８０％，合計１００点満点で６０点以上を合格とする。
Examination 80% and assignment 30%. Credit is given if the total score >= 60%.
教科書・参考書
主にスライドを用いるが，定理等の詳細な証明および練習問題を加えた講義録も配布する。
教科書は指定しない。テキスト類を授業中に配布する。
参考文献：
（関担当分参考書）
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.)
課外学習等（授業時間外学習の指示）
講義において説明した理論を理解するために課題を与える。
Assignments will be given.
授業開講形態等
遠隔授業（オンデマンド型）で行う場合の追加措置