淡江大學九十六學年度第二學期課程教學計劃表

壹. 科目名稱: 計算理論(二), 課號TMIXM1M1772 0A

貳. 授課老師: 廖賀田 Tel: 02-27687342, Email: htliaw@mail.tku.edu.tw

參. 開課系所班級: 資管系碩士班

肆. 必選修: 選修

伍. 學分數: 2 學分

陸. 先修科目: 須有程式設計經驗

柒. 教學內容及進度:

1. 繼續討論 Turing machine
2. intractable problem
3. polynomial time-space
4. NP-complete problems
5. the class co-NP
6. PSpace-complete problems
7. P=NP question

捌. 授課方式: 課堂講授

玖. 教學設備: 電腦, 投影機

拾. 教材課本:

• J. E. Hopcroft, R. Motwani, J. D. Ullman, "Introduction to Automata Theory, Languages, and Computation," 2 ed. Addison-Wesley 華通書坊經銷

拾壹. 參考書籍 :

• J. L. Gersting: "Mathematical Structures for Computer Science"
• P. Linz: "An Introduction to Formal Languages and Automata, 3ed, Johns and Bartlett, 開發經銷
• H. Lewis , C. H. Papadimitriou: "Elements of the Theory of omputation", 2ed, 全華經銷
• J. G. Brookshear: "Theory of Computation-- Formal Languages, Automata, and Complexity", Benjamin/Cummings

拾貳. 成績考核方式:

• 交報告與課堂表現

拾參. 備考:

• 本課程資料下載: 本課程FTP