- Sommersemester 2024

Dozent: Dominik Scheder vorname.nachname@gmail.com

Raum: TBA

Zeit: TBA

Grundlegende algorithmische Prinzipien und Datenstrukturen. Binäre Suche. Sortieren. Datenstrukturen zum Finden, Einfügen, Löschen wie Binärbäume und Hashtabellen. Im Verlaufe dieses Teils auch Auseinandersetzung mit mathematischer Beweisfindung und Beweisführung und allgemein formalen Methoden.
Formale Sprachen. Grundlegend geht es um die Frage Wie können wir unendliche Mengen, die in der Computer-Praxis vorkommen (z.B. die Menge aller syntaktisch korrekten Email-Adressen) formal beschreiben, verarbeiten, verstehen? Insbesondere:
- Reguläre Sprachen: reguläre Grammatiken, endliche Automaten, reguläre Ausdrücke. Praktische Anwendung / Programmierprojekt: Syntax-Highlighting von Html-Quelltext.
- Kontextfreie Sprachen: kontextfreie Grammatiken, Kellerautomaten. Methoden für das Parsen von kontextfreien Sprachen: \(LL(k), LR(1)\). Konkrete Parser für konkrete Grammatiken. Programmierprojekt: Auswertung und Umformung von arithmetischen Ausdrücken, z.B. Alltagsnotation (3 + 4) * (2 + 1) in Racket-Style (* (+ 2 1) (+ 3 4)) umformen / Zeichenroboter, der eine primitive Programmiersprache in Svg-Grafik übersetzt (siehe auch Material der Veranstaltungen früherer Jahre)
Allgemeine Modelle für Berechenbarkeit: allgemeine Grammatiken, Turing-Maschinen. Wort-Problem, Universal-Maschine, Unentscheidbarkeit.