|
|
 |
|
 |
|
Sipser教授的教科書封面圖片（圖片經Thomson/Course Technology授權使用。）
Image of cover of Prof. Sipser's textbook. (Courtesy of Thomson/Course Technology. Used with permission.)
|
|
|
課程重點
這門課程的網站包括作業集，一份期中考試的樣卷和有關Sipser教授的課本《計算理論入門》的相關資訊。
This course web site features problem sets, a sample mid-term exam, and information about Professor Sipser's textbook: Introduction to the Theory of Computation.
課程描述
本課程比18.400J 自動機、可計算性和複雜性涉及面更廣、更理論化。主要側重於可計算性，計算複雜性理論，正則和上下文無關語言，可判定和不可判定問題，規約性，遞迴函數理論，計算的時間和空間複雜性的度量，完備性，分層理論，固有複雜問題，神喻（Oracles），概率計算和交互推理系統。
A more extensive and theoretical treatment of the material in 18.400J, Automata, Computability, and Complexity, emphasizing computability and computational complexity theory. Regular and context-free languages. Decidable and undecidable problems, reducibility, recursive function theory. Time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems.
|
|
|
| 師資 |
|
講師：
Michael Sipser 教授
|
| 上課時數 |
教師授課：
每週2節
每節1.5小時
複習/實習課：
每週1節
每節1小時
|
| 程度 |
|
研究所
|
| 回應 |
| 告訴我們您對本課程或「開放式課程網頁」的建議。 |
| 聲明 |
麻省理工學院開放式課程認可 開放式課程計畫（OOPS）的翻譯計畫，開放式課程計畫（OOPS）乃是運用其獨立團隊、獨立資源、獨立流程進行翻譯計畫之團隊。
所有麻省理工學院開放式課程之材料皆以麻省理工學院開放式課程創作共享授權發佈，所有之翻譯資料皆由開放式課程計畫（OOPS）所提供，並由其負翻譯品質之責任。
此處麻省理工學院開放式課程之資料乃由 開放式課程計畫（OOPS） 譯為正體中文。麻省理工學院開放式課程在此聲明，不論是否遭遇或發現相關議題，麻省理工學院開放式課程、麻省理工學院教師、麻省理工學院校方並不對翻譯正確度及完整性作保證。上述單位並對翻譯後之資料不作明示或默許對任一特定目的之適合性之保證、非侵權之保證、或永不出錯之保證。麻省理工學院校方、麻省理工學院開放式課程對翻譯上之不正確不負任何責任。由翻譯所引發任何關於此等資料之不正確或其他瑕疵，皆由開放式課程計畫（OOPS）負全責，而非麻省理工學院開放式課程之責。
原文聲明 |
|
|
|
|
|
 |
|
