Subject: Subject Sylbus: Intro. to Computability and Complexity - 097447 (Previous)

Intro. to Computability and Complexity - 097447
Credit
Points
2.5
 
Given In
Semester
b
 
  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
 
Identical Courses Theory of Computation 237343


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. 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.




Times and places of examinations 02/2021 2021/2022 Spring Semester סמסטר Previous
Roombuildingexamination timedaydateSeason
703
705
706
707
708
801
802
803
804
805
806
Ullman
Ullman
Ullman
Ullman
Ullman
Ullman
Ullman
Ullman
Ullman
Ullman
Ullman
13:00-16:00Tuesday02.08.2022א
214
215
216
151
152
נהול
נהול
נהול
בלומפילד
בלומפילד
17:00-20:00Monday24.10.2022ב

Timetable to semester 02/2021 2021/2022 Spring Semester semester Previous
RoomBuildingHourdayLecturerExercise
Lecture
no.Registering
Group
1Sego16:30-18:30WednesdayProf. Strichman OferLecture1011
234אמדו15:30-16:30WednesdayMr Gil YuvalExercise11
 
1Sego16:30-18:30WednesdayProf. Strichman OferLecture1012
216נהול17:30-18:30TuesdayMr Solomon MatanExercise12
 
1Sego16:30-18:30WednesdayProf. Strichman OferLecture1013
214נהול18:30-19:30MondayMr Gutman OferExercise13
 
1Sego16:30-18:30WednesdayProf. Strichman OferLecture1014
215נהול12:30-13:30ThursdayMr Gutman OferExercise14
 
1Sego16:30-18:30WednesdayProf. Strichman OferLecture1015
215נהול08:30-09:30WednesdayMr Solomon MatanExercise15
 
    Prof. Strichman OferLecture6069
     Exercise69


Textbooks
PublishedPublisherAuthorsBook
1998prentice-hallh.r. lewis, and c.h. papadimitriouelements of the theory of computation (2nd ed.)
2013cengage learningmichael sipserintroduction to the theory of computation, 3rd edition

Created in 08/12/2022 Time 10:53:52