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

This is a support page of "I216E: Computational Complexity and Discrete Mathematics" (I216E 計算量の理論と離散数学) at JAIST, Ishikawa from April 8 to June 5. The lectures in the former half are given by Ryuhei Uehara, and the ones in the latter half are given by Prof. Atsuko Miyaji. This page is maintained by Ryuhei Uehara, and it contains information of the former half.

Information (サポート情報)

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

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(ログイン)

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

• 4/13(Mon):(1) Elements of Computation (計算の基本要素)
• 4/16(Thu):(2) Proof of Unsolvability and Diagonalization Method (計算不能性の証明と対角線論法)
• 4/20(Mon):(3) Relations among Time Complexity Classes (時間量クラス間の関係)
• 4/23(Thu):(4) Class NP (クラスNP)
• 4/27(Mon):(5) Polynomial-time Reducibility (多項式時間還元可能性)
• 4/30(Thu):(By Prof. Miyaji) (宮地先生の講義(1))
• 5/07(Thu):(6) Completeness Based on Polynomial-time Reducibility (多項式時間還元可能性にもとづく完全性)
• 5/11(Mon):(7) Recent Topics of Computational Complexity (計算量の理論の最新トピック)
• 5/14(Thu):(By Prof. Miyaji) (宮地先生の講義(2))
• 5/18(Mon): Review and Mid-term Examination

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

• 4/13(Mon): PDF file of handout(配布資料)
• 4/16(Thu): PDF file of report 1 (レポート1)
• 4/23(Thu): PDF file of the answer and comments on report 1 (レポート1の解答とコメント)(by Duc)
• 5/07(Thu): PDF file of report 2 (レポート2)
• 5/11(Mon): PDF file of the answer and comments on report 2 (レポート2の解答とコメント)

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

• 4/16(Thu): Ask me if you have any questions/comments/etc.
• 4/23(Thu): Answers and Comments on Report 1. (レポート1の解答と解説)
• 4/30(Thu): On Business trip...
• 5/07(Thu): Ask me if you have any questions/comments/etc.
• 5/14(Thu): Ask me if you have any questions/comments/etc.

Misc. (その他)

• The deadline of the first report is extended from April 20 to April 23.
• The mid-term examination will be placed on May 18th. (中間試験は5月18日(月)です．)
• 2015/04/12: This page is available on the Web. (ページ公開．)

Last modified: Sun May 10 22:20:00 JST 2015 by R.Uehara (uehara@jaist.ac.jp)