Learning Outcome
(WAS) Die Studierenden erlernen formale Grundlagen der Informatik wie Begriffe, Methoden, Modelle und Arbeitsweisen, (WOMIT) indem Sie Probleme abstrahieren und modellieren, etwa mithilfe logischer und algebraischer Kalküle, graphentheoretischer Notationen, formalen Sprachen und Automaten. (WOZU) um den algorithmischen Kern von Problemen identifizieren, passende Algorithmen entwerfen und implementieren, sowie bestehende Umsetzungen auf ihre Eigenschaften hin untersuchen zu können.
Inhalte
Grundlagen
- Mengen, Relationen, Graphen
- Zahlensysteme, Zahlendarstellung, Numerische Aspekte
Logik und Boolesche Algebra
- Aussagenlogik
- Prädikatenlogik
- Boolesche Algebra
Reguläre Sprachen
- Endliche Automaten
- Reguläre Ausdrücke
- Reguläre (Typ-3) Grammatiken, Syntaxdiagramme
- Chomsky-Hierarchie
Kontextfreie Sprachen
- Kontextfreie (Typ-2) Grammatiken, Chomsky- und Greibach-Normalformen
- Anwendungen (Ableitungs- und Syntaxbäume, Syntax von Programmiersprachen, Backus-Naur-Form)
Kontextsensitive und rekursiv aufzählbare Sprachen
- Kontextsensitive (Typ-1) und Phrasenstruktur- (Typ-0) Grammatiken, Monotonie, Normalform
Berechenbarkeit, Entscheidbarkeit und Komplexität
- Turing-Maschinen, Turing-Berechenbarkeit
- Entscheidbarkeit, rekursive Aufzählbarkeit
- Komplexität
Empfohlene Literatur
- Hoffmann, D. (2018): Theoretische Informatik, 4. Auflage, Carl Hanser Verlag München.
- Hedtstück, U. (2004): Einführung in die Theoretische Informatik. Oldenbourg, München.
- Kelly, J. (2003): Logik. Pearson Studium, München.
- Ehrig, H. et al. (1999): Mathematisch-strukturelle Grundlagen der Informatik. Springer, Heidelberg.
- Beuth, K. (1992): Digitaltechnik. 9. Auflage, Vogel, Würzburg.