平成31年(令和元年)度1-1期・I238 計算論 (I238: Computation Theory)

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

サポート情報(Information)

基本情報

• 教室(Classroom)：I3・4講義室
• 講義時間(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)

講義の進行によって日程が変わることがあるので注意すること 期末試験は6月の試験期間中(11日)に実施します。 (The final examination will be done on June 11.)

• 4月16日(火): 01. 計算の基本要素(Elements of Computation)
• 4月18日(木): 02. 集合の基礎(Introduction to set theory)(前回の続きなのでスライドは同じ)
• 4月18日(木,TH): 居室にて質問受け付け(時間によっては会議で不在かもしれません)
• 4月23日(火): 休講
• 4月25日(木): 03. 対角線論法(Diagonalization)
• 4月25日(木,TH): 居室にて質問受け付け(時間によっては会議で不在かもしれません)
• 5月07日(火): 04. 計算可能性と枚挙可能性(Computability and enumerability)
• 5月09日(木): 05. 還元性とComplementation Theorem (Reducibility and complementation theorem)
• 5月09日(木,TH): 計算可能性に関するまとめ（Recent topics of computability）
• 5月14日(火): 中間試験(I3・4講義室で実施します)
• 5月16日(木): 06. 計算量クラス(Computational classes)
• 5月16日(木,TH): 07. グラフ理論超入門（無向グラフ，有向グラフ，多重グラフ，木構造、平面グラフ） (Very introduction to graph theory)
• 5月21日(火): 08. 計算量クラスとグラフ理論超入門の続き
• 5月23日(木): 09. クラスNP(Class NP)
• 5月23日(木,TH): 10. 計算量クラス間の関係(Relationship between computational classes)
• 5月28日(火): 休講
• 5月30日(木): 休講
• 6月04日(火): 12. 多項式時間還元可能性にもとづく完全性（頂点被覆問題，ハミルトン路など）(Completeness under polynomial time reduction)
• 6月06日(木): 13. 最近の計算量の話題より(Recent topics on Computional Complexity) Slides 1, Slides 2
• 6月06日(木,HT): 14. まとめと質問受け付けなど
• 6月11日(火): 期末試験

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

• 5月23日(木): レポート2(Report2) 締切：6月04日(火)10:50am.(Deadline：June 04, 10:50am.)
• 5月07日(火): レポート1(Report1) 締切：5月14日(火)10:50am.(Deadline：May 14, 10:50am.)
• 4月16日(火): 配布資料(handout)

その他(Misc)

• 2018年04月15日: ページ公開．(This page is available on the Web.)

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