Subject: Subject Sylbus: Theory of Computation - 237343

Theory of Computation - 237343
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 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 Np-Completeness, 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.




Textbooks
Compulsory
Book
PublishedPublisherAuthorsBook
Compulsory1996course technology (1st edition)michael sipserintroduction to the theory of computation
 2000pearson addison wesleyjohn e. hopcroft, rajeev motwani, john e. hopcroft, rajeev motwani,introduction to automata theory, languages and computation (2nd edition ).
 1979wh freeman and co.michael r. garey, david s. johnsoncomputers and intractability: a guide to the theory of np-completeness
 1994 christors h. papadimitrioucomputational complexity addison-wesley pub co.

Created in 08/12/2022 Time 11:26:08