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

This is a support page of I238: Computation Theory (I238 計算論) at JAIST since October 11, 2023. This page is maintained by Ryuhei Uehara.

サポート情報(Information)

基本情報

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

講義に関する注意点

• 必ずJAIST-LMSで最新情報を確認して下さい．
• 講義に伴って必要となるファイルはJAIST-LMSを使って配布します．

講義予定(Schedule)

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

• 10月11日(水): 01. 計算の基本要素(Elements of Computation)
• 10月13日(金): 02. 集合の基礎(Introduction to set theory)
• 10月18日(水): 03. 対角線論法(Diagonalization)
• 10月20日(金): 04. 計算可能性と枚挙可能性(Computability and enumerability)
• 10月25日(水): 05. 還元性と完全性定理 (Reducibility and complementation theorem)
• 10月27日(金): 06. 計算量クラス(Computational classes)
• 11月01日(水): 07. 中間試験とこれまでのまとめ
• 11月08日(水): 08. グラフ理論入門（無向グラフ，有向グラフ，多重グラフ，木構造、平面グラフ）(Introduction to graph theory)
• 11月10日(金): 09. グラフ上の問題とアルゴリズム（探索問題：オイラー閉路、最小全域木など）(Graph algorithms)
• 11月15日(水): 10. クラスNP(Class NP)
• 11月17日(金): 休講
• 11月22日(水): 11. 計算量クラス間の関係(Relationship between computational classes)
• 11月24日(金): 12. 多項式時間還元可能性(Polynomial time reduction)
• 11月29日(水): 13. 多項式時間還元可能性にもとづく完全性（頂点被覆問題，ハミルトン路など）(Completeness under polynomial time reduction) 金曜時間割で実施
• 12月01日(金): 14. 最近の計算量の話題より(Recent topics on Computional Complexity)
• 12月04日(月)の13:30-15:10: 期末試験(Final Examination)

レポートと試験について

• ほぼ毎回，理解度を測るための小テストを実施します．これは上原が理解度を確認するためで，成績には無関係です．
• ほぼ毎回，10点満点（あるいは20点満点）のミニレポートを出題します．提出期限は1週間後で， PDFフォーマットでJAIST-LMSを使って送って下さい． 最終的に良い方から100点満点分採用して100点満点の「レポート点」を出します．
• 10月27日の中間試験と12月04日の期末試験を100点満点になるように実施します． 実施方法は，別途講義の中でアナウンスして JAIST-LMSにも掲載します．
• レポート点と試験の点の良い方を採用して成績をつけます．
• レポートや試験の解答やコメントは，上原がビデオ録画して JAIST-LMSに適宜公開します．

チュートリアルアワーについて

基本的には上原は居室(情報III棟6階)にいるので，気軽に質問に来てください． 急な出張や講義の進度によっては補講をすることもあるので， JAIST-LMSのアナウンスを確認のこと．

その他のPDFファイル

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

その他(Misc)

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

Last modified: Tue Oct 10 10:46:00 JST 2023 by R.Uehara (uehara@jaist.ac.jp)