Computer Science
Tel-Aviv University

Computational Models

0368.2200

Winter 2012/13

Lecture 

Monday 13:00-16:00, Orenstein 111

Instructor 

Nachum Dershowitz | Schreiber 218 

Recitations 

Wednesday 14:00-15:00, Schreiber 006

Wednesday 15:00-16:00, Schreiber 006

T.A 

Mariano Schain  

Office Hours: Schreiber Open Space, Wednesday 10am-11am



Requirements
  • Attendance is mandatory.
  • Homeworks (done individually) - 10 points.
  • Midterm - 15 points.
    • Quiz Grades
  • Surprise quizzes (Bonus) - 5 points.
  • Final test - 75 points.
    • Exam
Prerequisites
 Extended introduction to CS.

Recommended Reading

Textbooks

Main references:
  • [1] Nachum Dershowitz, Models of Computation (Draft).
    		•
  • [2] John E. Savage, Models of Computation .
    		•

    Other textbooks:
  • M. Sipser, Introduction to the Theory of Computation, PWS Publishing Co., 1997 (second edition, 2005).
    		•
  • C. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Co., 1994.
    		•
  • H. Lewis and C. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1981.
    		•
  • J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing Co., 1979.
    		•
  • אוטומטים ושפות פורמליות, האוניברסיטה הפתוחה, 1991
    • Useful Links

  • Previous year course materials can be found here and here.
    		•
  • Alan Turing.
    •


    Announcements


    Homework assignments


    Previous Exams

    and some solutions can be found here


    Schedule

    Date

    Class Topic

    Notes

    References

    Oct 22

    Administratrivia. 

    What is an algorithm? What can and cannot be done?

    The Busy Beaver Problem. The Halting Problem.

    Cardinality argument, Alan Turing.

  • L1

    		•

    [1] 1.1-2, 5.3, 17.2

  • 2012, Lecture 1

  • 2012, Lecture 2

  • 2009, Lecture 8

  • 2011, Lecture 1

    		•

    Oct 29

    weak languages, oracles,

    interpreters, steppers and computation-history-checkers

  • L2

    		•

    [1] 12.1-3, 12.6, 16.4, 17.6, 21.1

  • 2012, Lecture 4

  • 2009, Lecture 9

    • Nov 5

    Decision Problems as Language Recognition Problems

    Reductions, Rice Theorem

  • L3

    		•

    [1] 15.1-2, 10

  • 2012, Lecture 3

  • 2009, Lecture 8

  • 2009, Lecture 9

    • Nov 12

    Equivalence of models

  • L4

  • TM.scm

  • tm.pdf

  • ram.pdf

    		•

    [1] 6.2, 19.1-5

  • 2012, Lecture 6

  • 2011, Intro

    • Nov 19

    RE

  • L5

    		•

    [1] 16.1

  • 2012, Lecture 6

    • Nov 26

    Recursion Theorem

    Mapping Reductions

  • L6

    		•

    [1] 16.2, 11, 12.4-5

  • 2012, Lecture 5

    • Dec 3

    Descriptive complexity

  • L7

    		•

    [1] 13

  • 2012, Lecture

    • Dec 10

    Finite Automata, Regular Languages

  • L8

    		•

    Dec 17

    Continued

  • L9

    		•

  • AliceBob

    • Dec 24

    CFGs

  • L10

    		•

    Dec 31

    CFGs Cont. Tiling is Undecidable

  • L11

    		•

    Jan 7

    Computational Complexity. P, NP

  • L12

    		•

    Jan 14

    		 Cook-Levin Theorem, Polynomial Reductions, NP-Completeness

  • NTM.ppt

  • L13

    		•

    Jan 21

  • L14

    		•