令和2年度1-1期・I238 計算論 (I238: Computation Theory)

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

サポート情報(Information)

基本情報

• 教室(Classroom)：I2講義室
• 講義時間(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): 「計算可能性・計算の複雑さ入門」渡辺治著，近代科学社

オンライン講義に伴う注意点

初のオンライン講義のため、いろいろと試してみます。具体的には以下を計画しています。

• 講義に伴って必要となるファイルはLMSを使って配布してみます。 (Files used in class rooms will be distributed through LMS.)
• 期末試験は6月の試験期間中(9日)に実施します。実施方法は検討中です。 (The final examination will be done on June 9. The way of enforcement is under consideration.)
• 中間試験は実施せず、こまめなレポート提出で代替します。ほぼ毎回レポートを出す予定です。 目安としてはレポート合計50点、期末試験50点で成績をつける予定です。 詳細は講義とLMSにて。 (Mid-term examination is canceled. I will aks you small reports almost every class. Tentative plan is that reports make up to 50 points, and the final report makes up to 50 points.)
• 要望その他があれば、いつでも上原か、TAの鎌田君(kamata)にメールでいつでも気軽にお知らせ下さい。 (Please feel free to ask Uehara or Kamata-kun (kamata), TA, if you have any questions and comments by email.)

講義予定(Schedule)

講義の進行によって日程が変わることがあるので注意すること。

• 4月21日(火): 01. 計算の基本要素(Elements of Computation)
• 4月23日(木): 02. 集合の基礎(Introduction to set theory)
• 4月23日(木,TH): 03. 対角線論法(Diagonalization)
• 4月28日(火): 04. 計算可能性と枚挙可能性(Computability and enumerability)
• 4月30日(木): 水曜日の時間割(Courses on Wedgesday will be performed.)
• 5月07日(木): 05. 還元性と完全性定理 (Reducibility and complementation theorem)
• 5月07日(木,TH): 06. まとめと計算可能性に関する最新の話題(Survey and Recent Topics)
• 6月02日(火): 07. 計算量クラス(Computational classes)
• 5月12日(火): 08. グラフ理論入門（無向グラフ，有向グラフ，多重グラフ，木構造、平面グラフ）(Introduction to graph theory)
• 5月14日(木): 09. グラフ上の問題とアルゴリズム（探索問題：オイラー閉路、最小全域木など）(Graph algorithms)
• 5月14日(木,TH): チュートリアルアワー（研究室で質問受付）(Tutorial hour in laboratory)
• 5月19日(火): 10. クラスNP(Class NP)
• 5月21日(木): 11. 計算量クラス間の関係(Relationship between computational classes)
• 5月26日(火): 12. 多項式時間還元可能性(Polynomial time reduction)
• 5月28日(木): 13. 多項式時間還元可能性にもとづく完全性（頂点被覆問題，ハミルトン路など）(Completeness under polynomial time reduction)
• 6月02日(火): 14. 最近の計算量の話題より(Recent topics on Computional Complexity)
• 6月04日(木): 15. まとめと質問受け付けなど(Survey and others)
• 6月09日(火): 期末試験(Final Examination)

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

講義に伴って必要となるファイルはLMSを使って配布してみます。 (Files used in class rooms will be distributed through LMS.)

その他(Misc)

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

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