Die Vorlesung Theoretische Informatik 2 ist ein Pflichtmodul im 4. Semester und setzt die Theoretische Informatik 1 fort und erweitert sie.
Unser Ziel ist es, die angefangene Algorithmik-Toolbox auszubauen. Gleichzeitig schulen wir dabei das Hantieren mit und schnelle Erfassen von neuen Modellen. Dazu schauen wir uns Algorithmen in diversen Gebieten an:
- Graphalgorithmen befassen sich mit effizienter Erkennung von Strukturen (z. B. kürzeste Wege) in Graphen.
- Stringalgorithmen sorgen für eine effiziente Verarbeitung von Strings (z. B. das Parsen regulärer Ausdrücke).
Dabei sind wir darauf bedacht, eine Dualität aufzuzeigen: Auf der einen Seite fragen wir uns häufig, was ist der schnellste Algorithmus, den wir für ein Problem finden können? Auf der anderen Seite möchten wir wissen, ob es mathematisch beweisbar ist, dass es keinen schnelleren Algorithmus geben kann. Daher betrachten wir klassische Modelle und Beweistechniken aus der theoretischen Informatik.
- (Nicht-)deterministische endliche Automaten geben einen Einstieg in das Konzept des Nichtdeterminismus.
- Nichtdeterministische Turingmaschinen werden häufig gebraucht, um schwere kombinatorische Probleme zu beschreiben.
- Mittels Polynomialzeitreduktionen lernen wir das klassische P-NP-Problem kennen und können neue Probleme nach diesem Kriterium klassifizieren.
