令和6年度2-1期・I238 計算論 (I238: Computation Theory)
This is a support page of I238: Computation Theory (I238 計算論) at JAIST since October 10, 2024.
This page is maintained by Ryuhei Uehara.
サポート情報(Information)
- 基本情報
-
- 教室(Classroom)：I3・4講義室
- 講義時間(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)
- 講義の進行によって日程が変わることがあるので注意すること．
- 10月10日(木): 01. 計算の基本要素(Elements of Computation)
- 10月15日(火): 02. 集合の基礎(Introduction to set theory)
- 10月17日(木): 03. 対角線論法(Diagonalization)
- 10月22日(火): 休講
- 10月24日(木): 04. 計算可能性と枚挙可能性(Computability and enumerability)
- 10月29日(火): 05. 還元性と完全性定理 (Reducibility and complementation theorem)
- (10月31日(木): 月曜日の時間割)
- 11月05日(火): 06. 計算量クラス(Computational classes)
- 11月07日(木): 08. グラフ理論入門（無向グラフ，有向グラフ，多重グラフ，木構造、平面グラフ）(Introduction to graph theory)
- 11月07日(木)のチュートリアル・アワー: 07. 中間試験とこれまでのまとめ
- 11月12日(火): 09. グラフ上の問題とアルゴリズム（探索問題：オイラー閉路、最小全域木など）(Graph algorithms)
- 11月14日(木): 10. クラスNP(Class NP)
- 11月14日(木)のチュートリアル・アワー: 11. 計算量クラス間の関係(Relationship between computational classes)
- 11月19日(火): 休講
- 11月21日(木): 12. 多項式時間還元可能性(Polynomial time reduction)
- 11月26日(火): 13. 多項式時間還元可能性にもとづく完全性（頂点被覆問題，ハミルトン路など）(Completeness under polynomial time reduction)
- 11月28日(木): 14. 最近の計算量の話題より(Recent topics on Computional Complexity)
- 12月03日(火): 期末試験(Final Examination)
- レポートと試験について
-
- ほぼ毎回，理解度を測るための小テストを実施します．これは上原が理解度を確認するためで，成績には無関係です．
- ほぼ毎回，10点満点（あるいは20点満点）のミニレポートを出題します．提出期限は1週間後で，
PDFフォーマットでJAIST-LMSを使って提出して下さい．
最終的に良い方から100点満点分採用して100点満点の「レポート点」を出します．
- 11月07日の中間試験と12月03日の期末試験を100点満点になるように実施します．
実施方法は，別途講義の中でアナウンスして
JAIST-LMSにも掲載します．
- レポート点と試験の点の良い方を採用して成績をつけます．
- レポートや試験の解答やコメントは，上原がビデオ録画して
JAIST-LMSに適宜公開します．
- 品川で試験を受けたい受講生は個別に連絡してください．上原が東京に行って実施します．
- チュートリアルアワーについて
- 基本的には上原は居室(情報III棟6階)にいるので，気軽に質問に来てください．
急な出張や講義の進度によっては補講をすることもあるので，
JAIST-LMSのアナウンスを確認のこと．
- その他のPDFファイル
-
講義に伴って必要となるファイルはJAIST-LMSを使って配布します．
(Files used in class rooms will be distributed through JAIST-LMS.)
- その他(Misc)
-
- 2024年10月06日: ページ公開．(This page is available on the Web.)
Last modified: Tue Oct 10 10:46:00 JST 2023
by R.Uehara (uehara@jaist.ac.jp)
| 
|