Theoretische Informatik 2

BSc Vorlesung - Sommer 2025

Personen: Prof. Dr. Tobias Friedrich, Merlin de la Haye
Links: HPI Moodle

Die Vorlesung Theoretische Informatik 2 ist ein Pflichtmodul im 4. Semester des Bachelors IT-Systems Engineering am Hasso-Plattner-Institut der Universität Potsdam und setzt die Theoretische Informatik 1 fort und erweitert sie. Angaben zur Einschreibung befinden sich demnächst auf der zentralen Seite. Hier finden Sie alle Informationen für die Voraussetzungen, die Durchführung sowie die Leistungserfassung der Veranstaltung im Sommersemester 2025. Lehrmaterialien und aktuelle Ankündigungen werden im Moodle veröffentlicht.

Beschreibung

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

Voraussetzungen

Formal sind keine Voraussetzungen notwendig. Spaß an kniffeligen Aufgaben ist aber eine exzellente Grundlage! Ebenso ist es von Vorteil, mit den Inhalten aus Mathematik 1 und 2 (wie Aussagen-/Prädikatenlogik, Analysis, Landau-Notation, formales Beweisen) und Theoretische Informatik 1 vertraut zu sein.

Organisation

Die Verwaltung der Veranstaltung geschieht über das HPI Moodle (Link s.o.). Dort könnt ihr euch mit eurem regulären HPI-Login einloggen und für die Veranstaltung eintragen. Die Registrierung im Moodle ist verpflichtend für alle Teilnehmenden, da darüber auch die Verwaltung der Übungsblätter und deren Bewertung läuft.

Wöchentliche Veranstaltungen

Vorlesung: Dienstags, 11:00-12:30, hybrid in Hörsaal 1 und online (Zugangsdaten im Moodle)
7 Tutorien (Start in der zweiten Vorlesungswoche, Details zu den Terminen und Einwahl im Moodle)
Office Hours: einfach bei Merlin in K.2-13 vorbeikommen

Klausurzulassung

Die Endnote dieser Vorlesung wird durch eine Abschlussklausur ermittelt. Es werden zwei Prüfungstermine angeboten.
Erlaubtes Hilfsmittel in der Klausur ist ein beidseitig benutzbares DIN-A4-Blatt als Spickzettel.

Darüber hinaus werden wöchentlich Übungen ausgeteilt. Um zur Klausur zugelassen zu werden, benötigt man 50 % der insgesamt erreichbaren Übungspunkte.

Literatur

Cormen, Leiserson, Rivest, Stein: Algorithmen - Eine Einführung. (Für Algorithmik)
Jeff Erickson's Lecture Notes. (Großartige Sammlung von Material für Algorithmik)
Kozen: Automata and Computability (Formale Sprachen)
Neubert: Grundkurs Theoretische Informatik