The Course Provides an Introduction to Computatbility and Complexity, Including# Deterministic Automaton and Regular Languages, Nondeterministic Automaton, Context-free Languages and Push-down Automaton, Algorithms On Automata, Turing Machine, and Decidability. In Complexity Theory The Course Covers The Classes P, Np, Np-hard, Np-complete, and Pspace. Learning Outcome# At The End of The Course The Students 1. Will Know Fundamental Concepts in Computability, Including Automata Theory, Turing Machines, Regular Languages and Decidability. 2. Will Know Fundamental Concepts in Complexity Theory, Including The Major Complexity Classes of P, Np, Np-c and Pspace. 3. Will Know How to Prove Membership of a Problem in a Complexity Class, and How to Prove That a Problem Is Decidable Or Undecidable. 4. Will Be Familiar With The Argument of Why The Number of Decidable Problems Is Countable, Whereas The Number of Undecidable Problems Is Uncountable.

Faculty: Data and Decision Sciences
|Undergraduate Studies |Graduate Studies
Pre-required courses

94224 - Data Structures and Algorithms or 234247 - Algorithms 1

Course with no extra credit

236343 - Theory of Computation 237343 - Theory of Computation

Course with no extra credit (contained)

94250 - Introduction to Computability

Semestrial Information

Weekly Hours

2.5 Academic Credit • 2 Lecture Hours • 1 Discussion Hours

Responsible(s)

Shay Kutten


Exams
Session A: 02-09-2024 Session B: 24-09-2024
Registration Groups
11
Lecture Sunday 16:30 - 18:30 בלומפילד 100 | Shay Kutten
Exercise Sunday 18:30 - 19:30 נהול 216
12
Lecture Sunday 16:30 - 18:30 בלומפילד 100 | Shay Kutten
Exercise Monday 13:30 - 14:30 בלומפילד 527
13
Lecture Sunday 16:30 - 18:30 בלומפילד 100 | Shay Kutten
Exercise Tuesday 13:30 - 14:30 נהול 215
Weekly Hours

2.5 Academic Credit • 2 Lecture Hours • 1 Discussion Hours

Responsible(s)

Shay Kutten


Registration Groups
11
Lecture Sunday 16:30 - 18:30 בלומפילד 100 | Shay Kutten
Exercise Wednesday 17:30 - 18:30 נהול 215 | Matan Solomon
12
Lecture Sunday 16:30 - 18:30 בלומפילד 100 | Shay Kutten
Exercise Tuesday 11:30 - 12:30 נהול 216 | Matan Solomon
13
Lecture Sunday 16:30 - 18:30 בלומפילד 100 | Shay Kutten
Exercise Sunday 18:30 - 19:30 בלומפילד 100 | Ofer Gutman
14
Lecture Sunday 16:30 - 18:30 בלומפילד 100 | Shay Kutten
Exercise Tuesday 16:30 - 17:30 נהול 215 | Ofer Gutman
Weekly Hours

2.5 Academic Credit • 2 Lecture Hours • 1 Discussion Hours

Responsible(s)

Ofer Strichman


Exams
Session A: 02-08-2022 13:00 - 16:00
  • אולמן 703. 705. 706. 707. 708. 801. 802. 803. 804. 805. 806.
Session B: 24-10-2022 17:00 - 20:00
  • נהול 112. 214. 215. 216.
  • בלומפילד 151. 152. 153. 424. 526.

Quizzes
Session A: 18-05-2022 16:30 - 17:30
  • אולמן 100, 103, 105, 200, 201, 202, 203, 205, 206, 300, 302, 304, 305, 306, 307, 308,

Registration Groups
11
Lecture Wednesday 16:30 - 18:30 סגו 1 | Ofer Strichman
Exercise Wednesday 15:30 - 16:30 אמדו 234 | Yuval Gil
12
Lecture Wednesday 16:30 - 18:30 סגו 1 | Ofer Strichman
Exercise Tuesday 17:30 - 18:30 נהול 216 | Matan Solomon
13
Lecture Wednesday 16:30 - 18:30 סגו 1 | Ofer Strichman
Exercise Monday 18:30 - 19:30 נהול 214 | Ofer Gutman
14
Lecture Wednesday 16:30 - 18:30 סגו 1 | Ofer Strichman
Exercise Thursday 12:30 - 13:30 נהול 215 | Ofer Gutman
15
Lecture Wednesday 16:30 - 18:30 סגו 1 | Ofer Strichman
Exercise Wednesday 08:30 - 09:30 נהול 215 | Matan Solomon
69
Enrollment Group No information regarding course hours