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