平成25年度III期・I216 計算量の理論と離散数学(I216: Computational Complexity and Discrete Mathematics)

このページは品川キャンパスで開講されているI216 計算量の理論と離散数学のサポートページです． 前半は上原隆平が担当して， 後半は宮地充子教授が担当します． このページは上原隆平が管理していて，前半部分の情報しかありません．

サポート情報(Information)

• シラバス| Syllabus
• 教室(Classroom):
• テキスト(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 on JAIST local network.) 視聴方法(How to see)| ログイン(Login)

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

• 11/02(Sat):(1) 計算の基本要素 (Elements of Computation)
• 11/02(Sat):(2) 計算不可能性の証明と対角線論法 (Proof of Unsolvability and Diagonalization Method)
• 11/16(Sat):(3) 時間量クラス間の関係(Relations among Time Complexity Classes)
• 11/16(Sat):(4) クラスNP(Class NP)
• 11/23(Sat):(5) 多項式時間還元可能性(Polynomial-time Reducibility)
• 11/23(Sat):(6) 多項式時間還元可能性にもとづく完全性(Completeness Based on Polynomial-time Reducibility)
• 12/30(Wed): 中間試験(Mid-term Examination)

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

• 11/02(Sat): 配布資料(handout) (中に13:30amという記述がありますが，13:30pmの間違いです．)
• 11/02(Sat): レポート1(report 1)
• 11/16(Sat): レポート2(report 2)
• 11/23(Sat): レポート1の解答と解説(Answers and Comments on Reports)
• 11/23(Sat): レポート2の解答と解説(Answers and Comments on Reports)
• 12/21(Sat): 中間試験の解答と解説(Answers and Comments on the Exam)

その他(Misc)

• 中間試験は12月21日(土)です．(The mid-term examination will be placed on December 21st.)
• 2013/10/29: ページ公開．(This page is available on the Web.)

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