Recursive and Primitive Recursive Functions, Turing Machines. Equivalence Between Several Models, Church's Thesis, Universal Machine, Undecidable Problems, Deterministic and Nondeterministic Machines, The Class P and Np-completeness, Cook's Theorem. Learning Outcomes# at The End of The Course The Students Will Know# 1. Be Familiar With Models of Computation, in Particular The Turing Machine Model. 2. Distinguish Between Decidable and Undecidable Problems. 3. Be Familiar With The Concept of Efficient Computation (in Time Or Memory), and Be Able to Classify Problems Into Those That Can Be Solved Efficiently Or That Are "computationally Hard". 4. Understand and Apply The Concept of Reduction Between Problems.

Faculty: Computer Science
|Graduate Studies
Pre-required courses

234247 - Algorithms 1

Course with no extra credit

46002 - Design and Analysis of Algorithms 97447 - Intro. to Computability and Complexity 106843 - Theory of Computation C 214912 - Computational Models For Teachers 237343 - Theory of Computation

Course with no extra credit (contained)

94250 - Introduction to Computability

Semestrial Information

Weekly Hours

3 Academic Credit • 2 Lecture Hours • 1 Discussion Hours • 1 Project Hours

Go to Course Page

Go to Course Page


Responsible(s)

Eyal Kushilevitz


Exams
Session A: 27-08-2024 Session B: 30-09-2024
Quizzes
Session A: 29-07-2024
Registration Groups
11
Lecture Tuesday 10:30 - 12:30 אמדו 233 | Eyal Kushilevitz
Exercise Sunday 15:30 - 16:30 אולמן 506 | Adam Nice
12
Lecture Tuesday 10:30 - 12:30 אמדו 233 | Eyal Kushilevitz
Exercise Monday 14:30 - 15:30 אולמן 501 | Tomer Gewirtzman
13
Lecture Tuesday 10:30 - 12:30 אמדו 233 | Eyal Kushilevitz
Exercise Tuesday 15:30 - 16:30 אולמן 506 | Rotem Shavit
14
Lecture Tuesday 10:30 - 12:30 אמדו 233 | Eyal Kushilevitz
Exercise Wednesday 14:30 - 15:30 אולמן 801 | Ido Rafael
21
Lecture Wednesday 10:30 - 12:30 אולמן 802 | Eyal Kushilevitz
Exercise Thursday 12:30 - 13:30 אולמן 703 | Neta Dafni
69
Enrollment Group No information regarding course hours
Weekly Hours

3 Academic Credit • 2 Lecture Hours • 1 Discussion Hours • 1 Project Hours

Go to Course Page

Go to Course Page


Responsible(s)

Yuval Ishai

Notes
  • קבוצה 77 מיועדת לסינים בלבד.

Exams
Session A: 18-04-2024 09:00 - 12:00
  • אולמן 307. 500. 501. 502. 503. 504. 505. 506. 507. 600. 601. 603.
Session B: 20-05-2024 13:00 - 16:00
  • אולמן 100. 103. 104. 105. 200. 201. 203. 205. 206. 300. 301. 305. 307.

Quizzes
Session A: 03-03-2024 17:30 - 19:30
  • אולמן 604, 606, 700, 701, 704, 706, 707, 708, 800, 802, 803, 804, 805, 806,

Registration Groups
11
Lecture Sunday 12:30 - 14:30 טאוב 1 | Yuval Ishai
Exercise Monday 12:30 - 13:30 טאוב 7 | Tomer Gewirtzman
12
Lecture Sunday 12:30 - 14:30 טאוב 1 | Yuval Ishai
Exercise Wednesday 11:30 - 12:30 טאוב 9 | Rotem Shavit
13
Lecture Sunday 12:30 - 14:30 טאוב 1 | Yuval Ishai
Exercise Sunday 14:30 - 15:30 טאוב 4 | Neta Dafni
21
Lecture Monday 10:30 - 12:30 טאוב 5 | Yuval Ishai
Exercise Thursday 10:30 - 11:30 טאוב 8 | Ido Rafael
22
Lecture Monday 10:30 - 12:30 טאוב 5 | Yuval Ishai
Exercise Tuesday 14:30 - 15:30 טאוב 7 | Dor Katzelnick
69
Enrollment Group No information regarding course hours
Weekly Hours

3 Academic Credit • 2 Lecture Hours • 1 Discussion Hours • 1 Project Hours

Go to Course Page

Go to Course Page


Responsible(s)

Eyal Kushilevitz


Exams
Session A: 23-07-2023 09:00 - 12:00
  • אולמן 703. 704. 705. 706. 707. 708. 800. 801. 802. 803. 804. 805. 806.
Session B: 11-10-2023 09:00 - 12:00
  • אולמן 500. 505. 507. 600. 601. 602. 603. 604. 605. 606. 607.

Quizzes
Session A: 04-06-2023 17:30 - 19:30
  • אולמן 700, 701, 702, 703, 704, 705, 706, 707, 708, 800, 801, 802, 803, 804, 805, 806,

Registration Groups
11
Lecture Wednesday 10:30 - 12:30 טאוב 2 | Eyal Kushilevitz
Exercise Sunday 15:30 - 16:30 טאוב 7 | Neta Dafni
12
Lecture Wednesday 10:30 - 12:30 טאוב 2 | Eyal Kushilevitz
Exercise Monday 14:30 - 15:30 | Ido Rafael
13
Lecture Wednesday 10:30 - 12:30 טאוב 2 | Eyal Kushilevitz
Exercise Tuesday 15:30 - 16:30 אולמן 301 | Rotem Shavit
14
Lecture Wednesday 10:30 - 12:30 טאוב 2 | Eyal Kushilevitz
Exercise Wednesday 14:30 - 15:30 טאוב 3 | Tomer Gewirtzman
21
Lecture Thursday 10:30 - 12:30 טאוב 3 | Eyal Kushilevitz
Exercise Thursday 12:30 - 13:30 טאוב 3 | Dor Katzelnick
69
Enrollment Group No information regarding course hours