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

本ページは平成23年度10月期にJAISTの品川キャンパスで 開講されている『I216 計算量の理論と離散数学(Computational Complexity and Discrete Mathematics)』の 授業のページです．担当は前半が上原隆平で， 後半が宮地充子先生です． このページは上原が管理していて，前半の情報しか書いてありません．

サポート情報

基本情報

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

石川キャンパスでの授業を録画したビデオ(Videos taken in the classroom)

ログイン(Login)

授業のスケジュールと 使用したPowerPointのPDFファイル(Schedule of the lessons and PDF files used in the lessons)

• 10/14：(1)計算の基本要素(Elements of Computation) (Original size; 1/6 size)
• 10/14：(2)計算不可能性の証明と対角線論法(Proof of Unsolvability and Diagonalization Method) (Original size; 1/6 size)
• 10/21：(3)時間量クラス間の関係(Relations among Time Complexity Classes) (Original size; 1/6 size)
• 10/21：(4)クラスNP(Class NP) (Original size; 1/6 size)
• 10/28：(5)多項式時間還元可能性(Polynomial-time Reducibility) (Original size; 1/6 size)
• 10/28：(6)多項式時間還元可能性にもとづく完全性(Completeness Based on Polynomial-time Reducibility) (Original size; 1/6 size)
• 11/11：レポートの返却/解答/解説(Comments on the report)…30分程度(30min.)
• 11/11：中間試験(Mid Exam)…上記のあとすぐ(After the comments)

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

• 10/14: 配布資料のPDFファイル(Handout)
• 10/14: レポートのPDFファイル(Report)

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

• 11/11:レポートの解答のPDFファイル(Answer to the report)

休講情報(Schedules for cancelations)

• 予定なし

その他(Misc.)

• 10月11日：ページ公開．(This page is available on the Web.)

Last modified: Wed Apr 21 13:23:47 JST 2010 by R.Uehara (uehara@jaist.ac.jp)