MyOOPS開放式課程
請加入會員以使用更多個人化功能
來自全球頂尖大學的開放式課程,現在由世界各國的數千名義工志工為您翻譯成中文。請免費享用!
課程來源:MIT
     

6.045J / 18.400J 自動機,可計算性與複雜性, 2005年春季課程

6.045J / 18.400J Automata, Computability, and Complexity, Spring 2005

 

譯者:屈國棟

編輯:劉慕華、洪曉慧

An NP completeness problem.

 “P等於NP嗎?,這個NP完全性問題是現代數學中最重要的待解問題之一。(圖片由麻省理工學院開放式課程提供。)

課程重點

本課程包含一套完整的作業。另外,復習/實習課程部分包括很多練習問題。6.045J是本系理論資訊科學系列中的一門課程。

 

課程描述

該課程提供給大學部學生,介紹基本的數學性計算模型,以及無窮物件的有窮表示法。該課程內容比6.840J/18.404J.稍淺顯。課程內容包括:有窮自動機與正則語言,上下文無關語言,圖靈機,部分遞迴函數,Church論題,不可判定性,可簡化性與完全性,時間複雜度與NP-完全性,概率計算,與互動式證明系統。

 

 

教學大綱

此教學大綱說明了本課程的學習目標,預期成果,必備先修課,必讀資料,課程形式與課程規範。

 

學習目標

修完6.045這門課後,學生將能夠掌握計算理論的基本方法和結論。他們將能夠運用這些方法去解決來自不同領域的問題,以及能夠藉由計算解法得到這些問題的答案。

特別是,學生能夠:

1.說明對於不可判定性問題和固有複雜問題的計算解法的理論上的限制。

2.描述不同領域中,不可判定性問題與固有不可行問題的計算解法的具體例子。

3.設計與分析過程的複雜度, 以確定各類自動機的屬性。

4.理解機器模型的形式定義。

5.證明各種問題的不可判定性或複雜性。

 

預期成果

學生應該能夠:

1.依據特殊屬性建構有窮自動機。

2.在有窮自動機的多種不同的表達方法之間轉換。

3.運用鴿巢原理(譯者:即抽屜原理)以及封閉性來證明某些無法用有窮自動機解決的問題。

4.計算關於自動機,語言與圖論的簡單程式的可計算複雜度的漸近值。

5.用對角矩陣與簡化方法證明不可判定性。

6.用可識別性與可判定性的關係來確定問題的可判定性。

7.描述各種不可判定問題的具體例子。

8.定義與解釋"P = NP?"問題與NP完全性的重要性。

9.描述各種NP完全性問題的具體例子。

10.用對角矩陣與多項式時間簡化方法證明時間與空間複雜度的下限。

11.定義確定性與非確定性計算的時間與空間,並解釋彼此間的關係。

12.描述已知的在多項式時間不能解決的可判定問題的具體例子。

 

目標 vs. 成果

目標:相關的成果

 

不可判定性與複雜性:5, 6, 7, 8, 9, 10, 11, 12

不可判定問題與複雜問題的例子:6, 9, 11, 12

自動機:1, 2, 3

正則模型:1, 2, 3

證明不可判定性與複雜性:3, 4, 5, 6, 7, 8, 10, 11

 

成果:反映的目標

 

構造有窮自動機:3, 4

正則運算式等:3, 4

非正則性:3, 4, 5

漸進複雜度: 5

不可判定的例子:1, 2

不可判定性:1, 5

可識別性:1, 5

PNP1, 5

NP例子:1, 2

不可判定性與複雜性:1, 5

時間-空間(複雜度):1, 2, 5

例子:1, 2

 

必備先修課

你應已修過6.042J,資訊科學數學。6.045 實際上是一門數學課程,你也要對數學概念相當熟悉。尤其是,你能熟練運用正規的數學證明,並能將證明恰當地寫出。

 

課程資料

本課程的教材是Michael Sipser 的《計算理論導論》Introduction to the Theory of Computation第二版,Boston, MA: Course Technology, 2005. ISBN: 0534950973.

除了教材以外,過去的學生認為以下幾本書很有用。我們希望學生在教科書中遇到費解的內容時可以參考這幾本書籍的解釋:

Martin, John. 《計算理論與語言導論》Introduction to Languages and the Theory of Computation.. New York, NY: McGraw Hill, 2002. ISBN: 0072322004.

Kozen, Dexter. 《自動機與可計算性》Automata and Computability. New York, NY: Springer-Verlag, 1999. ISBN: 0387949070.

Garey, Michael, and David S. Johnson. 《資訊與棘手問題:NP-完全性理論指導》 Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, NY: W.H. Freeman and Company, 1979. ISBN: 0716710455.

 

評分政策

最後的評分包括每週的作業,三次課堂測驗和期末考試。計算最終成績的方法如下:

 

Course grading.

項目

比重    

作業

30%

測驗

30%

期末考試

30%

課堂和復習課討論的參與

10%

 

 

課後作業

作業要在每週上課前交,你必須瞭解準時交作業是很重要的,我們不接受遲交的作業。在最後計算總成績的時候我們會去掉你作業的一個最低分數,所以請勿為某次作業的不理想成績而擔憂。

正確的答案與證明會被給予滿分。我們對於不完全的或者有小瑕疵的解答會給予部分分數。我們也會對如我不知道這類答案給予一點分數。有瑕疵的證明同樣也會給予部分分數,並且如果你將瑕疵部分注明的話,可以得到更高的分數。我們對於毫無道理,明顯想要混分數的答案將不給分。請只寫下你有把握的答案。胡亂的猜測只會浪費你我的時間。你要相信:錯誤的證明對你的頭腦是有害的。

我們要求所有的作業都必須是打字的。我們會提供LaTeX工具讓你充實作業答案,不過你並不一定要用到它們。允許手繪圖表。

 

合作原則

我們非常鼓勵合作。我們不期望你獨立完成每題作業,不過,我們期望你寫下自己的答案,即使該答案來自你合作者的貢獻。 再次重申:每個人必須獨立寫出自己的答案。並請注明與你合作的人。如果你用到了教科書以外的資料,請在每題中注明所用的參考資料。

 

測驗和考試

共有三次測驗和一次期末考試。測驗會在下面的時間舉行

第十日

第二十二日

第三十三日

每次測驗會涉及課程的一單元,期末考試涉及總的課程。測驗的那天就不會有作業了。

 

 

教學時程、復習/實習課程、相關閱讀資料

 

以下的日程表提供了授課(L),復習課(R)和測驗的資訊。

 

復習/實習課程部分包括用來討論的材料以及學生們在復習課中解決的問題。

 

該部分內容包括每週的閱讀材料。大部分閱讀資料來自教材:Michael Sipser 的《計算理論導論》Introduction to the Theory of Computation第二版,Boston, MA: Course Technology, 2005. ISBN: 0534950973.

(譯者:簡體中文譯本為《計算理論導論》第二版,張立昂等譯,機械工業出版社)

 

課程單元

重要日期

閱讀資料

簡介與復習Introduction and Review

L1

簡介Introduction

指派作業1

教材第0

 

R1

復習數學知識Math Review (PDF)

 

教材0

 

有窮自動機,正則語言,正則運算式Finite Automata, Regular Languages, Regular Expressions

 

L2

確定性有窮自動機(DFA) Deterministic Finite Automata (DFA)

 

教材1.1

 

L3

非確定性有窮自動機 (NFA) Nondeterministic Finite Automata (NFA)

交作業1
指派作業2

 

 

R2

確定性有窮自動機(DFA)和非確定性有窮自動機(NFA)DFAs and NFAs (PDF)

 

教材1.1, 1.2

 

L4

正則運算式Regular Expressions

 

教材1.3

 

L5

非正則語言Non-Regular Languages

交作業2
指派練習作業2.5

教材1.4

 

R3

正則運算式和非正則語言Regular Expressions and Non-Regular Languages (PDF)

 

教材1.3, 1.4

 

L6

自動機的演算法Algorithms for Automata

 

教材第1, 4.1

 

L7

測驗1 Quiz 1

指派作業3

 

 

R4

測驗1的題目和自動機綜合知識Quiz Questions and Automata Wrap-up (PDF)

 

 

 

可計算性理論Computability Theory

 

L8

圖靈機Turing Machines

 

教材第3(3.1, 3.3,3.2 – 尤其是非確定性圖靈機)

 

L9

非確定性圖靈機

Nondeterministic Turing Machines

交作業3
指派作業4

教材3.2 (尤其pp. 138-141), 教材4.2 (尤其pp. 160-164)

 

R5

圖靈機Turing Machines (PDF)

 

教材第3

 

L10

不可判定性Undecidability

 

教材第4(跳過pp. 156-158), 教材5.1 (直到p. 176)

 

L11

Post對應問題(PCP) PCP

交作業4
指派作業5

計算歷史(見教材p. 176) 和教材5.2

 

R6

不可判定性Undecidability (PDF)

 

教材第4(176), 教材5.1 (尤其 pp. 181-182), 5.2

 

L12

計數器和堆疊器

Counter and Stack Machines

 

Hopcroft, John, Rajeev MotwaniJeffrey Ullman.《自動機理論、語言和計算導論》Introduction to Automata Theory, Languages and Computation2版,Reading, MA: Addison Wesley, 2000, section 8.5. ISBN: 0201441241.

 

L13

簡化性Reducibility

交作業5
指派練習作業5.5

教材5.3

 

R7

計數器和堆疊器,簡化性,Rice定理Counter and Stack Machines, Reducibility, Rice's Theorem (PDF)

 

教材5.3

Hopcroft, John, Rajeev Motwani
Jeffrey Ullman.《自動機理論、語言和計算導論》Introduction to Automata Theory, Languages and Computation2版,Reading, MA: Addison Wesley, 2000, section 8.5. ISBN: 0201441241.

 

L14

遞迴定理Recursion Theorem

 

教材6.1

 

L15

測驗2 Quiz 2

指派作業6

 

 

R8

測驗2的題目和可計算性綜合知識Quiz 2 Questions and Computability Wrap-up (PDF)

 

 

 

複雜性理論Computability Theory

 

L16

時間複雜度Time Complexity

 

教材7.1, 7.2

 

L17

非確定性時間複雜度Nondeterministic Time Complexity

交作業6
指派作業7

教材7.3

 

R9

P問題和NP問題P and NP (PDF)

 

教材7.1, 7.2, 7.3

 

L18

NP完全性NP-Completeness

 

教材7.4 (尤其是定理7.30)

 

L19

Cook-Levin定理Cook-Levin Theorem

交作業7
指派作業8

教材7.4 (定理 7.30)

 

R10

多項式時間簡化Poly-Time Reductions

 

 

 

L20

NP完全性 II NP-Completeness II

交作業8
指派練習作業8.5

教材7.5

選讀:Cormen, Thomas H., Charles E. LeisersonRonald L. Rivest.《演算法導論》Introduction to Algorithms.,Cambridge, MA: MIT Press, 1990, chapter 36.5. ISBN: 0262530910.

 

R11

NP完全性NP-Completeness (PDF)

 

教材7.5

 

L21

進階時間複雜度

Advanced Time Complexity

 

教材9.1, 9.2

 

L22

測驗3 Quiz 3

指派作業9

 

 

R12

測驗3的題目和時間複雜度結尾Quiz 3 Questions and End of Time Complexity

 

 

 

L23

空間複雜度Space Complexity

 

教材8.4, 8.5, 8.6

 

L24

空間複雜度II Space Complexity II

交作業9
指派作業10

教材8.4, 8.5, 8.6

 

R13

空間複雜度III Space Complexity III (PDF)

 

教材8.4, 8.5, 8.6

 

L25

概率複雜度Probabilistic Complexity

 

教材10.2

 

L26

概率複雜度續

Probabilistic Complexity (cont.)

指派練習作業10.5

教材10.2

 

R14

概率複雜度和互動式證明Probabilistic Complexity and Interactive Proofs

 

選讀:

教材10.4

 

 

期末考試復習(可選)

 Final Exam Review Session (Optional)

 

 

 

 

期末考試Final Exam

 

 

 

 

 

 

作業(pdf)

我們要求所有的作業都必須是輸入的。任課老師推薦使用LaTeX。我們會提供LaTeX工具讓你充實作業答案。

除了一些用來練習的作業以外,學生們要完成所有的作業並繳交,如此學生可將課程內容相關材料均做練習。練習用作業標示如下。

作業 1  (PDF)

作業2 (PDF)

作業2.5 (PDF) (僅作練習)

作業3 (PDF)

作業4 (PDF)

作業5 (PDF)

作業5.5 (PDF) (僅作練習)

作業6 (PDF)

作業7 (PDF)

作業8 (PDF)

作業8.5(PDF) (僅作練習)

作業9 (PDF)

作業10 (PDF) (僅作練習)

作業10.5 (PDF) (僅作練習)

 

測驗 (pdf)

該部分包含了本課程的三次測驗和期末考試,以及附加練習題。

 

Exam files.

年度

考試

2005

測驗1:資訊和復習材料(PDF)

2005

測驗1 (PDF)

2004

測驗1 (PDF)

2005

測驗2:資訊和復習材料(PDF)

2005

測驗2 (PDF)

2004

測驗2 (PDF)

2005

測驗3:資訊和復習材料(PDF)

2005

測驗3 (PDF)

2004

測驗3 (PDF)
測驗3:附加練習問題(PDF)

2005

期末考試:資訊和復習材料(PDF)

2005

期末考試(PDF)

2004

期末考試(PDF)

 

6.045J / 18.400J Automata, Computability, and Complexity

Spring 2005

An NP completeness problem.

An NP completeness problem. "Does P equal NP?" is one of the most important unsolved questions in modern mathematics. (Image by MIT OCW.)



Course Highlights

This course features a full set of homework assignments. In addition, the recitation section includes many practice problems. 6.045J is a course in the department's "Theoretical Computer Science" concentration.

Course Description

This course is offered to undergraduates and introduces basic mathematical models of computation and the finite representation of infinite objects. The course is slower paced than 6.840J/18.404J. Topics covered include: finite automata and regular languages, context-free languages, Turing machines, partial recursive functions, Church's Thesis, undecidability, reducibility and completeness, time complexity and NP-completeness, probabilistic computation, and interactive proof systems.


*Some translations represent previous versions of courses.





Syllabus

Amazon logo Help support MIT OpenCourseWare by shopping at Amazon.com! MIT OpenCourseWare offers direct links to Amazon.com to purchase the books cited in this course. Click on the book titles and purchase the book from Amazon.com, and MIT OpenCourseWare will receive up to 10% of all purchases you make. Your support will enable MIT to continue offering open access to MIT courses.

The syllabus presents the course's objectives, learning outcomes, prerequisites, required readings, format, and policies.



Objectives

On completion of 6.045, students will be able to explain the basic methods and conclusions of the Theory of Computation. They will be able to apply these methods to problems from different fields and be guided by the results in searching for computational solutions to the problems.

In particular, students will be able to:

Explain the theoretical limits on computational solutions of undecidable and inherently complex problems.

Describe concrete examples of computationally undecidable or inherently infeasible problems from different fields.

Devise and analyze the complexity of procedures to determine properties of computationally bounded automata.

Understand formal definitions of machine models.

Prove the undecidability or complexity of a variety of problems.



Learning Outcomes

Students will be able to:

Synthesize finite automata with specific properties.

Convert among multiple representations of finite automata.

Use pigeon-holing arguments and closure properties to prove particular problems cannot be solved by finite automata.

Calculate asymptotic estimates of the computational complexity of simple procedures from automata, language and graph theory.

Prove undecidability using diagonalization and reducibility methods.

Use the relationship between recognizability and decidability to determine decidability properties of problems.

Describe concrete examples of undecidable problems from different fields.

Define, and explain the significance of, the "P = NP?" question and NP-completeness.

Describe concrete examples of NP-complete problems from different fields.

Prove lower bounds on time and space complexity using diagonalization and polynomial time reducibility methods.

Define deterministic and nondeterministic computation time and space, and explain the relationships among them.

Describe concrete examples of decidable problems that are known to be unsolvable in polynomial time.



Objectives vs. Outcomes

Objectives: Related Outcomes

Undecidability and complexity: 5, 6, 7, 8, 9, 10, 11, 12

Example undecidable/complex problems: 6, 9, 11, 12

Automata: 1, 2, 3

Formal models: 1, 2, 3

Prove undecidability/complexity: 3, 4, 5, 6, 7, 8, 10, 11

Outcomes: Reflected Objectives

Synthesize DFA's: 3, 4

Regular expressions, etc.: 3, 4

Nonregularity: 3, 4, 5

Asymptotic complexity: 5

Undecidable examples: 1, 2

Undecidability: 1, 5

Recognizability: 1, 5

P and NP: 1, 5

NP examples: 1, 2

Undecidability and complexity: 1, 5

Time-space: 1, 2, 5

Examples: 1, 2



Prerequisites

We assume that you have taken 6.042J, Mathematics for Computer Science. 6.045 is, at heart, a mathematics course, and we assume that you are reasonably facile with mathematical concepts. In particular, we assume that you are comfortable with formal mathematical proofs, and can write them up properly.



Course Materials

The book for this class is: Sipser, Michael. Introduction to the Theory of Computation. 2nd ed. Boston, MA: Course Technology, 2005. ISBN: 0534950973.

Apart from the textbook, students in the past have found the following books useful. We hope that students who find the textbook unenlightening can consult these books for a different explanation:

Martin, John. Introduction to Languages and the Theory of Computation. New York, NY: McGraw Hill, 2002. ISBN: 0072322004.

Kozen, Dexter. Automata and Computability. New York, NY: Springer-Verlag, 1999. ISBN: 0387949070.

Garey, Michael, and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, NY: W.H. Freeman and Company, 1979. ISBN: 0716710455.



Grading Policy

There will be (approximately) weekly homework assignments, three in-class quizzes, and a final exam. The final grade will be computed using the following weights:


Course grading. ACTIVITIES PERCENTAGES
Homework 30%
Quizzes 30%
Final Exam 30%
Participation in Class and Recitation Sessions 10%





Homeworks

Homework will be due approximately every week, at the beginning of lecture. We feel it is very important that you turn in the homework assignments on time and we are unable to accept late homeworks. However, when computing your grade at the end of the course, we will drop your lowest homework score. Therefore you need not worry about getting a bad grade on a single assignment.

With regards to homeworks: full credit will be given for correct answers and proofs. We will also grant partial credit for partial solutions and solutions with minor flaws. We will also give a small amount of partial credit for answers which read in full, "I don't know." Likewise, proofs with gaps will receive partial credit, and the partial credit granted will increase if the gaps are explicitly noted. We will give no credit for wildly incorrect answers which are obviously only there in the hopes of getting partial credit. Please only write down answers in which you are confident. Wild guesses only waste our time. Making yourself believe a false proof is bad for your brain.

We require that all homework solutions be typed up. We will provide LaTeX shells for you to flesh out with your solutions, but you do not need to use them. Hand-drawn diagrams are permitted.



Collaboration Policy

We strongly encourage collaboration. We do not expect you to be able to solve every homework problem on your own. We do, however, expect you to write up your own solution to every problem even if the solution is the result of a collaborative effort. To repeat: each person must write up his/her solutions separately. Also, in your write-up please credit the people with whom you worked. If you consult any reference material other than the textbook, please note on your homework which sources you used for each problem.



Quizzes and Exams

There will be three quizzes and one final exam. The quizzes will be held during class time on:

Day 10 Day 22 Day 33

Each quiz will cover a unit of the course; the final exam will be cumulative. There will be no homework due on a day on which a quiz is given.





Calendar

The calendar below provides information on the course's lecture (L), recitation (R) sessions and quizzes.


Course calendar. SES # TOPICS KEY DATES
Introduction and Review
L1 Introduction Homework 1 out
R1 Math Review  
Finite Automata, Regular Languages, Regular Expressions
L2 Deterministic Finite Automata (DFA)  
L3 Nondeterministic Finite Automata (NFA) Homework 1 due

Homework 2 out
R2 DFAs and NFAs  
L4 Regular Expressions  
L5 Non-Regular Languages Homework 2 due

Practice homework 2.5 out
R3 Regular Expressions and Non-Regular Languages  
L6 Algorithms for Automata  
L7 Quiz 1 Homework 3 out
R4 Quiz Questions and Automata Wrap-up  
Computability Theory
L8 Turing Machines  
L9 Nondeterministic Turing Machines Homework 3 due

Homework 4 out
R5 Turing Machines  
L10 Undecidability  
L11 PCP Homework 4 due

Homework 5 out
R6 Undecidability  
L12 Counter and Stack Machines  
L13 Reducibility Homework 5 due

Practice homework 5.5 out
R7 Counter and Stack Machines, Reducibility, Rice's Theorem  
L14 Recursion Theorem  
L15 Quiz 2 Homework 6 out
R8 Quiz 2 Questions and Computability Wrap-up  
Complexity Theory
L16 Time Complexity  
L17 Nondeterministic Time Complexity Homework 6 due

Homework 7 out
R9 P and NP  
L18 NP-Completeness  
L19 Cook-Levin Theorem Homework 7 due

Homework 8 out
R10 Poly-Time Reductions  
L20 NP-Completeness II Homework 8 due

Practice homework 8.5 out
R11 NP-Completeness  
L21 Advanced Time Complexity  
L22 Quiz 3 Homework 9 out
R12 Quiz 3 Questions and End of Time Complexity  
L23 Space Complexity  
L24 Space Complexity II Homework 9 due

Practice homework 10 out
R13 Space Complexity III  
L25 Probabilistic Complexity  
L26 Probabilistic Complexity (cont.) Practice homework 10.5 out
R14 Probabilistic Complexity and Interactive Proofs  
  Final Exam Review Session (Optional)  
  Final Exam  




Readings

Amazon logo Help support MIT OpenCourseWare by shopping at Amazon.com! MIT OpenCourseWare offers direct links to Amazon.com to purchase the books cited in this course. Click on the book titles and purchase the book from Amazon.com, and MIT OpenCourseWare will receive up to 10% of all purchases you make. Your support will enable MIT to continue offering open access to MIT courses.

This section contains the weekly reading assignments for the course. Most of the reading assignments refer to the required textbook: Sipser, Michael. Introduction to the Theory of Computation. 2nd ed. Boston, MA: Course Technology, 2005. ISBN: 0534950973.


Course readings. SES # TOPICS READINGS
Introduction and Review
L1 Introduction Chapter 0
R1 Math Review Chapter 0
Finite Automata, Regular Languages, Regular Expressions
L2 Deterministic Finite Automata (DFA) Section 1.1
L3 Nondeterministic Finite Automata (NFA)  
R2 DFAs and NFAs Sections 1.1, 1.2
L4 Regular Expressions Section 1.3
L5 Non-Regular Languages Section 1.4
R3 Regular Expressions and Non-Regular Languages Sections 1.3, 1.4
L6 Algorithms for Automata Chapter 1, Section 4.1
L7 Quiz 1  
R4 Quiz Questions and Automata Wrap-up  
Computability Theory
L8 Turing Machines Chapter 3 (Sections 3.1, 3.3, and 3.2 - except Nondeterminism)
L9 Nondeterministic Turing Machines Section 3.2 (especially pp. 138-141), Section 4.2 (especially pp. 160-164)
R5 Turing Machines Chapter 3
L10 Undecidability Chapter 4 (skip pp. 156-158 on context-free languages), Section 5.1 (up to p. 176)
L11 PCP Computation histories (see p. 176) and Section 5.2
R6 Undecidability Chapter 4 (up to p. 176), Sections 5.1 (except pp. 181-182), 5.2
L12 Counter and Stack Machines Hopcroft, John, Rajeev Motwani, and Jeffrey Ullman. Introduction to Automata Theory, Languages and Computation. 2nd ed. Reading, MA: Addison Wesley, 2000, section 8.5. ISBN: 0201441241.
L13 Reducibility Section 5.3
R7 Counter and Stack Machines, Reducibility, Rice's Theorem Section 5.3

Hopcroft, John, Rajeev Motwani, and Jeffrey Ullman. Introduction to Automata Theory, Languages and Computation. 2nd ed. Reading, MA: Addison Wesley, 2000, section 8.5. ISBN: 0201441241.
L14 Recursion Theorem Section 6.1
L15 Quiz 2  
R8 Quiz 2 Questions and Computability Wrap-up  
Complexity Theory
L16 Time Complexity Sections 7.1, 7.2
L17 Nondeterministic Time Complexity Section 7.3
R9 P and NP Sections 7.1, 7.2, 7.3
L18 NP-Completeness Section 7.4 (except Theorem 7.30)
L19 Cook-Levin Theorem Section 7.4 (Theorem 7.30)
R10 Poly-Time Reductions  
L20 NP-Completeness II Section 7.5

Optional Reading: Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms. Cambridge, MA: MIT Press, 1990, chapter 36.5. ISBN: 0262530910.
R11 NP-Completeness Section 7.5
L21 Advanced Time Complexity Sections 9.1, 9.2
L22 Quiz 3  
R12 Quiz 3 Questions and End of Time Complexity  
L23 Space Complexity Sections 8.4, 8.5, 8.6
L24 Space Complexity II Sections 8.4, 8.5, 8.6
R13 Space Complexity III Sections 8.4, 8.5, 8.6
L25 Probabilistic Complexity Section 10.2
L26 Probabilistic Complexity (cont.) Section 10.2
R14 Probabilistic Complexity and Interactive Proofs Optional Reading: Section 10.4
  Final Exam Review Session (Optional)  
  Final Exam  




Recitations

This section contains discussion materials and problems solved by students during the recitation sessions.


Recitation files. SES # Topics
R1 Math Review (PDF)
R2 DFAs and NFAs (PDF)
R3 Regular Expressions and Non-Regular Languages (PDF)
R4 Quiz Questions and Automata Wrap-up (PDF)
R5 Turing Machines (PDF)
R6 Undecidability (PDF)
R7 Counter and Stack Machines, Reducibility, Rice's Theorem (PDF)
R8 Quiz 2 Questions and Computability Wrap-up (PDF)
R9 P and NP (PDF)
R10 Poly-Time Reductions
R11 NP-Completeness (PDF)
R12 Quiz 3 Questions and End of Time Complexity
R13 Space Complexity III (PDF)
R14 Probabilistic Complexity and Interactive Proofs




Assignments

Amazon logo Help support MIT OpenCourseWare by shopping at Amazon.com! MIT OpenCourseWare offers direct links to Amazon.com to purchase the books cited in this course. Click on the book titles and purchase the book from Amazon.com, and MIT OpenCourseWare will receive up to 10% of all purchases you make. Your support will enable MIT to continue offering open access to MIT courses.

This section contains the weekly homework assignments for the course. Many of the homework assignments refer to the required textbook: Sipser, Michael. Introduction to the Theory of Computation. 2nd ed. Boston, MA: Course Technology, 2005. ISBN: 0534950973.

All homework solutions for this course must be typed. The course staff highly recommend that students use LaTeX. A useful LaTeX Web site can be found here.

The students are expected to complete and turn in all homework assignments except for a few assignments that are just given so that students can practice the material covered in the lectures. The practice homework assignments are indicated below.

Homework 1 (PDF)

Homework 2 (PDF)

Homework 2.5 (PDF) (practice only)

Homework 3 (PDF)

Homework 4 (PDF)

Homework 5 (PDF)

Homework 5.5 (PDF) (practice only)

Homework 6 (PDF)

Homework 7 (PDF)

Homework 8 (PDF)

Homework 8.5 (PDF) (practice only)

Homework 9 (PDF)

Homework 10 (PDF) (practice only)

Homework 10.5 (PDF) (practice only)





Exams

This section contains the course's three quizzes and final exam, along with practice problems.


Exam files. YEARS EXAMs
2005 Quiz 1: Information and Review Material (PDF)
2005 Quiz 1 (PDF)
2004 Quiz 1 (PDF)
2005 Quiz 2: Information and Review Material (PDF)
2005 Quiz 2 (PDF)
2004 Quiz 2 (PDF)
2005 Quiz 3: Information and Review Material (PDF)
2005 Quiz 3 (PDF)
2004 Quiz 3 (PDF)

Quiz 3: Additional Practice Problems (PDF)
2005 Final Exam: Information and Review Material (PDF)
2005 Final Exam (PDF)
2004 Final Exam (PDF)



留下您對本課程的評論
標題:
您目前為非會員,留言名稱將顯示「匿名非會員」
只能進行20字留言

留言內容:

驗證碼請輸入7 + 0 =

標籤

現有標籤:1
新增標籤:


有關本課程的討論

课程讨论
workonet,请你尊重我们的网上空间。谢谢。

michael, 2011-11-16 12:25:59
課程討論
先說聲抱歉,如果打擾到您們。 誠摯告訴您一個機會:  你想致富嗎? 相信我 ! 這是一個已被眾多名人保證最有效, 低 門 檻 的 創 業 -> http://azyyeayzz.weebly.com/
workonet, 2010-10-13 14:58:29
课程讨论
什么时候能有以前的上课视频啊?
mayhykova, 2010-03-21 22:16:48

Creative Commons授權條款 本站一切著作係採用 Creative Commons 授權條款授權。
協助推廣單位: