CENG565 INTRODUCTION TO THEORY OF COMPUTATION
| Course Code: |
5710565 |
| METU Credit (Theoretical-Laboratory hours/week): |
3(3-0) |
| ECTS Credit: |
8.0 |
| Department: |
Computer Engineering |
| Language of Instruction: |
English |
| Level of Study: |
Graduate |
| Course Coordinator: |
Prof.Dr. FARUK POLAT |
| Offered Semester: |
Fall or Spring Semesters. |
Course Content
Turing machines. Church-Turing thesis. Decidability. Reducibility and Recursion Theorem. Complexity theory: Classes P and NP, NP-Completeness. Space Complexity. Intractability.
