|
課程名稱 |
資訊工程理論基礎
COMPUTING THEORY |
|
開課學期 |
99-1 |
|
授課對象 |
資訊工程學研究所 |
|
授課教師 |
呂育道 |
|
課號 |
CSIE7110 |
|
課程識別碼 |
922EM0520 |
|
班次 |
01 |
|
學分 |
3 |
|
全/半年 |
半年 |
|
必/選修 |
必修 |
|
上課時間 |
星期二2,3,4(9:10~12:10) |
|
上課地點 |
資103 |
|
備註 |
本課程以英語授課。本課程以英語授課。
限電資學院學生(含輔系、雙修生)
總人數上限：176人 |
|
Ceiba 課程網頁 |
http://ceiba.ntu.edu.tw/991complexity |
|
課程簡介影片 |
|
|
核心能力關聯 |
核心能力與課程規劃關聯圖 |
|
課程大綱
|
|
為確保您我的權利,請尊重智慧財產權及不得非法影印
|
|
課程概述 |
本課程將介紹計算理論中重要的內容，例如丘池－圖靈論點（Church-Turing thesis）、可計算性（computability）、時間複雜度（time complexity）、空間複雜度（space complexity）、電路複雜度（circuit complexity）、P完備性（P-completeness）、NP完備性（NP-completeness）、類亂數產生器（pseudorandom generator）、質數判定（primality testing）、互動式證明系統（interactive proof system）、可近似性（approximability）等。 |
|
課程目標 |
本課程的目標在於讓修課同學：
1)了解資訊工程領域中常提及的NP完備問題之意義。
2)在遇到各種計算問題時，能夠估計該問題之難度並採取適當方式解決，如利用近似演算法、隨機演算法等。
|
|
課程要求 |
■考試 ■作業 |
|
預期每週課後學習時數 |
|
|
Office Hours |
|
|
指定閱讀 |
|
|
參考書目 |
C. H. Papadimitriou, Computational Complexity. Addison-Wesley, 1995. Errata for the 1994 edition.
M. R. Garey and D. S. Johnson, Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, 1979.
J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation. Prentice-Hall, 1981. |
|
評量方式
(僅供參考) |
|
|