Theoretische Informatik: Automaten und formale Sprachen

Wintersemester 2019/20

bei Prof. Dr. Sibylle Schwarz

Pflichtmodul 3010 im 3. Semester Bachelor Informatik,
Wahlpflichmodul für Bachelor Medieninformatik

Prüfung

Klausur (90 min) am Freitag, dem 14. Februar 2020 um 11:00-12:30 Uhr in N001

(einzige) zugelassene Hilfsmittel: ein A4-Blatt beidseitig handbeschrieben

Zur Prüfung ist zugelassen, wer in diesem Semester alle drei folgenden Voraussetzungen erfüllt:

mindestens drei Punkte für Kurzvorträge zu Hausaufgaben (Vorrechnen) in verschiedenen Übungen seiner Gruppe
wenigstens 12 Punkte für Autotool-Pflichtaufgaben
wenigstens 36 Punkte für rechtzeitig in Opal eingesendete sinnvolle Lösungen zu Pflichtaufgaben

Ob Sie in diesem Semester die Prüfungszulassung erworben haben, finden Sie im OPAL-Kurs.

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 Student ist einer Übungsgruppe zugeordnet und nimmt an der wöchentlich stattfindenden Übung dieser Gruppe teil.

In den Übungen werden vorwiegend die Lösungen der schriftlichen Hausaufgaben besprochen und damit die Zulassungen zur Prüfung erworben.

Übungsaufgaben

Serie 0 bis 21. 10. 2019 (nicht in Opal einzusenden)
Serie 1 bis 23. 10. 2019, nur Aufgaben 1 - 4 in Opal einzusenden
Serie 2 bis 3. 11. 2019
Serie 3 bis 6. 11. 2019
Serie 4 bis 13. 11. 2019
Serie 5 bis 20. 11. 2019
Serie 6 bis 27. 11. 2019 (ab jetzt Selbsttest-Aufgaben nicht in OPAL einsenden, werden aber in Übungen besprochen)
Serie 7 bis 4. 12. 2019
Serie 8 bis 11. 12. 2019
Serie 9 bis 18. 12. 2019
Serie 10 bis 8. 1. 2020
Serie 11 bis 15. 1. 2020
Serie 12 bis 22. 1. 2020
Serie 13 bis 26. 1. 2020 (Einsendung in Opal bis 26.1.2020 freiwillig)

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 2018/19 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 2009
Rolf Socher: Theoretische Grundlagen der Informatik, Hanser 2008
Ulrich Hedtstück: Einführung in die Theoretische Informatik, Oldenbourg 2007
Gottfried Vossen, Kurt-Ulrich Witt: Grundkurs Theoretische Informatik, Vieweg 2006
Alexander Asteroth, Christel Baier: Theoretische Informatik. Eine Einführung in Berechenbarkeit, Komplexität und formale Sprachen, Pearson 2002
Renate Winter: Theoretische Informatik, Oldenbourg 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.

http://www.imn.htwk-leipzig.de/~schwarz mailto:sibylle.schwarz@htwk-leipzig.de