Theoretische Informatik
Grundlagen der Theoretischen Informatik (Informatik IV)
Studiengang
Bachelor-Studiengang Informatik
Leistungspunkte
10 LP
Lehrveranstaltungen
- Vorlesung „Grundlagen der Theoretischen Informatik“, 4 SWS,
Di. 08.30 - 10, Hörsaal 5E + Fr. 12.30 - 14, Hörsaal 5F - Übung, 2 SWS, nach Vereinbarung
Inhalte
- Formale Sprachen und Automaten
- Grundbegriffe
- Wörter, Sprachen und Grammatiken
- Die Chomsky-Hierarchie
- Reguläre Sprache
- Endliche Automaten
- Reguläre Ausdrücke
- Gleichungssysteme
- Das Pumping-Lemma
- Satz von Myhill und Nerode und Minimalautomaten
- Abschlusseigenschaften regulärer Sprachen
- Charakterisierungen regulärer Sprachen
- Kontextfreie Sprache
- Normalformen
- Das Pumping-Lemma
- Der Satz von Parikh
- Abschlusseigenschaften kontextfreier Sprachen
- Der Algorithmus von Cocke, Younger und Kasami
- Kellerautomaten
- Deterministisch kontextfreie Sprachen
- Deterministische Kellerautomaten
- LR(k)- und LL(k)-Grammatiken
- Anwendung: Syntaxanalyse durch LL(k)-Parser
- Kontextsensitive und L0-Sprachen
- Turingmaschinen
- Linear beschränkte Automaten
- Zusammenfassung
- Berechenbarkeit
- Intuitiver Berechenbarkeitsbegriff und die These von Church
- Turing-Berechenbarkeit
- LOOP-, WHILE- und GOTO-Berechenbarkeit
- LOOP-Berechenbarkeit
- WHILE-Berechenbarkeit
- GOTO-Berechenbarkeit
- Primitiv rekursive und partiell rekursive Funktionen
- Primitiv rekursive Funktionen
- Die Ackermann-Funktion
- Allgemein und partiell rekursive Funktionen
- Der Hauptsatz der Berechenbarkeitstheorie
- Entscheidbarkeit und Aufzählbarkeit
- Einige grundlegende Sätze
- Entscheidbarkeit
- Rekursiv aufzählbare Mengen
- Unentscheidbarkeit
- Der Satz von Rice
- Reduzierbarkeit
- Das Postsche Korrespondenzproblem
- Unentscheidbarkeit in der Chomsky-Hierarchie
- Zusammenfassung
Lernergebnisse/Kompetenzen
Ziel der Veranstaltung Informatik IV ist die Vermittlung von Grundlagenwissen aus den Bereichen Formale Sprachen und Automaten sowie Berechenbarkeitstheorie. Am Ende der Veranstaltung sollten Studierende in der Lage sein, formale Sprachen in die Chomsky-Hierarchie einzuordnen, verschiedene äquivalente Automatenmodelle ineinander bzw. in Grammatiken des entsprechenden Typs umzuformen, Argumente für die In-Äquivalenz von bestimmten Automatenmodellen bzw. Grammatiktypen zu geben, die algorithmische Entscheidbarkeit von Problemen einzuschätzen und Argumente für die Nichtentscheidbarkeit von Problemen zu geben. Auch sollten sie die Erkenntnis gewonnen haben, dass es nicht berechenbare Funktionen gibt, und eine Vorstellung vom Aufbau eines Compilers und von lexikalischer und Syntaxanalyse erworben haben. Neben diesen Kenntnissen sollten sie sich auch Fertigkeiten im Umgang mit formalen Begriffs- und Modellbildungen sowie mit formalen Argumentationsweisen sowie bestimmte Beweistechniken (wie etwa Diagonalisierung) angeeignet haben.
Empfohlene Literatur
- Uwe Schöning: Theoretische Informatik kurz gefasst, Spektrum Akademischer Verlag, 2. Auflage, 1995.
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Pearson Studium, 2. Auflage, 2002.
- Klaus W. Wagner: Theoretische Informatik. Eine kompakte Einführung, Springer-Verlag, 2. Auflage, Berlin, Heidelberg, 2003.
Ergänzende Literatur
- Norbert Blum: Theoretische Informatik. Eine anwendungsorientierte Einführung, Oldenbourg, 2001.
- Alexander Asteroth, Christel Baier: Theoretische Informatik. Eine Einführung in Berechenbarkeit, Komplexität und formale Sprachen mit 101 Beispielen, Pearson Studium, 2002.
Verwendbarkeit des Moduls
- Bachelor-Studiengang Informatik (Pflichtbereich)
- Master-Studiengang Mathematik (Nebenfach)
Teilnahmevoraussetzungen
Keine
Voraussetzungen für die Vergabe von Kreditpunkte
- erfolgreiche Bearbeitung der Übungsaufgaben
- Bestehen der schriftlichen Prüfung (Klausur)
Häufigkeit des Angebots, modulare Schiene
Jedes Sommersemester
Modulbeauftragte und hauptamtliche Lehrende
Prof. Dr. Michael Leuschel, Prof. Dr. Jörg Rothe, Jun.-Prof. Dr. Dorothea Baumeister