Theory of Computation in Nomi

平成18年度2-1期・I222 計算の理論(Theory of Computation)@能美キャンパス

本ページは平成18年度2-1期(10月4日(水)～12月1日(金))にJAISTの石川キャンパスで開講されている『I222 計算の理論(Theory of Computation)』の授業のページです． 1-2期の東京田町キャンパスでの授業に関するページはこちらを御覧下さい．

基本情報

教室での授業を録画したビデオ(Videos taken in the classroom)

大学内のみ視聴可能で，Windows 上の IE のみ対応しているようです． (It is available in JAIST, and you can see only when you use IE on Windows) 視聴方法(How to see)| ログイン先(Login)

授業で使用したPowerPointのPDFファイル(PDF files used in the lessons)

10/4(Wed):(1)計算の基本要素(Elements of Computation) (Original size; 1/6 size)
10/6(Fri):(2)計算不可能性の証明と対角線論法(Proof of Unsolvability and Diagonalization Method) (Original size; 1/6 size)
10/11(Wed):(3)計算不可能な関数の例(Examples of Uncomputable Functions) (Original size; 1/6 size)
10/18(Wed):(4)枚挙可能集合(Enumerable Set) (Original size; 1/6 size)
10/20(Fri):(5)クラスRECとクラスRE(Class REC and Class RE) (Original size; 1/6 size)
10/25(Wed):(6)還元可能性と完全性(Reducibility and Completeness) (Original size; 1/6 size)
11/1(Wed):(7)計算時間の計り方(Measure of Computation Time) (Original size; 1/6 size)
11/8(Wed):(8)階層定理(Hierarchy Theorem) (Original size; 1/6 size)
11/10(Fri):(9)代表的な時間計算量クラス(Representative Time Complexity Classes) (Original size; 1/6 size)
11/15(Wed):(10)クラスNP(Class NP) (Original size; 1/6 size)
11/17(Fri): レポート4の補足説明(Supplementary Explanation of the 4th report) (Original size; 1/6 size)
11/17(Fri):(11)時間量クラス間の関係(Relations among Time Complexity Classes) (Original size; 1/6 size)
11/22(Wed):(12)多項式時間還元可能性(Polynomial-time Reducibility) (Original size; 1/6 size)
11/24(Fri):(13)多項式時間還元可能性にもとづく完全性(Completeness Based on Polynomial-time Reducibility) (Original size; 1/6 size)

授業で配布した資料やレポートのPDFファイル(PDF files for the handouts distributed in lessons)

10/4(Wed):配布資料のPDFファイル
10/6(Fri):レポート1のPDFファイル(締切は10/11(Wed)授業終了時)
[訂正] 問題2の「∃」と「∀」を逆にしてしまいました．授業のスライドで示した方が正解です．修正して答えるようにして下さい．ここで公開しているファイルは修正済です．すみません．
10/18(Wed):レポート2のPDFファイル(締切は10/25(Wed)授業終了時)
10/25(Wed):レポート3のPDFファイル(締切は11/1(Wed)授業終了時) The PDF file of the report 3 (Deadline: 11/1(Wed))
11/8(Wed):レポート4のPDFファイル(締切は11/15(Wed)授業終了時) The PDF file of the report 4 (Deadline: 11/15(Wed))
11/15(Wed):レポート5のPDFファイル(締切は11/22(Wed)授業終了時) The PDF file of the report 5 (Deadline: 11/22(Wed))
11/22(Wed):レポート6のPDFファイル(締切は11/29(Wed)試験終了時) The PDF file of the report 6 (Deadline: 11/29(Wed))

レポートの解説などで使ったPDFファイル(PDF files used for the solutions and comments on the reports)

10/11(Wed):レポート1の解答と解説(Answers and Comments for report (1))(PDFファイル)
10/25(Wed):レポート2の解答と解説(Answers and Comments for report (2))(PDFファイル)
11/1(Wed):レポート3の解答と解説(Answers and Comments for report (3))(PDFファイル)
11/1(Wed):中間試験の解答と解説(Answers and Comments for Mid-term Examination) (PDFファイル: Original size, 1/6 size)
11/15(Wed):レポート4の解答と解説(Answers and Comments for report (4))(PDF File)
11/22(Wed):レポート5の解答と解説(Answers and Comments for report (5))(PDF File)
11/29(Wed):レポート6の解答と解説(Answers and Comments for report (6))(PDFファイル)
11/29(Wed):期末試験の解答と解説(Answers and Comments for Final Examination) (PDFファイル: Original size, 1/6 size)

オフィスアワーの予定(Schedules for Office Hours)

休講情報(Schedules for cancelations)

10/13(Fri)は休講です． (On October 13th, the lecture will be canceled since Uehara will not be present.)

その他(Misc.)

[12/1] レポート6と期末試験の採点が終わりました．試験の答案は保存義務があるそうなので，期末試験の返却は中止します．すみません．でもレポート6の返却や採点結果を閲覧することは可能なので，興味のある人は訪ねて下さい． (I have finished the last report and the final exam. If you have any questions, ask me.)
[10/6] レポート1の問題2の「∃」と「∀」が逆でした．すみません．修正版を公開しました．
期末試験は11/29(Wed)です．(Final examination will be placed on November 29th.)
中間試験は10/27(Fri)です．(Mid-term examination will be placed on October 27th.)
10/2: ページを充実させました．

Last modified: Fri Dec 1 16:00:16 JST 2006
by R.Uehara (uehara@jaist.ac.jp)