inf401 Grundlagen der Theoretischen Informatik (Complete module description)

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
• wissen von der Relevanz NP-vollständiger Probleme 

Methodenkompetenzen
Die Studierenden:

• lernen die Mächtigkeit von abstrakten Modellen von Berechenbarkeit kennen
• kennen nicht-effizient lösbare Probleme und können diese in praktischen Aufgabenstellungen wiedererkennen 

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

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.

Essenziell: 

• 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...)

Am Ende des Semesters

Klausur oder mündl. Prüfung