Theory of Computation  237343





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
    Theory of Computation 
236343
 

Incorporated Courses
    Introduction to Computability 
094250
 

Identical Courses
    Design and Analysis of Algorithms 
046002
 
    Intro. to Computability and Complexity 
097447
 
    Theory of Computation C 
106843
 
    Computational Models for Teachers 
214912
 
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 NpCompleteness, Cook'S Theorem._
Learning Outcomes
By the End of the Course, the Student Will:
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. Undersand and Apply the Concept of Reduction Between Problems.
TextbooksCompulsory Book  Published  Publisher  Authors  Book 

Compulsory  1996  course technology (1st edition)  michael sipser  introduction to the theory of computation 
 2000  pearson addison wesley  john e. hopcroft, rajeev motwani, john e. hopcroft, rajeev motwani,  introduction to automata theory, languages and computation (2nd edition ). 
 1979  wh freeman and co.  michael r. garey, david s. johnson  computers and intractability: a guide to the theory of npcompleteness 
 1994   christors h. papadimitriou  computational complexity addisonwesley pub co. 
Created in 08/12/2022 Time 11:26:08