After successful completion of the course, students are able to classify formal languages relative to the Chomsky hierarchy, develop and adequately manipulate formal grammars, as well as recognize limits of computability. Moreover successful participants have a deeper understanding of basic concepts of classical logic and formal specification, in particular with respect to the syntax/semantics division. They can formalize relatively complex sentences in classical first order logic and can use the tableau calculus to find formal proofs. Finally, they can judge the partial and/or total correctness of simple programs and evaluate the correctness of rules for correctness proofs.
Specification of of formal languages: regular and context free languages (deepening), Chomsky hierarchy, finite automata (deepening), push-down auomata, Turing machines, computability, problem reduction, elements of complexity theory: P, NP; syntax/semantics division, model structures, terms and boolean expressions, syntax and semantics of a simple programming language, classical propositional and first order logic: logical consequence and implication, concep of a logical calculus, semantic tableaux with and without identity, basic properties of first order logic (undecidability, completeness etc.); reasoning about programs: Hoare calculus
The following information is for the (regular) German track of the course only. If you have to get credits for this course to be admitted for a master program in English, please contact Prof. Agata Ciabatoni <agata@logic.at>.
Die erste Vorlesung zu "Theoretische Informatik und Logik" im WS 2019 findet am Mittwoch 2.10., 15.15 - 16.45, im EI 7 statt.
Anmeldung zur Lehrveranstaltung über TISS zwischen 02.10.2019, 10:00 und 09.10.2019, 23:59
Absolvierung eines Eingangstests im TUWEL-Online-Kurs zwischen 3.10. und 13.10.2019 (nur möglich nach Anmeldung in TISS). Der Eingangstests besteht aus einfachen Fragen zum Stoff der ersten beiden Vorlesungseinheiten, sowie zur Organisation der Lehrveranstaltung.
ECTS breakdown:
- 40 hours: lecture time
- 60 hours: exercises (homework - 4 blocks)
- 20 hours: two verbal examinations (incl. preparation)
- 30 written examination (incl. preparation)
Total: 150 hours