Computational Complexity and Discrete Mathematics

I216: Computational Complexity and Discrete Mathematics（平成28年度2-1期・I216E 計算量の理論と離散数学）

This is a support page of I216E: Computational Complexity and Discrete Mathematics (I216E 計算量の理論と離散数学) at JAIST, Ishikawa from October 12 to December 1, 2016. The lectures are given by Ryuhei Uehara, who maintains this page.

Information (サポート情報)

Classroom (教室): Lecture Hall (大講義室)
Lectures (講義時間): On Mondays, 10:50-12:30, and Thursdays 9:00-10:40.
Office Hour (オフィスアワー): Thursdays 13:30-15:00 (木曜日3時限).
Textbook (テキスト):

Former half(前半)
``Introduction to the Theory of Computation,'' Michael Sipser, PWS Publishing, 1997.
「計算理論の基礎」Michael Sipser著，太田和夫・田中圭介監訳，阿部正幸・植田広樹・藤岡淳・渡辺治訳，共立出版
全3冊組のうち，後半の[2. 計算可能性の理論]と[3. 複雑さの理論]が本授業の領域をカバーしています．
Latter half(後半)
``Cryptography in Algebraic Aspects,'' Atsuko Miyaji, Nihon-hyoronsha, 2012 (in Japanese)
「代数学から学ぶ暗号理論」宮地充子著，日本評論社，2012年
Reference (参考図書):

Former half(前半)
``Introduction to Computability and Computational Complexity,'' Osamu Watanabe, Kindai-kagakusha, 1992.
「計算可能性・計算の複雑さ入門」渡辺治著，近代科学社，1992年
Latter half(後半)
``IT Text Information Security,'' Atsuko Miyaji and Hiroaki Kikuchi, Ohmsha, 2003 (in Japanese)
「IT Text情報セキュリティ」宮地充子，菊池浩明著，オーム社，2003年

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

10/13(Thu): Cancel due to business trip (出張のため休講)
10/17(Mon): 1. Elements of Computation (計算の基本要素)
10/20(Thu): 2. Proof of Unsolvability and Diagonalization Method (計算不能性の証明と対角線論法)
10/24(Mon): 3. Relations among Time Complexity Classes (時間量クラス間の関係)
10/27(Thu): 4. Class NP (クラスNP)
10/31(Mon): 5. Polynomial-time Reducibility (多項式時間還元可能性)
11/07(Mon): 6. Completeness Based on Polynomial-time Reducibility (多項式時間還元可能性にもとづく完全性)
11/10(Thu): 7. Mid-term Examination (中間試験)
11/14(Mon): 8. Group (1) （群）
11/17(Thu): 9. Group (2) （群）
11/17(Thu): 10. Ring （環）
11/21(Mon): 11. Ring, Field （環，体）
11/24(Thu): 12. Number Theory (1) （数論）
11/24(Thu): 13. Number Theory (2) （数論）
11/28(Mon): 14. Final Examination （期末試験）
12/01(Thu): Cancel due to business trip (出張のため休講)

PDF files of the others (その他のPDFファイル)

10/17(Thu): PDF file of handout(配布資料)
10/20(Thu): PDF file of report 1 (レポート1)
10/27(Thu): PDF file of the answer and comments for Report 1 by Duc
11/07(Mon): PDF file of report 2 (レポート2)
11/17(Thu): PDF file of the answer and comments for Report 2 by Duc
11/17(Thu): PDF file of report 3 (レポート3)
11/24(Thu): PDF file of the answer and comments for Report 3 by Duc

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

10/13(Thu): Uehara is out of JAIST
10/20(Thu): Ask me if you have any questions/comments/etc.
10/27(Thu): Comments on Report 1 (by Duc)
11/10(Thu): Comments on Report 2 (by Duc)
11/17(Thu): 10. Ring
11/24(Thu): 13. Number Theory
12/01(Thu): Uehara is out of JAIST

Misc. (その他)

2016/10/16: This page is available on the Web. (ページ公開．)

Last modified: Sun May 10 22:20:00 JST 2015
by R.Uehara (uehara@jaist.ac.jp)