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

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

サポート情報

基本情報

• シラバス| Syllabus
• 教場：I3・4講義室
• 講義時間(Lectures)：月曜日2時限(Mon;11:00〜12:30)，木曜日1時限(Thu;9:20〜10:50)，
• オフィスアワー(Office Hour)：木曜日3時限(Thu;13:30〜15:00)
• テキスト：「計算可能性・計算の複雑さ入門」渡辺治著，近代科学社
• 参考図書：「計算理論の基礎」Michael Sipser著，太田和夫・田中圭介監訳， 阿部正幸・植田広樹・藤岡淳・渡辺治訳，共立出版
  全3冊組のうち，[2. 計算可能性の理論]と[3. 複雑さの理論]が 本授業の領域をカバーしています．

教室での授業を録画したビデオ(Videos taken in the classroom)

ログイン(Login)

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

• 4/7(Thu)：(1)計算の基本要素(Elements of Computation) (Original size; 1/6 size)
• 4/11(Mon)：(2)計算不可能性の証明と対角線論法(Proof of Unsolvability and Diagonalization Method) (Original size; 1/6 size)
• 4/14(Thu)：(3)時間量クラス間の関係(Relations among Time Complexity Classes) (Original size; 1/6 size)
• 4/18(Mon)：休講
• 4/21(Thu)：(4)クラスNP(Class NP) (Original size; 1/6 size)
• 4/25(Mon)：(5)多項式時間還元可能性(Polynomial-time Reducibility) (Original size; 1/6 size)
• 4/28(Thu)：(6)多項式時間還元可能性にもとづく完全性(Completeness Based on Polynomial-time Reducibility) (Original size; 1/6 size)
• 5/2(Mon)：中間試験(Mid Exam)

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

• 4/7(Thu): 配布資料のPDFファイル(Handout)
• 4/14(Thu): レポート(1)のPDFファイル(Report(1))
• 4/25(Mon): レポート(2)のPDFファイル(Report(2))

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

• 4/21(Thu):レポート(1)の解答のPDFファイル(Answer to the report) (Original size; 1/6 size)
• 4/28(Thu):レポート(2)の解答のPDFファイル(Answer to the report) (Original size; 1/6 size)

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

• 4/7(Thu): 居室にて質問受け付け(Questions are welcome at I67b)．
• 4/14(Thu): 居室にて質問受け付け(Questions are welcome at I67b)．
• 4/21(Thu): レポート(1)の解答と解説(Comments on the report)．
• 4/28(Thu): 講義(6)とレポート(2)の解答と解説(Comments on the report)．

休講情報(Schedules for cancelations)

• 4月28日（木）は午前中は出張のため休講ですが，オフィスアワーに補講をやります．
• 4月18日（月）は出張のため休講です．

その他(Misc.)

• 5月5日：中間テストの採点終わりました．質問がある人は適宜聞いて下さい．
• 4月6日：ページ公開．(This page is available on the Web.)

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