Computability and Complexity
|Flow||L - Computer Software|
|Category||Obligatory by selection|
|Class Hours - Lab Hours||3 - 0|
|Lecturers||Stathis Zachos, Petros Potikas (T & R Associates)|
|Links||Helios, Course's Website|
Computability: Logical foundation of computer science, historical overview about the problem of decidability of mathematical propositions, solvability or computability of problems with an effective, i.e. algorithmic, way. Simple equivalent computational models: Turing machines, WHILE programs. Induction and recursion, encodings and semantics. Fix-point theory. Arithmetical hierarchy.
Complexity: Relations among complexity classes. Reductions and completeness. Oracles. Polynomial hierarchy. Probabilistic, interactive and counting classes. Advanced topics of formal grammar theory. Applications to the syntax of programming languages.