Stud.IP Uni Oldenburg
Universität Oldenburg
21.10.2021 14:48:41
inf401 - Grundlagen der Theoretischen Informatik (Vollständige Modulbeschreibung)
Originalfassung Englisch PDF Download
Modulbezeichnung Grundlagen der Theoretischen Informatik
Modulkürzel inf401
Kreditpunkte 6.0 KP
Workload 180 h
Einrichtungsverzeichnis Department für Informatik
Verwendbarkeit des Moduls
  • Fach-Bachelor Informatik (Bachelor) > Aufbaumodule
  • Fach-Bachelor Mathematik (Bachelor) > Nebenfachmodule
  • Master of Education (Gymnasium) Informatik (Master of Education) > Mastermodule
  • Zwei-Fächer-Bachelor Informatik (Bachelor) > Aufbaumodule (60 KP)
  • Zwei-Fächer-Bachelor Informatik (Bachelor) > Wahlpflicht Theoretische Informatik (30 KP)
Zuständige Personen
Habel, Annegret (Modulverantwortung)
Olderog, Ernst-Rüdiger (Modulverantwortung)
Lehrenden, Die im Modul (Prüfungsberechtigt)
Teilnahmevoraussetzungen
Kompetenzziele
Einführung in die Theorie der Automaten, formalen Sprachen, Berechenbarkeit und Komplexität

Fachkompetenzen
Die Studierenden:
  • kennen verschiedene Sprachklassen (z.B. reguläre und kontextfreie Sprachen)
  • kennen dazugehörige Automatenmodelle (z.B. endliche Automaten, Kellerautomaten, Turingmaschinen)
  • erstellen Automaten,Turingmaschinen und Grammatiken zu gegebenen Aufgaben
  • kennen äquivalente Formalisierungen des Begriffs des Algorithmus
  • weisen Funktionen als algorithmisch berechenbar bzw.
  • Probleme als algorithmisch entscheidbar nach
  • kennen unentscheidbare Probleme
  • schätzen die Komplexität von Algorithmen ab
  • kennen Probleme, die deterministisch oder nichtdeterministisch in polynomieller Zeit lösbar sind


Methodenkompetenzen
Die Studierenden:
  • lernen die Mächtigkeit von abstrakten Modellen von Berechenbarkeit kennen


Sozialkompetenzen
Die Studierenden:
  • arbeiten in kleinen Gruppen an Lösungen von Aufgaben
  • präsentieren Lösungen von Aufgaben vor Gruppen


Selbstkompetenzen
Die Studierenden:
  • erlernen Ausdauer bei der Bearbeitung schwieriger Aufgaben
  • erlernen Präzision beim Aufschreiben von Lösungen
Modulinhalte
Im ersten Teil der Vorlesung werden verschiedene Sprachklassen (reguläre und kontextfreie Sprachen) eingeführt. Für jede Sprachklasse werden die dazugehörigen Automatenmodelle (endliche Automaten und Kellerautomaten) vorgestellt, die zum Akzeptieren der jeweiligen Sprachen eingesetzt werden können. Diverse Eigenschaften der eingeführten Sprachen und Automaten werden bewiesen.

Im zweiten Teil der Vorlesung wird untersucht, welche Funktionen algorithmisch berechenbar bzw. welche Probleme algorithmisch entscheidbar sind. Dazu wird der Begriff des Algorithmus formalisiert. Turingmaschinen und Grammatiken stellen sich als äquivalente Ansätze heraus. Es wird gezeigt, dass es Probleme gibt, die nicht algorithmisch entscheidbar sind. Dazu gehören auch viele Probleme von praktischem Interesse.

Im dritten Teil der Vorlesung geht es um die Komplexität von Algorithmen, d.h. wie viel Zeit und Speicherplatz zum Lösen einer Aufgabe benötigt werden. Insbesondere werden Probleme betrachtet, die deterministisch oder nichtdeterministisch in polynomieller Zeit lösbar sind. Diese Problemklassen sind unter den Namen P und NP bekannt.
Literaturempfehlungen
  • essentiell: Skript "Grundbegriffe der Theoretischen Informatik", jeweils in aktueller Ausgabe
  • empfohlen: Schöning: "Theoretische Informatik kurzgefasst", 5. Auflage, Spektrum, 2008
  • Gute Sekundärliteratur: Hopcroft, Motwani, Ullman: "Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie", Pearson, 2002 (ein Klassiker...)
Links
Unterrichtssprache Deutsch
Dauer in Semestern 1 Semester
Angebotsrhythmus Modul jährlich
Aufnahmekapazität Modul unbegrenzt
Modullevel / module level AC (Aufbaucurriculum / Composition)
Modulart / typ of module je nach Studiengang Pflicht oder Wahlpflicht
Lehr-/Lernform / Teaching/Learning method V+Ü
Vorkenntnisse / Previous knowledge
Lehrveranstaltungsform Kommentar SWS Angebotsrhythmus Workload Präsenz
Vorlesung
3 WiSe 42
Übung
1 WiSe 14
Präsenzzeit Modul insgesamt 56 h
Prüfung Prüfungszeiten Prüfungsform
Gesamtmodul
Am Ende des Semesters
Klausur oder mündl. Prüfung