学部・大学院区分
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		1
開講期・開講時間帯
Term / Day / Period		秋１期 月曜日 ３時限
Fall1 Mon 3
対象学年
Year		１年
1
授業形態
Course style
開講系（学部）・開講専攻（大学院）
Subject
情報システム学専攻
必修・選択
Required / Selected


授業の目的　【日本語】
Goals of the Course(JPN)
計算機で問題を解くときの問題の難しさを計る尺度である計算複雑さについて，その基本概念と方法論を修得することを目的とする。
授業の目的　【英語】
Goals of the Course
Computational complexity theory provides mathematical concepts and tools for representing the computational hardness of problems. The aim of this course is to provide basic definitions and methodologies of the theory such as NP-completeness.
到達目標　【日本語】
Objectives of the Course(JPN)
問題の難しさをはかる尺度として，特に重要な考え方であるNP完全性等について理解する。まず，時間計算量と領域計算量等の概念，ついでNP完全性の定義を理解する。次に，問題の難しさを相対化する技法である還元法を用いてNP完全性を証明する方法を，例題を通して身につける。後半では，クラスco-NP，PSPACE，ランダム計算，交代計算，対話証明系等，その他の計算量クラスとそれらの相互関係を理解する。
到達目標　【英語】
Objectives of the Course
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 the hardness of given two problems and is useful for proving that a problem is NP-complete. Then, the classes co-NP and PSPACE are explained. In the latter part, other important computation models including randomized computation, alternation and interactive proof systems are explained.
授業の内容や構成
Course Content / Plan
計算複雑さについて，以下の授業計画に沿って学ぶ。
〔計画〕
1. 導入
2. 計算量クラス・Cookの定理
3. 様々なNP完全問題
4. co-NPとPSPACE
5. ランダム計算
6. 交代計算
7. 対話証明系
8. 総括と演習
[Course 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
成績評価の方法と基準
Course Evaluation Method and Criteria
演習課題の評価２０％，試験８０％，合計１００点満点で６０点以上を合格とする。
Examination 80% and assignment 20%. 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)