平成21年度・I216 計算量の理論と離散数学(Computational Complexity and Discrete Mathematics)

本ページは平成21年度６期（２月〜３月）にJAISTの田町キャンパスで 開講されている『I216 計算量の理論と離散数学(Computational Complexity and Discrete Mathematics)』の 授業のページです．担当は上原隆平です． ただし上原は「計算量の理論」のみ担当で，「離散数学」は宮地充子先生が担当します． このページには「計算量の理論」の情報しか書いてありません．

サポート情報

基本情報

• シラバス| Syllabus
• 教場：３階311号室
• テキスト: 「計算可能性・計算の複雑さ入門」渡辺治著，近代科学社
• 参考図書: 「計算理論の基礎」Michael Sipser著，太田和夫・田中圭介監訳， 阿部正幸・植田広樹・藤岡淳・渡辺治訳，共立出版
  全3冊組のうち，[2. 計算可能性の理論]と[3. 複雑さの理論]が 本授業の領域をカバーしています．

授業予定(Schedule)

• 2月26日(金)18:30〜21:40：上原担当
• 2月27日(土)13:30〜16:40：宮地先生担当
• 3月5日(金)18:30〜21:40：上原担当
• 3月6日(土)13:30〜16:40：宮地先生担当
• 3月12日(金)18:30〜21:40：上原担当
• 3月13日(土)13:30〜16:40：上原担当
• 3月19日(金)18:30〜21:40：宮地先生担当
• 3月20日(土)13:30〜16:40：宮地先生担当

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

• 2月26日(金)：(1)計算の基本要素(Elements of Computation) (Original size;1/6 size)
• 2月26日(金)：(2)計算不可能性の証明と対角線論法(Proof of Unsolvability and Diagonalization Method) (Original size;1/6 size)
• 3月5日(金)：(3)クラスNP(Class NP) (Original size;1/6 size)
• 3月5日(金)：(4)時間量クラス間の関係(Relations among Time Complexity Classes) (Original size;1/6 size)
• 3月12日(金)：(5)多項式時間還元可能性(Polynomial-time Reducibility) (Original size;1/6 size)
• 3月12日(金)：(6)多項式時間還元可能性にもとづく完全性(Completeness Based on Polynomial-time Reducibility) (Original size;1/6 size)
• 3月13日(土)：試験(Examination)
• 3月13日(土)：オプション：試験の解答と解説(Option:Answers and Comments on the exam.) (Original size;1/6 size)

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

• 2月26日(金)：配布資料のPDFファイル(Handout)
• 2月26日(金)：レポート1のPDFファイル(Report 1)
  [訂正] Problem 1に 「例えば　lo(ε)=oo(ε)=1, lo(0)=oo(0)=1, lo(1)=2, oo(00)=2」 とありますが，これは 「例えば　lo(ε)=oo(ε)=1, lo(0)=oo(0)=2, lo(1)=3, oo(00)=3」 が正解です．すみません．
• 3月5日(金)：レポート2のPDFファイル(Report 2)

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

• 3月12日(金)： レポート1とレポート2の解答のPDFファイル(Answers and Comments on Reports 1 and 2) (Original size;1/6 size)
  [訂正] Report 2 の Problem 2 の 2 で「d=0」とおいていますが， 定義に従うと「d>0」でなければならないので，例えば「d=1」とでも すべきでした．すみません．
• 3月13日(土)： 試験の解答と解説のPDFファイル(Answers and Comments on Exam.) (Original size;1/6 size)

その他(Misc.)

• 3月14日：試験の採点終わりました．もし疑問点などあれば気軽にメールで聞いて下さい．
• 3月4日：レポート(1)の問題文にちょっと間違いがありました． 上記の[訂正]を参考にして下さい．
• 3月3日: レポートをメールで提出する際はPDFファイルにしてくれるとうれしいです．
• 2月18日: ページ公開．(This page is available on the Web.)

Last modified: Sun Mar 14 11:04:07 JST 2010 by R.Uehara (uehara@jaist.ac.jp)