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.