Computational Complexity and Discrete Mathematics

I216: Computational Complexity and Discrete Mathematics（平成22年度2-1期・I216 計算量の理論と離散数学）

This is a support page of "I216: Computational Complexity and Discrete Mathematics" (I216 計算量の理論と離散数学) at JAIST, Ishikawa from October 7 to December 3. The lecturer in the former half is Ryuhei Uehara, and the one in the latter half is Prof. Atsuko Miyaji. This page is maintained by Ryuhei Uehara, and it contains information of the former half.

Information (サポート情報)

Syllabus| シラバス
Classroom (教室): I-1
Lectures (講義時間): On Mondays, 11:00～12:30, and Thursdays 9:20～10:50.
Office Hour (オフィスアワー): Thursdays 13:30～15:00 (木曜日3時限).
Textbook (テキスト) in Japanese: 「計算可能性・計算の複雑さ入門」渡辺治著，近代科学社
References (参考図書): "Introduction to the Theory of Computation," Michael Sipser, PWS Publishing, 1997.
「計算理論の基礎」Michael Sipser著，太田和夫・田中圭介監訳，阿部正幸・植田広樹・藤岡淳・渡辺治訳，共立出版
全3冊組のうち，[2. 計算可能性の理論]と[3. 複雑さの理論]が本授業の領域をカバーしています．

Videos taken in the classroom (教室での授業を録画したビデオ)

It is available in JAIST, and you can see only when you use IE on Windows. (大学内のみ視聴可能で，Windows 上の IE のみ対応しているようです．) How to see(視聴方法)| Login(ログイン)

PDF files used in the lessons (授業で使用したPowerPointのPDFファイル)

10/ 7(Thu):(1) Elements of Computation (計算の基本要素) (Original size; 1/6 size)
10/14(Thu):(2) Proof of Unsolvability and Diagonalization Method (計算不可能性の証明と対角線論法) (Original size; 1/6 size)
10/18(Mon):(3) Relations among Time Complexity Classes (時間量クラス間の関係) (Original size; 1/6 size)
10/21(Thu):(4) Class NP (クラスNP) (Original size; 1/6 size)
10/25(Mon):(5) Polynomial-time Reducibility (多項式時間還元可能性) (Original size; 1/6 size)
10/28(Thu):(6) Completeness Based on Polynomial-time Reducibility (多項式時間還元可能性にもとづく完全性) (Original size; 1/6 size)

PDF files of the others (その他のPDFファイル)

10/7(Thu): PDF file of handout(配布資料)
10/18(Mon): PDF file of report(レポート)
10/28(Thu): PDF file of Answers and Comments on the report(レポートの解答と解説) by Nakanishi-kun

Schedules for Office Hours (オフィスアワーの予定)

10/14(Thu): Questions are welcome at I67b. (居室I67bにて質問受け付け)
10/21(Thu): Questions are welcome at I67b. (居室I67bにて質問受け付け)
10/28(Thu): Comments on the report. (レポートの解答と解説)

Misc. (その他)

A report will be distributed on October 18, and its deadline is October 27. (レポートは10月18日に配布します．締切は10月27日(月)です．)
The mid-term examination will be placed on November 1st. (中間試験は11月1日(月)です．)
2009/10/6: This page is available on the Web. (ページ公開．)

Last modified: Tue Oct 26 13:24:08 JST 2010
by R.Uehara (uehara@jaist.ac.jp)