Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

Theoretische Informatik 1

BSc Lecture - Winter 2018/19

Personen: Dr. Timo Kötzing, Stefan Neubert
Links: Lehrveranstaltungen IT-Systems Engineering, Algorithm Engineering Moodle

Die Vorlesung Theoretische Informatik 1 ist ein Pflichtmodul im 3. Semester des Bachelors IT-Systems Engineering am Hasso-Plattner-Institut der Universität Potsdam. 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 Wintersemester 2018/2019.

Beschreibung

In der theoretischen Informatik befassen wir uns mit grundlegenden Fragen, die den Computer betreffen:

  • Gibt es Probleme, die kein Computer jemals lösen kann?
  • Wenn man einem Computer mehr Zeit (oder Platz) gibt, kann er dann mehr Probleme lösen als vorher?
  • Sind alle Computer(-modelle) mehr oder weniger gleich? Oder gibt es wesentliche Unterschiede?
  • Gibt es Probleme, die man mit sehr viel Zeit lösen kann, aber niemals effizient mit wenig Zeit?

Um diese Fragen zu beantworten, abstrahieren wir von dem komplexen Begriff eines Computers und betrachten nur sehr einfache Programmiersprachen. In diesem Kontext lernen wir zeitgleich formal korrektes Arbeiten, mathematische Denkweisen und sauberes Führen von Beweisen. Auf dem Programm stehen:

  • Landau- bzw. O-Notation
  • WHILE-Programmierung, Turingmaschinen und endliche Automaten
  • das Halteproblem und Nichtentscheidbarkeit
  • P vs. NP
  • Zeit- vs. Platzkomplexität

Zudem geben wir eine Einführung in die Algorithmik. Wir entwerfen effiziente Algorithmen für bekannte Probleme und beweisen deren Laufzeit und Korrektheit. Dabei lernen wir verschiedene Techniken zur Problemlösung kennen. Darunter fallen beispielsweise:

  • Graphalgorithmen (kürzeste Wege, Tiefen-/Breitensuche, Spannbäume, Flüsse etc.)
  • Arrayalgorithmen (Sortieren, Suchen, Partition, Median etc.)
  • Dynamische Programmierung
  • Algorithmische Geometrie

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.

Voraussetzungen

Formal sind keine Voraussetzungen notwendig. Spaß an kniffeligen Aufgaben ist aber eine exzellente Grundlage!

Organisation

Die Verwaltung der Vorlesung 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: Mi. um 13:30 Uhr in HS 2
  • Übungsgruppen:
    • Ackermann, Dienstag 13:30 Uhr, A-1.1
    • Cantor, Dienstag 13:30 Uhr, A-1.2
    • Church, Dienstag 15:15 Uhr, A-1.1
    • Cook, Dienstag 15:15 Uhr, A-2.2
    • Dijkstra, Dienstag 17:00 Uhr, A-1.2
    • Neumann, Mittwoch 9:15 Uhr, A-1.2
    • Turing, Mittwoch 15:15 Uhr, A-1.1
    • Gödel, Mittwoch 15:15 Uhr, A-2.2

Klausurtermine

Die Endnote dieser Vorlesung wird durch eine Abschlussklausur ermittelt. Diese findet am 15.02.2019 ab 9:00 Uhr statt.
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. Am 28. November wird im Vorlesungsslot ein Übungsblatt unter Klausurbedingungen bearbeitet, das doppelt für die Klausurzulassung zählt. Details hierzu werden im Moodle bekannt gegeben.

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)

Vorlesungsteam

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

Dozent

Vorlesung: Mi., 13:30 Uhr
Raum: Hörsaal 2

Office Hour: Mo., 10-12 Uhr, A-1.12

E-Mail: Timo.Koetzing(at)hpi.de

Übungsleiter

Sprechzeiten: Einfach vorbeikommen. Für gewöhnlich bin ich zwischen 10:00 und 17:30 Uhr da. Mittagspause ist oft zwischen 12:30 und 13:30 Uhr.
Büro: A-1.7/8

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

Hans Gawendowicz

Tutor

Übung: Ackermann
Raum: A-1.1
Termin: Dienstag, 13:30 Uhr

E-Mail:Hans.Gawendowicz(at)student.hpi.de

Linus Heinzl

Tutor

Übung: Neumann
Raum: A-1.2
Termin: Mittwoch, 09:15 Uhr

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

Jannik Peters

Tutor

Übung: Cantor
Raum: A-1.2
Termin: Dienstag, 13:30 Uhr

E-Mail:Jannik.Peters(at)student.hpi.de

Antje Schubotz

Tutor

Übung: Church
Raum: A-1.1
Termin: Dienstag, 15:15 Uhr

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

David Stangl

Tutor

Übung: Cook
Raum: A-2.2
Termin: Dienstag, 15:15 Uhr

E-Mail: David.Stangl(at)student.hpi.de

Daniel Stephan

Tutor

Übung: Turing
Raum: A-1.1
Termin: Mittwoch, 15:15 Uhr

E-Mail:Daniel.Stephan(at)student.hpi.de

Martin Taraz

Tutor

Übung: Gödel
Raum: A-2.2
Termin: Mittwoch, 15:15 Uhr

E-Mail:Martin.Taraz(at)student.hpi.de

Arthur Zahn

Tutor

Übung: Dijkstra
Raum: A-1.2
Termin: Dienstag, 17:00 Uhr

E-Mail:Arthur.Zahn(at)student.hpi.de