School of Computer Science, Tel Aviv University

Computational Models

0368.2200

Fall 2010

 

Lecture

Monday 13-16 (Dach 005)

Recitations

(a) Wednesday 14-15 (Schreiber 007)

(b) Wednesday 15-16 (Schreiber 007)

Lecturer

Dr. Anna Zamansky

Teaching Assistant

Ori Lahav

Grader

Ariel Jarovsky  (post box 303) ( arielhe -at- post -dot- tau -dot- ac -dot- il )

Exam

Moed A           09/02/2011

 

Moed B            06/09/2011

 

 

Class Bulletin-Board

Date

Announcement

17/10/10

Welcome to computational models, fall 2010, we hope you have a wonderful semester!

As an appetizer, we recommend to read (and understand) this proof: http://www.ling.ed.ac.uk/~gpullum/loopsnoop.html

19/10/10

ההרצאה בשבוע הבא (25.10) תתחיל בשעה 14:10. השעה הראשונה מבוטלת.

27/11/10

רמז נוסף לשאלה 8 בתרגיל 2: נסו להראות ששפה כזו היא איחוד סופי של שפות מהצורה xy* .

13/12/10

ביום שישי ה-17.12.10 יתקיים תרגול השלמה. לקבוצה 02 משעה 10:00 עד 11:00. לקבוצה 03 משעה 11:00 עד 12:00. התרגול יתקיים בשרייבר 7.

13/12/10

רמזים קלים לשאלה 2ג : ii- האם מה שעשיתם בסעיף הראשון לא עובד? iii- כדאי להשתמש כאן בעובדה שחיתוך של שפה ח"ה ושפה רגולרית היא שפה ח"ה.

22/12/10

רמז קל לשאלה 7 בתרגיל 4: "לכסון".

07/01/10

תיקון לתרגיל 5 שאלה 5: (תודה לערן)

הרדוקציה שהייתה במצגת של הרצאה 10 (שקף 31) הייתה שגויה (ולכן אני מקווה שנכשלתם בהוכחת נכונותה J).

החלפנו את הרדוקציה באחת אחרת במצגת, אנא הורידו מחדש את המצגת וודאו שאתם מוכיחים נכונות של הרדוקציה הנכונה.

09/01/10

בנושא "NP=P?", אנו ממליצים לקרוא ולצפות בלינקים הבאים:

http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf

http://video.google.com/videoplay?docid=2727170905577830475#

23/01/10

מצורף קובץ עם הרבה מבחנים קודמים ופתרונות. בהצלחה!

30/01/10

מצורף קובץ עם ציוני התרגילים עד תרגיל 5. אנא ודאו שהציונים שלכם הוזנו כהלכה.

02/02/10

מצורפות הוראות לבחינה (העמוד הראשון של הטופס).

מצורף קובץ עם ציוני כל התרגילים.

12/12/10

מצורף טופס המבחן (מועד א) וסקיצת פתרון

23/09/11

את מועד ב' ניתן למצוא כאן http://tau-cm.wikidot.com/exam

 

Homework Assignments   -   (Files have been removed. Moed B students, contact Ori if you don't have them)

Assignment

date handed

due date

solution

Remarks

Ex1

26/10/2010

10/11/2010, 14:00

Sol1

 

Ex2

17/11/2010

01/12/2010, 14:00

Sol2

 

Ex3

01/12/2010

15/12/2010, 14:00

Sol3

 

Ex4

15/12/2010

29/12/2010, 14:00

Sol4

19.12 – הוכנס תיקון קטן בשאלה g6

Ex5

29/12/2010

12/01/2011, 14:00

Sol5

 

Ex6

11/01/2011

30/01/2011, 14:00

Sol6

We gave 1 week extensions.

But, there won't be any more extensions…


Your solution should be handed to the grader's mail box at the time and date specified. You can collect your checked home assignments from room 114.

 

Course Timetable

Week

Subject

Reference(s)

Lecture Slides*

1

Administratrivia. Some mathematical preliminaries. Finite automata. Regular languages. Closure properties: Union.

Sipser 0, 1.1

slides

2

Non-Deterministic Finite Automata (NFA). Closure properties of Regular Languages.
Regular expressions.

Sipser 1.1-1.3

slides

3

Regular expressions and their equivalence with finite automata via generalized NFAs. The Pumping Lemma.

Sipser 1.3, 1.4, 2.1-2.2

slides

4

Canceled

5

Myhill-Nerode Theorem, Context free grammars. Closure under union, concatenation, and star. Linear grammars. Ambiguity. CFL pumping lemma. Non context free languages.

Hopcroft and Ullman 3.4

Sipser 2.1- 2.3

slides updated on 14/11

6

Chomsky normal form of CFGs. More CFL closure properties. Some algorithmic questions for CFGs. Push-down automata. Equivalence of Context Free Grammars and Push down automata.

Sipser 2.1-2.3

slides uploaded on 23/11

(Note corrections in slides 33-39)

7

Turing Machines and alternative Models of Computers, Non Deterministic TMs.

The language classes R, RE and coRE.

Sipser 3.1-3.3

slides uploaded on 28/11

8

The language classes R, RE and coRE. What is an algorithm? The Church-Turing Thesis. Hilbert's tenth problem. Encoding of Turing Machines. Universal Turing Machine. The acceptance problem. Diagonalization.

Sipser 3.3,4.1,4.2

slides uploaded on 04/12

9

Review of Diagonalization. The acceptance and halting problems are undecidable 
Computable functions. Additional Undecidable Languages, Reductions among languages, Mapping reductions.

Sipser 4.1,4.2,5.1, 5.3

slides updated on 13/12

10

Undecidability by Rice Theorem. Reduction by computational histories.

Sipser 5.1,5.3

slides updated on 21/12

11

More reductions by computational histories. Post Correspondence Problem is undecidable. Introduction to Complexity.

Sipser 5.1, 5.3, 7.1

slides updated on 07/01

12

The classes P, NP. Examples of Problems in P and NP. Verifiability.

Sipser 7.2, 7.3

slides updated on 04/01

13

Poly-Time Reductions. NP completeness. Cook-Levin Theorem.

Sipser 7.3,7.4,7.5

slides updated on 09/01

14

Additional NP-complete problems.

Sipser 7.5

slides updated on 15/01

* We try to upload the slides in advance, but note that the slides file is replaced with an updated one after the lecture.

 


Course requirements and important information:

·         We will publish 6 homework assignments.

Assignment submission is usually due two weeks after publishing.

Late submission will be allowed only given proper approval (note from a doctor, etc.)

External sources (books, web pages) can be used but should be clearly quoted.

Solving assignments independently is crucial and is strongly encouraged.

 

·         To pass the course, one has to pass the exam.

 

·         The final grade is calculated as follows:

If  (number of submitted homework assignments ³ 5) and (average of 5 best homework grades > exam grade) then

final grade = 0.9 * exam grade + 0.1* average of 5 best homework grades

            Else

final grade = exam grade

 

 

Course Outline The course deals with fundamental questions of computer science:

  • What is a computer?
  • What can computers do (and what can they not do)?
  • Why are some problems computationally hard, while very similar ones are computationally easy?

 

These questions were mostly raised during the 20th century, and they accompanied and guided the actual development of computers.

Many of these and related questions were resolved, but some (especially those dealing with computational hardness) retained their status as "key open problems" into the 21st century.

 

 

Prerequisites  The course is a required course for Computer Science students, and "extended intro to Computer Science" is a prerequisite.

"Discrete Math" is recommended, though not required. Students from other disciplines are encouraged to contact the lecturer.

 

Textbook                    Introduction to the Theory of Computation, M. Sipser, PWS Publishing Co.,  1997 (second edition, 2005).

Reference Books       Introduction to Automata Theory, Languages, and Computation, J. Hopcroft and J. Ullman, Addison-Wesley Publishing Co., 1979.

Computational Complexity, C. Papadimitriou, Addison-Wesley Publishing Co.,  1994.

Elements of the Theory of Computation, H. Lewis and C. Papadimitriou, Prentice-Hall, 1981.

Automata and formal languages, the open university (in Hebrew) , 1991.