Computability and Complexity
| Code | 3.4.3254.8 |
|---|---|
| Semester | 8th |
| Flow | L - Computer Software |
| Category | Obligatory by selection |
| Credits | 4 |
| Class Hours - Lab Hours | 3 - 0 |
| Lecturers | Nikos Leonardos, Stathis Zachos, Petros Potikas (T & R Associates) |
| Links | Helios, Course's Website |
| Web Platform |
Class 1:
Webex
|
Description
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.