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

本ページは平成22年度1-1期(4月8日(木)〜6月4日(金))に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. 複雑さの理論]が 本授業の領域をカバーしています．
• TA：上原研の中西朗裕くん(nak-aki@jaist.ac.jp)

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

ログイン(Login)

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

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

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

• 4/8(Thu): 配布資料のPDFファイル(Handout)
• 4/15(Thu): レポートのPDFファイル(Report)

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

• 4/22(Thu): レポートの解答のPDFファイル(Answer to the report)
• 5/5(Thu): 中間試験の解答のPDFファイル(Answer to the report)

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

• 4/8(Thu): 居室にて質問受け付け(Questions are welcome at I67b)．
• 4/15(Thu): 【(4)クラスNP(Class NP)】の補講
• 4/22(Thu): レポートの解答と解説(Comments on the report)．
• 5/ 6(Thu): 中間試験の解答と解説(Comments on the mid examination)．
  研究室紹介はこの日ではありませんでした．

休講情報(Schedules for cancelations)

• 4月19日（木）は出張のため休講です．なおTAの中西君も同じ用事で出張のため不在です．

その他(Misc.)

• 5月 7日：中間試験採点終わりました．平均点は26.93/40点です． 試験とレポートを合わせた平均点は34.5/50点です．
• 4月26日：レポート採点終わりました．平均点は7.583/10点です．
• 4月22日：5月6日は研究室紹介はありませんので，オフィスアワーの中間試験の解答と解説は予定通り行います．
• 4月5日：ページ公開．(This page is available on the Web.)

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