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

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

サポート情報

基本情報

• シラバス| Syllabus
• 教場: I1講義室
• 講義時間(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)

大学内のみ視聴可能で，Windows 上の IE のみ対応しているようです． (It is available in JAIST, and you can see only when you use IE on Windows) 視聴方法(How to see)| ログイン先(Login)

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

• 4/9(Thu):(1)計算の基本要素(Elements of Computation) (Original size; 1/6 size)
• 4/13(Mon):(2)計算不可能性の証明と対角線論法(Proof of Unsolvability and Diagonalization Method) (Original size; 1/6 size)
• 4/16(Thu):(3)クラスNP(Class NP) (Original size; 1/6 size)
• 4/20(Mon):(4)時間量クラス間の関係(Relations among Time Complexity Classes) (Original size; 1/6 size)
• 4/23(Thu):(5)多項式時間還元可能性(Polynomial-time Reducibility) (Original size; 1/6 size)
• 4/27(Mon):(6)多項式時間還元可能性にもとづく完全性(Completeness Based on Polynomial-time Reducibility) (Original size; 1/6 size)
• 4/30(Thu):レポートの解説・質問受け付けなど(Office hour; some comments and answers of reports will be presented.)

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

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

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

• 4/23(Thu): レポート1の解答のPDFファイル(Answer to the report 1)
• 4/30(Thu): レポート2の解答のPDFファイル(Answer to the report 2)

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

• 4/9(Thu): 居室にて質問受け付け(Questions are welcome at I67b)．
• 4/16(Thu): 居室にて質問受け付け(Questions are welcome at I67b)．
• 4/23(Thu): レポート1の解答と解説(Comments on the 1st report)．
• 4/30(Thu): 居室にて質問受け付け(Questions are welcome at I67b)．
• 5/ 7(Thu): 居室にて質問受け付け(Questions are welcome at I67b)．

その他(Misc.)

• 5月7日: 中間テストの採点は終わりました．希望者には点数を通知します． メールをくれればメールで点を教えます． 直接来てくれればどこが間違っていたかを教えます．
• 5月1日: レポート2の採点は終わりました．希望者には返却します．
• 4月9日: テキストと参考図書を追加しました．
• 中間試験は5月7日(木)です．(Mid-term examination will be placed on May 7th.)
• 4月30日(木)は予備日です．オフィスアワーにする予定です．
• 4月3日: ページ公開．(This page is available on the Web.)

Last modified: Thu May 7 14:52:53 JST 2009 by R.Uehara (uehara@jaist.ac.jp)