Theory of Computation in Nomi

平成19年度2-1期・I222 計算の理論(Theory of Computation)

本ページは平成19年度2-1期(10月4日(木)～11月30日(金))にJAISTの石川キャンパスで開講されている『I222 計算の理論(Theory of Computation)』の授業のページです．担当は上原隆平です．

基本情報

教室での授業を録画したビデオ(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/5(Fri):(1)計算の基本要素(Elements of Computation) (Original size; 1/6 size)
10/9(Tue):(2)計算不可能性の証明と対角線論法(Proof of Unsolvability and Diagonalization Method) (Original size; 1/6 size)
10/12(Fri):(3)計算不可能な関数の例(Examples of Uncomputable Functions) (Original size; 1/6 size)
10/16(Tue):(4)枚挙可能集合(Enumerable Set) (Original size; 1/6 size)
10/19(Fri):(5)クラスRECとクラスRE(Class REC and Class RE) (Original size; 1/6 size)
10/23(Tue):(6)還元可能性と完全性(Reducibility and Completeness) (Original size; 1/6 size)
10/26(Fri):(7)計算時間の計り方(Measure of Computation Time) (Original size; 1/6 size)
11/2(Fri):(8)階層定理(Hierarchy Theorem) (Original size; 1/6 size)
11/6(Tue):(9)代表的な時間計算量クラス(Representative Time Complexity Classes) (Original size; 1/6 size)
11/9(Fri):(10)クラスNP(Class NP) (Original size; 1/6 size)
11/13(Tue):(11)時間量クラス間の関係(Relations among Time Complexity Classes) (Original size; 1/6 size)
11/13(Tue)&11/20(Tue):(12)多項式時間還元可能性(Polynomial-time Reducibility) (Original size; 1/6 size)
11/27(Tue):(13)多項式時間還元可能性にもとづく完全性(Completeness Based on Polynomial-time Reducibility) (Original size; 1/6 size)

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

10/5(Fri):配布資料のPDFファイル(Handout) (Japanese/ English)
10/9(Tue): PDF file of the report 1 (Deadline: 10/12(Fri))
10/16(Tue): PDF file of the report 2 (Deadline: 10/19(Fri))
10/23(Tue): PDF file of the report 3 (Deadline: 10/26(Fri))
11/2(Fri): PDF file of the report 4 (Deadline: 11/16(Fri))
11/9(Fri): PDF file of the report 5 (Deadline: 11/19(Mon))
11/20(Tue): PDF file of the report 6 (Deadline: 11/30(Fri))

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

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

休講情報(Schedules for cancelations)

[New]11月16日(金曜日)は，就職説明会のため出席できる学生が少ないということなので，休講にします．あちこちかわっているので，注意して下さい．特に期末試験が11月30日になりました． (The class on November 16th is canceled since many stundents will attend some kind of pre-job interview. Check that there are several changes. Especially, the final exam is postponed to November 30th.)

その他(Misc.)

[New]期末試験は11/30(Fri)です．(Final examination will be placed on November 30th.)
レポート(4),(5)の解答と解説は，オフィスアワーではなく，授業の中で行ないます． (Comments on reports (4) and (5) will be presented in some class, not office hour.)
[New]レポート(5)の提出期限を11月19日に伸ばしました．(Deadline of the report (5) is postponed to November 19th.)
レポート(4)の提出期限を11月16日に伸ばしました．(Deadline of the report (4) is postponed to November 16th.)
~~期末試験は11/27(Tue)です．(Final examination will be placed on November 27th.)~~
中間試験は10/30(Tue)です．(Mid-term examination will be placed on October 30th.)
10/1: ページ公開．

Last modified: Fri Nov 30 15:59:05 JST 2007
by R.Uehara (uehara@jaist.ac.jp)