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

This is a support page of I216: Computational Complexity and Discrete Mathematics (I216 計算量の理論と離散数学) at JAIST, Ishikawa from Octber 4 to December 2. The lecturers in the former half is by Ryuhei Uehara, and the ones in the latter half is by Prof. Kazumasa Omote. This page is maintained by Ryuhei Uehara, and it contains information of the former half.

サポート情報(Information)

• シラバス| Syllabus
• 教室(Classroom): I3・4
• 講義時間(Lectures): 水曜日(Wednesdays)9:20〜10:50, 金曜日(Fridays)11:00〜12:30.
• オフィスアワー(Office Hour): 木曜日(Wednesdays)3時限13:30〜15:00.
• テキスト(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)

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

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

• 10/09(Wed): 配布資料(handout)
• 10/11(Fri): レポート1(report 1)
• 10/16(Wed): レポート1の解答と解説(Answers and Comments on Report 1)
• 10/18(Fri): レポート2(report 2)
• 10/23(Wed): レポート2の解答と解説(Answers and Comments on Report 2)
• 10/30(Wed): 中間試験の解答と解説(Answers and Comments on the Exam)

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

• 10/09(Wed): 居室にて質問受付(Ask me if you have any questions/comments/etc. at my lab.)
• 10/16(Wed): レポート1の解答と解説(Answers and Comments on Report 1)
• 10/23(Wed): レポート2の解答と解説(Answers and Comments on Report 2)
• 10/30(Wed): 中間試験の解答と解説(Answers and Comments on the mid-term exam)

その他(Misc)

• 2013/10/30:中間試験の採点終わりました．平均点は37.8/50点です．成績が知りたい人は個別に email で聞いて下さい． 学生番号を必ず明記して聞いて下さい．
• 中間試験は10月30日(水)です．(The mid-term examination will be placed on October 30th.)
• 2013/10/7: ページ公開．(This page is available on the Web.)

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