平成30年度1-1期・I238 計算論 (I238: Computation Theory)

This is a support page of I238: Computation Theory (I238 計算論) at JAIST, Ishikawa from April 12 to May 31. This page is maintained by Ryuhei Uehara.

サポート情報(Information)

基本情報

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

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

講義の進行によって日程が変わることがあるので注意すること 中間試験は5月10日のチュートリアルアワーに大講義室で実施しました． 期末試験は5月31日のチュートリアルアワーにI1講義室で実施します。

• 4月12日(木)：休講
• 4月17日(火)：休講
• 4月19日(木): 01. 計算の基本要素(Elements of Computation)
• 4月19日(木,TH): 居室にて質問受け付け
• 4月24日(火): 02. 集合の基礎(Introduction to set theory)
• 4月26日(木): 03. 対角線論法(Diagonalization)
• 4月26日(木,TH): 居室にて質問受け付け
• 5月01日(火): 04. 計算可能性と枚挙可能性(Computability and enumerability)
• 5月08日(火): 05. 還元性とComplementation Theorem (Reducibility and complementation theorem)
• 5月10日(木): 06. 計算可能性に関するまとめ（Recent topics of computability）
• 5月10日(木,TH), 中間試験(大講義室で実施します)
• 5月15日(火): 07. グラフ理論入門（無向グラフ，有向グラフ，多重グラフ，木構造、平面グラフ） (Introduction to graph theory) [Last Updated: 2018/05/17]
• 5月17日(木): 08. 計算量クラス(Computational classes)
• 5月17日(木,TH): 会議のため不在
• 5月22日(火): 09. クラスNP(Class NP)
• 5月24日(木): 10. 計算量クラス間の関係(Relationship between computational classes)
• 5月24日(木,TH): 11. 多項式時間還元可能性(Polynomial time reducibility)
• 5月29日(火): 12. 多項式時間還元可能性(Polynomial time reducibility)（続き）
• 5月31日(木): 13. 多項式時間還元可能性にもとづく完全性（頂点被覆問題，ハミルトン路など）(Completeness under polynomial time reduction)
• 5月31日(木,TH): 14. まとめと期末試験(I1講義室で実施します)
• 6月05日(火)：不在

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

• 5月22日(火): レポート2(Report2) 締切：5月29日10:50am.(Deadline：May 29, 10:50am.)
• 4月26日(木): レポート1(Report1) 締切：5月8日10:50am.(Deadline：May 8, 10:50am.)
• 4月19日(木): 配布資料(handout)

その他(Misc)

• 2018年05月31日: チュートリアルアワーに，I1講義室で期末試験をやります．
• 2018年05月10日: チュートリアルアワーに，大講義室で中間試験をやります．
• 2018年04月18日: ページ公開．(This page is available on the Web.)

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