情報科学特別研究Ⅰ

科目名	情報科学特別研究Ⅰ
教員名	谷聖一
単位数	4	課程	前期課程	開講区分	文理学部
学期	通年	履修区分	必修

授業概要	計算可能性理論・計算の複雑さの理論・アルゴリズム理論の基礎を概観する。
授業のねらい・到達目標	計算可能性理論・計算の複雑さの理論・アルゴリズム理論の基本的な概念を理解し、それを計算論的位相幾何学における問題解決に応用できるようになる。この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応している。
授業の方法	受講者全員参加による輪講と議論を繰り返す。本授業の事前・後学習は、各４時間の学習を目安とする。

授業計画
1	アルゴリズムの定義・性能評価に関する導入【事前学習】アルゴリズムの定義・性能評価に基本概念を事前に確認する【事後学習】第2回以降の学習計画を定める
2	計算モデルと計算可能性：自然数【事前学習】自然数の定義及び基本性質を事前に確認する【事後学習】自然数に関する議論で生じた課題を検討する
3	計算モデルと計算可能性：帰納的関数【事前学習】帰納的関数の定義及び基本性質を事前に確認する【事後学習】帰納的関数に関する議論で生じた課題を検討する
4	計算モデルと計算可能性：ゲーデル数【事前学習】ゲーデル定義及び基本性質を事前に確認する【事後学習】ゲーデル数に関する議論で生じた課題を検討する
5	計算モデルと計算可能性：λ-定義可能関数【事前学習】λ-定義可能関数の定義及び基本性質を事前に確認する【事後学習】λ-定義可能関数に関する議論で生じた課題を検討する
6	計算モデルと計算可能性：チューリング機械【事前学習】チューリング機械の定義及び基本性質を事前に確認する【事後学習】チューリング機会に関する議論で生じた課題を検討する
7	計算モデルと計算可能性：Church-Turingの提唱【事前学習】Church-Turingの提唱の内容について事前に確認する【事後学習】Church-Turingの提唱に関する議論で生じた課題を検討する
8	計算モデルと計算可能性：ランダムアクセス機械【事前学習】ランダムアクセス機械　の定義及び基本性質を事前に確認する【事後学習】ランダムアクセス機械に関する議論で生じた課題を検討する
9	計算可能でない問題：様々なチューリング機械【事前学習】様々なチューリング機械の内容について事前に確認する【事後学習】様々なチューリング機械に関する議論で生じた課題を検討する
10	計算可能でない問題：帰納的に可算な問題と計算可能な問題【事前学習】帰納的に可算な問題と計算可能な問題に関する発表の準備を事前に行う【事後学習】帰納的に可算な問題と計算可能な問題に関する議論で生じた課題を検討する
11	計算可能でない問題：計算可能でない問題【事前学習】計算可能でない問題に関する発表の準備を事前に行う【事後学習】計算可能でない問題に関する議論で生じた課題を検討する
12	計算可能でない問題：帰着と決定不能問題【事前学習】帰着と決定不能問題に関する発表の準備を事前に行う【事後学習】帰着と決定不能問題に関する議論で生じた課題を検討する
13	計算量クラスと基本定理：計算量【事前学習】計算量に関する発表の準備を事前に行う【事後学習】計算量に関する議論で生じた課題を検討する
14	計算量クラスと基本定理：計算量の基本性質【事前学習】計算量の基本性質に関する発表の準備を事前に行う【事後学習】計算量の基本性質に関する議論で生じた課題を検討する
15	計算量クラスと基本定理：オーダ記法【事前学習】オーダ記法の定義や基本性質を事前に確認する【事後学習】オード記法の性質を理解するのに適切な練習問題を作成する
16	計算量クラスと基本定理：構成可能性と階層定理【事前学習】構成可能性と階層定理に関する発表の準備を事前に行う【事後学習】構成可能性と階層定理に関する議論で生じた課題を検討する
17	計算量クラスPとNP：クラスP 【事前学習】クラスPの定義及び基本性質を事前に確認する【事後学習】クラスPに関する議論で生じた課題を検討する
18	計算量クラスPとNP：クラスNP 【事前学習】クラスNPの定義及び基本性質を事前に確認する【事後学習】クラスNPに関する議論で生じた課題を検討する
19	計算量クラスPとNP：多項式時間版の帰着と困難性・完全性【事前学習】多項式時間版の帰着と困難性・完全性に関する発表の準備を事前に行う【事後学習】多項式時間版の帰着と困難性・完全性に関する議論で生じた課題を検討する
20	計算量クラスPとNP：NP-完全問題【事前学習】NP-完全問題に関する発表の準備を事前に行う【事後学習】NP-完全問題に関する議論で生じた課題を検討する
21	計算量クラスPとNP：Cook-Levinの定理の証明【事前学習】Cook-Levinの定理の証明に関する発表の準備を事前に行う【事後学習】Cook-Levinの定理の証明に関する議論で生じた課題を検討する
22	計算量クラスPとNP：様々なNP-完全問題【事前学習】様々なNP-完全問題に関する発表の準備を事前に行う【事後学習】様々なNP-完全問題に関する議論で生じた課題を検討する
23	基本な計算量クラスとそれらの関係：基本的な計算量クラス【事前学習】基本的な計算量クラスに関する発表の準備を事前に行う【事後学習】基本的な計算量クラスに関する議論で生じた課題を検討する
24	基本な計算量クラスとそれらの関係：補集合の計算量クラスと Immerman-Szelepc ́enyi の定理【事前学習】補集合の計算量クラスと Immerman-Szelepc ́enyi の定理に関する発表の準備を事前に行う【事後学習】補集合の計算量クラスと Immerman-Szelepc ́enyi の定理に関する議論で生じた課題を検討する
25	基本な計算量クラスとそれらの関係：基本的な計算量クラスに対する完全性【事前学習】基本的な計算量クラスに対する完全性に関する発表の準備を事前に行う【事後学習】基本的な計算量クラスに対する完全性に関する議論で生じた課題を検討する
26	基本な計算量クラスとそれらの関係：神託付チューリング機械・チューリング帰着【事前学習】神託付チューリング機械・チューリング帰着に関する発表の準備を事前に行う【事後学習】神託付チューリング機械・チューリング帰着に関する議論で生じた課題を検討する
27	基本な計算量クラスとそれらの関係：多項式時間階層【事前学習】多項式時間階層の定義及び基本性質を事前に確認する【事後学習】多項式時間階層に関する議論で生じた課題を検討する
28	確率的な計算【事前学習】確率的な計算に関する発表の準備を事前に行う【事後学習】確率的な計算に関する議論で生じた課題を検討する
29	確率計算の計算量クラス【事前学習】確率計算の計算量クラスに関する発表の準備を事前に行う【事後学習】確率計算の計算量クラスに関する議論で生じた課題を検討する
30	対話型証明系とグラフ同型判定問題【事前学習】対話型証明系とグラフ同型判定問題に関する発表の準備を事前に行う【事後学習】対話型証明系とグラフ同型判定問題に関する議論で生じた課題を検討する

その他
教科書	使用しない
参考書	使用しない
成績評価の方法及び基準	授業参画度(100%) 授業参画度は、毎回の輪講の発表内容・議論への参加の状況により評価する。
オフィスアワー	毎週月曜日１８：００〜１９：００

授業計画
1	アルゴリズムの定義・性能評価に関する導入【事前学習】アルゴリズムの定義・性能評価に基本概念を事前に確認する【事後学習】第2回以降の学習計画を定める
2	計算モデルと計算可能性：自然数【事前学習】自然数の定義及び基本性質を事前に確認する【事後学習】自然数に関する議論で生じた課題を検討する
3	計算モデルと計算可能性：帰納的関数【事前学習】帰納的関数の定義及び基本性質を事前に確認する【事後学習】帰納的関数に関する議論で生じた課題を検討する
4	計算モデルと計算可能性：ゲーデル数【事前学習】ゲーデル定義及び基本性質を事前に確認する【事後学習】ゲーデル数に関する議論で生じた課題を検討する
5	計算モデルと計算可能性：λ-定義可能関数【事前学習】λ-定義可能関数の定義及び基本性質を事前に確認する【事後学習】λ-定義可能関数に関する議論で生じた課題を検討する
6	計算モデルと計算可能性：チューリング機械【事前学習】チューリング機械の定義及び基本性質を事前に確認する【事後学習】チューリング機会に関する議論で生じた課題を検討する
7	計算モデルと計算可能性：Church-Turingの提唱【事前学習】Church-Turingの提唱の内容について事前に確認する【事後学習】Church-Turingの提唱に関する議論で生じた課題を検討する
8	計算モデルと計算可能性：ランダムアクセス機械【事前学習】ランダムアクセス機械　の定義及び基本性質を事前に確認する【事後学習】ランダムアクセス機械に関する議論で生じた課題を検討する
9	計算可能でない問題：様々なチューリング機械【事前学習】様々なチューリング機械の内容について事前に確認する【事後学習】様々なチューリング機械に関する議論で生じた課題を検討する
10	計算可能でない問題：帰納的に可算な問題と計算可能な問題【事前学習】帰納的に可算な問題と計算可能な問題に関する発表の準備を事前に行う【事後学習】帰納的に可算な問題と計算可能な問題に関する議論で生じた課題を検討する
11	計算可能でない問題：計算可能でない問題【事前学習】計算可能でない問題に関する発表の準備を事前に行う【事後学習】計算可能でない問題に関する議論で生じた課題を検討する
12	計算可能でない問題：帰着と決定不能問題【事前学習】帰着と決定不能問題に関する発表の準備を事前に行う【事後学習】帰着と決定不能問題に関する議論で生じた課題を検討する
13	計算量クラスと基本定理：計算量【事前学習】計算量に関する発表の準備を事前に行う【事後学習】計算量に関する議論で生じた課題を検討する
14	計算量クラスと基本定理：計算量の基本性質【事前学習】計算量の基本性質に関する発表の準備を事前に行う【事後学習】計算量の基本性質に関する議論で生じた課題を検討する
15	計算量クラスと基本定理：オーダ記法【事前学習】オーダ記法の定義や基本性質を事前に確認する【事後学習】オード記法の性質を理解するのに適切な練習問題を作成する
16	計算量クラスと基本定理：構成可能性と階層定理【事前学習】構成可能性と階層定理に関する発表の準備を事前に行う【事後学習】構成可能性と階層定理に関する議論で生じた課題を検討する
17	計算量クラスPとNP：クラスP 【事前学習】クラスPの定義及び基本性質を事前に確認する【事後学習】クラスPに関する議論で生じた課題を検討する
18	計算量クラスPとNP：クラスNP 【事前学習】クラスNPの定義及び基本性質を事前に確認する【事後学習】クラスNPに関する議論で生じた課題を検討する
19	計算量クラスPとNP：多項式時間版の帰着と困難性・完全性【事前学習】多項式時間版の帰着と困難性・完全性に関する発表の準備を事前に行う【事後学習】多項式時間版の帰着と困難性・完全性に関する議論で生じた課題を検討する
20	計算量クラスPとNP：NP-完全問題【事前学習】NP-完全問題に関する発表の準備を事前に行う【事後学習】NP-完全問題に関する議論で生じた課題を検討する
21	計算量クラスPとNP：Cook-Levinの定理の証明【事前学習】Cook-Levinの定理の証明に関する発表の準備を事前に行う【事後学習】Cook-Levinの定理の証明に関する議論で生じた課題を検討する
22	計算量クラスPとNP：様々なNP-完全問題【事前学習】様々なNP-完全問題に関する発表の準備を事前に行う【事後学習】様々なNP-完全問題に関する議論で生じた課題を検討する
23	基本な計算量クラスとそれらの関係：基本的な計算量クラス【事前学習】基本的な計算量クラスに関する発表の準備を事前に行う【事後学習】基本的な計算量クラスに関する議論で生じた課題を検討する
24	基本な計算量クラスとそれらの関係：補集合の計算量クラスと Immerman-Szelepc ́enyi の定理【事前学習】補集合の計算量クラスと Immerman-Szelepc ́enyi の定理に関する発表の準備を事前に行う【事後学習】補集合の計算量クラスと Immerman-Szelepc ́enyi の定理に関する議論で生じた課題を検討する
25	基本な計算量クラスとそれらの関係：基本的な計算量クラスに対する完全性【事前学習】基本的な計算量クラスに対する完全性に関する発表の準備を事前に行う【事後学習】基本的な計算量クラスに対する完全性に関する議論で生じた課題を検討する
26	基本な計算量クラスとそれらの関係：神託付チューリング機械・チューリング帰着【事前学習】神託付チューリング機械・チューリング帰着に関する発表の準備を事前に行う【事後学習】神託付チューリング機械・チューリング帰着に関する議論で生じた課題を検討する
27	基本な計算量クラスとそれらの関係：多項式時間階層【事前学習】多項式時間階層の定義及び基本性質を事前に確認する【事後学習】多項式時間階層に関する議論で生じた課題を検討する
28	確率的な計算【事前学習】確率的な計算に関する発表の準備を事前に行う【事後学習】確率的な計算に関する議論で生じた課題を検討する
29	確率計算の計算量クラス【事前学習】確率計算の計算量クラスに関する発表の準備を事前に行う【事後学習】確率計算の計算量クラスに関する議論で生じた課題を検討する
30	対話型証明系とグラフ同型判定問題【事前学習】対話型証明系とグラフ同型判定問題に関する発表の準備を事前に行う【事後学習】対話型証明系とグラフ同型判定問題に関する議論で生じた課題を検討する