Class Description

Course_ID: MYE 036

Weekly Hours: 5

Semester: >=6

ECTS Credits: 5

Course Homepage: http://www.cse.uoi.gr/~cnomikos/courses/cc/cc-main.htm

Description: Computational problems and formal languages.

Primitive recursive functions.

Recursive functions.

Turing machines and equivalent models of computation.

Church’s Thesis.

Kleene normal form.

Unsolvability.

Recursive and recursively enumerable sets.

The arithmetic hierarchy.

Non-deterministic Turing machines.

Complexity classes.

The classes P, NP and PSPACE.

Reductions and Completeness.

NP-complete problems.

Grammars and the Chomsky Hierarchy.