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
|Undergraduate Studies |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)

Gadi Aleksandrowicz


Exams
Session A: 20-07-2022 Session B: 22-09-2022
Quizzes
Session A: 24-05-2022
Registration Groups
11
Lecture Sunday 12:30 - 14:30 טאוב 1 | Gadi Aleksandrowicz
Exercise Sunday 15:30 - 16:30 טאוב 7 | גב. דפני נטע
12
Lecture Sunday 12:30 - 14:30 טאוב 1 | Gadi Aleksandrowicz
Exercise Monday 14:30 - 15:30 טאוב 5 | Chiara Meiohas
13
Lecture Sunday 12:30 - 14:30 טאוב 1 | Gadi Aleksandrowicz
Exercise Tuesday 15:30 - 16:30
14
Lecture Sunday 12:30 - 14:30 טאוב 1 | Gadi Aleksandrowicz
Exercise Thursday 12:30 - 13:30 אולמן 705 | Victor Kolobov
21
Lecture Tuesday 10:30 - 12:30 טאוב 1 | מר טלמון אוהד
Exercise Wednesday 14:30 - 15:30 טאוב 6 | גב. דפני נטע
22
Lecture Tuesday 10:30 - 12:30 טאוב 1 | מר טלמון אוהד
Exercise Wednesday 10:30 - 11:30 טאוב 3 | מר קצלניק דור
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


Exams
Session A: 31-01-2022 13:00 - 16:00
  • אולמן 100. 102. 103. 104. 105. 201. 202. 203. 205. 206.
  • אמדו 231. 233. 234.
  • טאוב 3. 4. 5. 6. 7. 8. 9.
Session B: 27-02-2022 13:00 - 16:00
  • אולמן 507. 600. 601. 602. 603. 604. 605. 606. 607. 700. 701. 702. 703. 704. 705. 706. 707. 708. 805. 806.
Session C: 20-03-2022 17:00 - 20:00
  • אולמן 100. 105. 200. 201. 202. 203. 205. 206. 308.

Quizzes
Session A: 02-01-2022 17:30 - 19:30
  • אולמן 601, 603, 604, 607, 701, 703, 704, 705, 801, 802, 803, 804, 805,

Registration Groups
11
Lecture Monday 10:30 - 12:30 טאוב 2 | Yuval Ishai
Exercise Monday 12:30 - 13:30 אולמן 307 | Victor Kolobov
12
Lecture Monday 10:30 - 12:30 טאוב 2 | Yuval Ishai
Exercise Wednesday 11:30 - 12:30 טאוב 5 | מר קצלניק דור
13
Lecture Monday 10:30 - 12:30 טאוב 2 | Yuval Ishai
Exercise Sunday 14:30 - 15:30 טאוב 7 | גב. דפני נטע
14
Lecture Monday 10:30 - 12:30 טאוב 2 | Yuval Ishai
Exercise Thursday 10:30 - 11:30 טאוב 6 | Chiara Meiohas
21
Lecture Sunday 12:30 - 14:30 טאוב 2 | Yuval Ishai
Exercise Tuesday 14:30 - 15:30 אמדו 231 | Ido Rafael
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

Notes
  • בקורס ייאכפו דרישות קדם וצמודים המתפרסמים באתר לימודי הסמכה.

Exams
Session A: 21-07-2021 09:00 - 12:00
  • אולמן 500. 501. 502. 503. 504. 600. 601. 602. 603. 604. 605. 606. 607.
Session B: 10-10-2021 13:00 - 16:00
  • אולמן 101. 102. 103. 104. 105. 300. 302. 303. 304. 305. 306. 307. 309. 310. 311. 502. 505.

Quizzes
Session A: 23-05-2021 17:30 - 19:30
  • אולמן 500, 501, 502, 503, 504, 505, 506, 600, 601, 602, 603, 604, 605, 606, 607, 800, 801, 802, 803,

Registration Groups
11
Lecture Tuesday 10:30 - 12:30 טאוב 6 | Eyal Kushilevitz
Exercise Sunday 15:30 - 16:30 | Victor Kolobov
12
Lecture Tuesday 10:30 - 12:30 טאוב 6 | Eyal Kushilevitz
Exercise Monday 14:30 - 15:30 טאוב 6 | גב. דפני נטע
13
Lecture Tuesday 10:30 - 12:30 טאוב 6 | Eyal Kushilevitz
Exercise Tuesday 15:30 - 16:30 | Ido Rafael
14
Lecture Tuesday 10:30 - 12:30 טאוב 6 | Eyal Kushilevitz
Exercise Thursday 12:30 - 13:30 טאוב 6 | Chiara Meiohas
21
Lecture Sunday 12:30 - 14:30 טאוב 2 | Eyal Kushilevitz
Exercise Wednesday 14:30 - 15:30 חומרים 303 | גב. דפני נטע
22
Lecture Sunday 12:30 - 14:30 טאוב 2 | Eyal Kushilevitz
Exercise Wednesday 10:30 - 11:30 טאוב 4 | מר קצלניק דור
69
Enrollment Group No information regarding course hours