Theoretische Informatik: Automaten und formale Sprachen
Wintersemester 2020/21
bei Prof. Dr. Sibylle Schwarz
Pflichtmodul C993
im 3. Semester Bachelor Informatik,
Wahlpflichmodul für Bachelor Medieninformatik
Lernziele / Kompetenzen
Die Studierenden sind in der Lage, wichtige Klassen formaler Sprachen als Grundlage von
Programmier- und Beschreibungssprachen einzuordnen und kennen die wesentlichen Eigenschaften
der Sprachklassen.
Sie kennen die entsprechenden abstrakten Maschinenmodelle und Algorithmen und können sie zur
Darstellung und Lösung praktischer Aufgabenstellungen einsetzen. Die Studierenden wissen, dass nicht jedes formal darstellbare Problem algorithmisch lösbar ist.
Inhalt
- Formale Sprachen und verschiedene Darstellungsformen dafür
- reguläre Ausdrücke
- Wortersetzungssysteme und Grammatiken
- Chomsky-Hierarchie
- Pumping Lemmata für reguläre und kontextfreie Sprachen
- Abschlusseigenschaften verschiedener Sprachklassen
- abstrakte Maschinenmodelle:
- endliche Automaten (NFA, DFA, ...)
- Kellerautomaten (PDA)
- linear beschränkte Automaten (LBA)
- Turingmaschinen
- Ausblick auf Grenzen der Berechenbarkeit
Vorlesung
Wöchentlich findet eine Vorlesung statt.
Übungen
Jeder Teilnehmer
nimmt an der wöchentlich online synchron stattfindenden Übung teil.
In den Übungen werden vorwiegend die Lösungen der schriftlichen
Hausaufgaben besprochen und damit die Zulassungen zur Prüfung
erworben.
Übungsaufgaben
Das Selbststudium zum Modul besteht aus
- Vor- und Nachbereitung
- jeder Vorlesung und Übung,
- praktischen Übungsaufgaben:
- wöchentlich als Hausaufgaben im
Autotool zu bearbeiten.
- schriftlichen Übungsaufgaben:
- wöchentlich als Hausaufgaben im
Opal-Kurs
zum Modul einzusenden.
Nicht rechtzeitig dort eingesendete Lösungen der schriftlichen Aufgaben können nicht gewertet werden.
Praktische Übungsaufgaben gibt es als Hausaufgaben im
Autotool.
Literaturempfehlungen
Zusammenfassung,
alle Folien
Die vollständigen Unterlagen zum Modul
Theoretische Informatik: Automaten und formale Sprachen
im WS 2019/20 stehen
hier.
Bücher:
- Uwe Schöning:
Theoretische Informatik - kurzgefasst, Spektrum 2001
- John E. Hopcroft, Jeffrey D. Ullman:
Einführung in die Automatentheorie, Formale Sprachen und
Komplexitätstheorie, Addison-Wesley 1990
- Dirk W. Hoffmann:
Theoretische Informatik, Hanser 2018
- Ulrich Hedtstück: Einführung in die Theoretische Informatik
Formale Sprachen und Automatentheorie, Oldenbourg 2012
- Lukas König, Friederike Pfeiffer-Bohnen, Hartmut Schmeck:
Theoretische Informatik – ganz praktisch, De Gruyter 2016
- Heinz-Peter Gumm, Manfred Sommer
Informatik – Band 3: Formale Sprachen, Compilerbau,
Berechenbarkeit und Komplexität, De Gruyter 2019
- Gottfried Vossen, Kurt-Ulrich Witt:
Grundkurs Theoretische Informatik, Vieweg 2006
- Renate Winter: Theoretische Informatik, Oldenbourg 2002
- Rolf Socher:
Theoretische Grundlagen der Informatik, Hanser 2008
- Alexander Asteroth, Christel Baier:
Theoretische Informatik. Eine Einführung in Berechenbarkeit,
Komplexität und formale Sprachen, Pearson 2002
Unter
http://wilfridhodges.co.uk/cognitive01.pdf
gibt es sieben uneingeschränkt richtige Hinweise zum Lernen von Mathematik, die
selbstverständlich genauso für die theoretische Informatik gelten.
https://informatik.htwk-leipzig.de/schwarz
mailto:sibylle.schwarz@htwk-leipzig.de