Intro. to Computability and Complexity  097447
Will be learned this year



Lecture 
Exercise 
Laboratory 
Project or Seminar 
House Work 
Weekly Hours 
2 
1 


2 

Determination of the grade according to progress during the semester and a final examination.
Prerequisites:
    Data Structures and Algorithms 
094224
 

or
   Algorithms 1 
234247
 

Overlapping Courses:
    Theory of Computation 
236343
 

Incorporated Courses:
    Introduction to Computability 
094250
 
The Course Provides An Introduction to Computatbility and Complexity, Including: Deterministic Automaton and Regular Languages, Nondeterministic Automaton, ContextFree Languages and PushDown Automaton, Algorithms on Automata, Turing Machine, and Decidability. in Complexity Theory the Course Covers the Classes P, Np, NpHard, NpComplete, and Pspace. 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, NpC 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.
Times and places of examinations
02/2020
2020/2021 Spring Semester
examination time  day  date  Season 

 Tuesday  27.07.2021  à 
 Friday  22.10.2021  á 
Timetable to semester 02/2020
2020/2021 Spring Semester
Room  Building  Hour  day  Lecturer  Exercise Lecture  no.  Registering Group 

213  Ullman  12:3014:30  Thursday  Full Professor Strichman Ofer  Lecture  10  11 
804  Ullman  14:3015:30  Thursday  Mr. âåèîï òåôø  Exercise  11 

213  Ullman  12:3014:30  Thursday  Full Professor Strichman Ofer  Lecture  10  12 
  11:3012:30  Sunday  Mr. Hess Green Raziel  Exercise  12 

213  Ullman  12:3014:30  Thursday  Full Professor Strichman Ofer  Lecture  10  13 
801  Ullman  15:3016:30  Thursday  Mr. âåèîï òåôø  Exercise  13 
TextbooksPublished  Publisher  Authors  Book 

1998  prenticehall  h.r. lewis, and c.h. papadimitriou  elements of the theory of computation (2nd ed.) 
2013  cengage learning  michael sipser  introduction to the theory of computation, 3rd edition 
Created in 08/03/2021 Time 15:00:56