Theoretische Informatik II (Sommersemester 2018)

Dozent: Prof. Dr. Tobias Friedrich (Algorithm Engineering)
Website zum Kurs: https://hpi.de/friedrich/teaching/ss18/ti2.html

Allgemeine Information

In Theoretische Informatik II bauen wir auf den Inhalten von TI1 auf

und erweitern diese. 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)
Geometrische Algorithmen helfen dabei, Ereignisse wie z.B. Schnittpunkte von Linien oder konvexe Hüllen in dem zweidimensionalen Raum zu finden

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 Polynomialzeit-Reduktionen lernen wir das klassische P vs. NP Problem kennen und können neue Probleme nach diesem Kriterium klassifizieren

Es wird davon ausgegangen, dass die Themen aus Theoretische Informatik I bekannt sind.

Schöning: Theoretische Informatik - kurz gefasst. (Gut lesbar, für Berechenbarkeitstheorie)
Bläser: Theoretical Computer Science (Umfangreich, für Berechenbarkeitstheorie)
Cormen, Leiserson, Rivest, Stein: Algorithmen - Eine Einführung. (Für Algorithmik)

Neben der Vorlesung gibt es wöchentliche Übungen und Online-Lehreinheiten zur Vor- und Nachbereitung des Vorlesungsstoffes. Mehr Informationen auf den Seiten des Fachgebiets.

Für die Zulassung zur Klausur müssen 50% der Punkte von den

Übungsblättern 1-6, und 50% der Punkte von den Übungsblättern 7-12

erreicht werden.

Es wird eine schriftliche Klausur am Ende des Semesters geschrieben.