Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

Theoretische Informatik 2 (Sommersemester 2017)

Beschreibung

Die Vorlesung Theoretische Informatik 2 ist ein Pflichtmodul im 4. Semester. Sie 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)
  • 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 der schnellste Algorithmus ist, 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-vs.-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

Neben der Vorlesung gibt es wöchentliche Übungen und Onlinelehreinheiten zur Vor- und Nachbereitung des Vorlesungsstoffes.

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 Termine

Die Vorlesungen sowie Übungen beginnen erst in der zweiten Vorlesungswoche (vom 25. April)! In der ersten Vorlesungswoche (vom 18. April) gibt es dennoch ein Übungsblatt.

  • Vorlesung: Dienstag, 13:30 Uhr, HS 2
  • Übung: Montag, 15:15 Uhr, A-1.2 (Turing)
  • Übung: Dienstag, 17:00 Uhr, A-1.1 (Church)
  • Übung: Mittwoch, 9:15 Uhr, A-2.1/A-2.2 (Cook/Dijkstra)
  • Übung: Mittwoch, 11:00 Uhr, A-1.1 (Gödel)
  • Office-Hour: Freitag, 15:00–16:00 Uhr, A.1-1

Klausurtermine

Die Klausurtermine werden im Laufe des Semester hier bekannt gegeben:

  • Endklausur: 7. August, 10:00–13:00 Uhr, HS1, HS2 und HS3
  • Nachklausur: 6. Oktober, 10:00–13:00 Uhr, HS1

Erlaubtes Hilfsmittel in den Klausuren ist jeweils ein beidseitig handbeschriebenes DIN-A4-Blatt.

Darüber hinaus werden wöchentlich Übungen ausgeteilt. Um zur Klausur zugelassen zu werden, benötigt man jeweils 50 % der Punkte aus den Übungsserien der ersten und der zweiten Hälfte des Semesters.

In jeder der Klausuren sind 50 % der Punkte hinreichend zum Bestehen.

Inhalte

Literatur

  • 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)
  • Jeff Erickson's Lecture Notes. (Großartige Sammlung von Material für Algorithmik)

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: Hörsaal 2

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

Übungsleiter

Sprechzeiten: Einfach mal vorbeikommen. Für gewöhnlich bin ich zwischen 9:00 und 16:30 Uhr da. Mittagspause ist oft zwischen 12:45 und 13:45 Uhr. Bitte beachtet aber auch die Hinweise zur Office-Hour.
Büro: A-1.7/8

E-Mail: Martin.Krejca(at)hpi.de

Tobias Knöschke

Tutor

Übung: Gödel
Raum: A-1.1
Termin: Mi., 11:00–12:30 Uhr

E-Mail: Tobias.Knoeschke(at)student.hpi.de

Simon Krogmann

Tutor

Übung: Turing
Raum: A-1.2
Termin: Mo., 15:15–16:45 Uhr

E-Mail: Simon.Krogmann(at)student.hpi.de

Stefan Neubert

Tutor

Übung: Church
Raum: A-1.1
Termin: Di., 17:00–18:30 Uhr

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

Antje Schubotz

Tutor

Übung: Cook
Raum: A-2.1
Termin: Mi., 9:15–10:45 Uhr

E-Mail: Antje.Schubotz(at)student.hpi.de

Fabian Sommer

Tutor

Übung: Dijkstra
Raum: A-2.2
Termin: Mi., 9:15–10:45 Uhr

E-Mail: Fabian.Sommer(at)student.hpi.de