Computability: Logic as a Foundation for C.S. Historical overview of decidability for mathematical sentences, of solvability and computability of problems in an effective, i.e. algorithmic way. Simple equivalent models of computation: Turing Machines, WHILE programs. Induction and Recursion, encodings and Semantics. Fix-point theory. Arithmetical Hierarchy. Complexity: Inclusions among Complexity Classes. Reductions and Completeness. Oracles. Polynomial Hierarchy. Probabilistic,Interactive and Counting classes. Advanced topics of the theory of Formal grammars. Applications on the Syntax of programming languages.
- Teacher: Ευστάθιος Ζάχος
- Teacher: Αριστείδης Παγουρτζής
ECTS : 4
Language : el