Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

Theoretische Informatik 2

BSc Lecture - Summer 2020

Personen: Prof. Dr. Tobias Friedrich, Stefan Neubert
Links: Lehrveranstaltungen IT-Systems Engineering, Algorithm Engineering 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 auf der zentralen Seite. Hier finden Sie alle Informationen für die Voraussetzungen, die Durchführung sowie die Leistungserfassung der Veranstaltung im Sommersemester 2020.

Dieses Semester wird nicht wie gewöhnlich mit einem Treffen im Hörsaal beginnen können. Deshalb ist es wichtig, dass sich alle Teilnehmenden der Veranstaltung bis zum 21.04.2020 im Moodle des Kurses einschreiben. Dort wird zeitnah der Zoom-Link für die erste Vorlesungseinheit veröffentlicht, die am 21.04.2020 um 13:30 Uhr stattfindet.

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

Voraussetzungen

Es wird davon ausgegangen, dass die Themen aus den Veranstaltungen Mathematik I, Mathematik II und Theoretische Informatik I bekannt sind.

Organisation

Die Verwaltung der Veranstaltung geschieht über das Moodle des Fachgebiets. Dort können Sie sich mit Ihrem regulären HPI-Login einloggen und für die Veranstaltung eintragen. Die Registrierung im Moodle ist verpflichtend für alle Teilnehmer, da darüber auch die Verwaltung der Übungsblätter und deren Bewertung läuft.

Wöchentliche Veranstaltungen

  • Vorlesung: Dienstags um 13:30 Uhr in HS 2 (bzw. digital)
  • Übungsgruppen:
    • Gouda: Montags um 11:00 Uhr in A-1.1 (bzw. digital)
    • Parmesan: Montags um 11:00 Uhr in A-1.2 (bzw. digital)
    • Mozzarella: Montags um 13:30 Uhr in A-1.1 (bzw. digital)
    • Feta: Montags um 13:30 Uhr in A-1.2 (bzw. digital)
    • Pecorino Romano: Dienstags um 15:15 Uhr in A-2.2 (bzw. digital)
    • Cheddar: Mittwochs um 13:30 Uhr in A-1.1 (bzw. digital)
  • Office Hour: Freitags um 10:00 Uhr in A-1.7/8 (bzw. digital)

Klausurtermine

Die Endnote dieser Vorlesung wird durch eine Abschlussklausur ermittelt.
Erlaubtes Hilfsmittel in der Klausur ist ein beidseitig eigens handbeschriebenes DIN-A4-Blatt.

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)

Vorlesungsteam

Die Vorlesung wird veranstaltet vom Fachgebiet Algorithm Engineering. An der Durchführung sind die folgenden Personen beteiligt:

Dozent

Vorlesung: Dienstag, 13:30 Uhr
Raum: HS 2 / vorerst digital

E-Mail:Tobias.Friedrich(at)hpi.de

Übungsleiter

Office Hour: Freitags, 10:00 Uhr
Büro: A-1.7/8 / vorerst digital (Siehe Moodle)

E-Mail: Stefan.Neubert(at)hpi.de

Linus Heinzl

Tutor

Übung: Feta
Raum: A-1.2 / vorerst digital
Termin: Montags, 13:30 Uhr

E-Mail: Linus.Heinzl(at)student.hpi.de

Nicolas Klodt

Tutor

Übung: Parmesan
Raum: A-1.2 / vorerst digital
Termin: Montags, 11:00 Uhr

E-Mail: Nicolas.Klodt(at)student.hpi.de

Leon Schiller

Tutor

Übung: Pecorino Romano
Raum: A-2.2 / vorerst digital
Termin: Dienstags, 15:15 Uhr

E-Mail: Leon.Schiller(at)student.hpi.de

Georg Tennigkeit

Tutor

Übung: Gouda
Raum: A-1.1 / vorerst digital
Termin: Montags, 11:00 Uhr

E-Mail: Georg.Tennigkeit(at)student.hpi.de

Armin Wells

Tutor

Übung: Cheddar
Raum: A-1.1 / vorerst digital
Termin: Mittwochs, 13:30 Uhr

E-Mail: Armin.Wells(at)student.hpi.de

Robin Wersich

Tutor

Übung: Mozzarella
Raum: A-1.1 / vorerst digital
Termin: Montags, 13:30 Uhr

E-Mail: Robin.Wersich(at)student.hpi.de