令和7年度2-1期・I238 計算論 (I238: Computation Theory)
This is a support page of I238: Computation Theory (I238 計算論) at JAIST since October 10, 2025.
This page is maintained by Ryuhei Uehara.
サポート情報(Information)
- 基本情報
-
- 教室(Classroom)：大講義室
- 講義時間(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):
「計算可能性・計算の複雑さ入門」渡辺治著，近代科学社
- TA:阿慈地惇人(2410004)
- 講義に関する注意点
-
- 講義予定(Schedule)
- 講義の進行によって日程が変わることがあるので注意すること．
- 10月10日(金): 01. 計算の基本要素(Elements of Computation)
- 10月15日(水): 02. 集合の基礎(Introduction to set theory)
- 10月17日(金): 出張のため，休講
- 10月22日(水): 03. 対角線論法(Diagonalization)
- 10月24日(金): 04. 計算可能性と枚挙可能性(Computability and enumerability)
- 10月29日(水): 05. 還元性と完全性定理 (Reducibility and complementation theorem)
- 10月31日(金): 06. 計算量クラス(Computational classes)
- 11月05日(水): 中間試験
- 11月07日(金): 07. グラフ理論入門（無向グラフ，有向グラフ，多重グラフ，木構造、平面グラフ）(Introduction to graph theory)
- 11月12日(水): 08. グラフ上の問題とアルゴリズム（探索問題：オイラー閉路、最小全域木など）(Graph algorithms)
- 11月14日(金): 09. クラスNP(Class NP)
- 11月19日(水): 10. 計算量クラス間の関係(Relationship between computational classes)
- 11月21日(金): 11. 多項式時間還元可能性(Polynomial time reduction)
- 11月26日(水): 12. 多項式時間還元可能性にもとづく完全性（頂点被覆問題，ハミルトン路など）(Completeness under polynomial time reduction)
- 11月28日(金): 学務上の調整で講義なし．
- 12月01日(金): 13. 最近の計算量の話題より(Recent topics on Computional Complexity)
- 12月03日(水): 期末試験(Final Examination)
- レポートと試験について
-
- ほぼ毎回，理解度を測るための小テストを実施します．これは上原が理解度を確認するためで，成績には無関係です．
- 前半で1回，後半で1回，レポートを出題します．提出期限は2週間後で，
PDFフォーマットでJAIST-LMSを使って提出してください．
配点は10点ずつ．
- 11月05日に中間試験，12月03日に期末試験を実施します．それぞれ40点満点です．
石川での実施方法は「A4用紙1枚のみ持ち込み可として，試験と一緒に回収し，それも採点対象とする」とします．
詳細は別途講義の中でアナウンスしてJAIST-LMSにも掲載します．
品川での実施方法は個別に連絡します．
- レポートや試験の解説は，動画を作ってJAIST-LMSに掲載します．
不明点などあった場合は，TAの阿慈地君か上原まで個別に質問ください．
- その他のPDFファイル
-
講義に伴って必要となるファイルはJAIST-LMSを使って配布します．
(Files used in class rooms will be distributed through JAIST-LMS.)
- その他(Misc)
-
- 2022年10月08日: ページ公開．(This page is available on the Web.)
Last modified: Tue Oct 05 17:51:00 JST 2022
by R.Uehara (uehara@jaist.ac.jp)
| 
|