Theoretische Informatik
Modulnummer:
1100670
Leistungspunkte:
9 ECTS
Lehrveranstaltungen:
- Vorlesung Komplexität und Formale Sprachen (2 SWS im Sommer)
- Übung Komplexität und Formale Sprachen (1 SWS im Sommer)
- Vorlesung Formale Methoden der Informatik (3 SWS im Winter)
- Übung Formale Methoden der Informatik (1 SWS im Winter)
Prüfung:
Klausur (120 min) oder mündliche Prüfung (20 min)
Prüfungsvorleistungen:
Lösen von Übungsaufgaben
Inhalt:
Komplexität und Formale Sprachen:
Wir studieren Probleme und lernen sie einzuordnen. Dazu betrachten wir die Hierarchien der Komplexitätstheorie, bei der Probleme nach ihrem Laufzeit- und Speicherbedarf kategorisiert werden sowie die Hierarchie der formalen Sprachen, wo Probleme nach strukturellen Kriterien kategorisiert werden. Die Fähigkeit, ein neues Problem einzuordnen, erleichtert das Verständnis und liefert wiederverwendbare Lösungsansätze.
Formale Methoden der Informatik:
Wir trainieren, Informatik-Inhalte präzise zu definieren und auf geeignetem Abstraktionsgrad darzustellen. Im ersten Teil geht es um die Formalisierung der Semantik, also um die maschinen- und compilerunabhängie Erklärung, was Konstrukte einer Programmiersprache bedeuten. Im zweiten Teil lernen wir verschiedene Methoden und Sprachen kennen, um Systeme formal zu spezifizieren. Die Fertigkeiten helfen Ihnen, Ideen missverständnisfrei zu kommunizieren und zu dokumentieren.