Subject: Subject Sylbus: Intro. to Computability and Complexity - 097447

Intro. to Computability and Complexity - 097447
Given In
  Lecture Exercise Laboratory Project or
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.

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

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 30/09/2022 Time 07:01:13