Subject: Subject Sylbus: Theory of Computation - 236343 (Current)

Theory of Computation - 236343
Credit
Points
3.0
Given In
Semester
a+b
Lecture Exercise Laboratory Project or
Seminar
House
Work
Weekly
Hours
2 1 1 6

Determination of the grade according to progress during the semester and a final examination.


Prerequisites Algorithms 1 234247
Overlapping Courses Design and Analysis of Algorithms 046002
Theory of Computation C 106843
Computational Models for Teachers 214912
Theory of Computation 237343
Intro. to Computability and Complexity 097447
Incorporated Courses Introduction to Computability 094250


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.




Times and places of examinations 01/2022 2022/2023 Winter Semester
Roombuildingexamination timedaydateSeason
203
205
206
300
301
303
304
307
308
309
310
311
500
501
503
504
Ullman
Ullman
Ullman
Ullman
Ullman
Ullman
Ullman
Ullman
Ullman
Ullman
Ullman
Ullman
Ullman
Ullman
Ullman
Ullman
13:00-16:00Sunday05.02.2023
Tuesday28.02.2023

Timetable to semester 01/2022 2022/2023 Winter Semester
RoomBuildingHourdayLecturerExercise
Lecture
no.Registering
Group
112:30-14:30SundayProf. Yuval IshaiLecture1011
Project11
912:30-13:30MondayExercise11
112:30-14:30SundayProf. Yuval IshaiLecture1012
Project12
11:30-12:30WednesdayExercise12
112:30-14:30SundayProf. Yuval IshaiLecture1013
Project13
514:30-15:30SundayExercise13
311Ullman10:30-12:30MondayProf. Yuval IshaiLecture2021
Project21
310:30-11:30ThursdayExercise21
311Ullman10:30-12:30MondayProf. Yuval IshaiLecture2022
Project22
414:30-15:30TuesdayExercise22
Prof. Yuval IshaiLecture6069
Project69
Exercise69


System of hours to the semesters
Semester Previous Semester information 02/2021 2021/2022 Spring Semester

Created in 08/12/2022 Time 11:02:43