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

本ページは平成18年度I-2期(6月,7月)にJAISTの東京田町キャンパスで 開講されている『I222 計算の理論(Theory of Computation)』の 授業のページです．上原はII-1期に石川キャンパスでも同じ授業を担当しています． 石川キャンパスでの授業に関するページはこちらを御覧下さい． 東京田町キャンパスでの授業に関する注意事項は以下の通りです．

• 質問は適宜メール(uehara@jaist.ac.jp)かオフィスアワーに直接受け付ける
• 成績はレポートと試験の成績で決める．

平成18年度I-2期・I222 計算の理論@田町キャンパス

• スケジュールとPDFファイル スケジュール中，3種類のPDFファイルを置いておきますが， それぞれ，次の意味です．

  [前]:	事前に配布した資料
  [実]:	実際に授業で使用した資料
  [小]:	[実]を1/6に縮小したもの)

  [前]と[実]は基本的には同じはずなのですが，ちょっと変わっていることがあります． 必要なところは授業中に説明します． また日程と章の対応は多少前後することがあります．
  1. (6月9日)計算の基本要素 (PDFファイル:[前] [実] [小])
  2. (6月9日)計算不可能性の証明と対角線論法 (PDFファイル:[前] [実] [小])
  3. (6月10日)計算不可能な関数の例 (PDFファイル:[前] [実] [小])
  4. (6月10日)枚挙可能集合 (PDFファイル:[前] [実] [小])
  5. (7月7日)クラスRECとクラスRE (PDFファイル:[前] [実] [小])
  6. (7月7日)還元可能性と完全性 (PDFファイル:[前] [実] [小])
  7. (7月8日)計算時間の計り方 (PDFファイル:[前] [実] [小])
  8. (7月8日)階層定理 (PDFファイル:[前] [実] [小])
  9. (7月21日)代表的な時間計算量クラス (PDFファイル:[前] [実] [小])
  10. (7月21日)クラスNP (PDFファイル:[前] [実] [小])
  11. (7月22日)時間量クラス間の関係 (PDFファイル:[前] [実] [小])
  12. (7月22日)多項式時間還元可能性 (PDFファイル:[前] [実] [小])
  13. (7月23日)多項式時間還元可能性にもとづく完全性 (PDFファイル:[前] [実] [小])
  14. (7月23日)期末テスト

配布資料とレポートのPDFファイル

• 6月9日:配布資料 ただし日程は変更されました．
• 6月10日:レポート(1)
• 7月8日:レポート(2)
• 7月23日:レポート(3)

休講情報

• 6月23日(金)，6月24日(土): 海外出張のため休講

その他

• 7月23日に期末テストを行ないます．

Last modified: Wed Jun 7 13:21:17 JST 2006 by R.Uehara (uehara@jaist.ac.jp)