Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

Theoretische Informatik 1

BSc Vorlesung - Winter 2022/23

Personen: Prof. Dr. Tobias Friedrich, Georg Tennigkeit
Links: Lehrveranstaltungen IT-Systems Engineering, HPI 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 Moodle-Seite. Hier gibt es alle Informationen für die Voraussetzungen, die Durchführung sowie die Leistungserfassung der Veranstaltung im Wintersemester 2023/2024.

Coronahinweise / Lehrorganisation

Nach aktuellem Plan finden die Übungsgruppen in Präsenz und der Vorlesungsteil der Veranstaltung Hybrid (Präsenz+Zoom) statt. Die Übertragung der Vorlesung via Zoom wird eingerichtet, der Link dazu wird im Moodle veröffentlicht. Dieses Semester wird durch die erste Vorlesung am Donnerstag, den 20.10.2022 um 13:30 in Hörsaal 1 begonnen werden. Bitte schreibt euch zusätzlich zur normalen Einschreibung beim Studienreferat schon bis zum 19.10.2022 im Moodle des Kurses ein, da dort auch weitere Ankündigungen bekannt gegeben werden.

Falls es die Umstände erfordern, werden wir auf digitalen Vorlesungsbetrieb via Zoom wechseln.

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 und Vorbereitung

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

Wer sich zusätzlich zu den empfohlenen Lehrveranstaltungen im 1./2. Semester vorbereiten möchte, dem empfehlen wir folgende Literatur und Übungsaufgaben:

  • Ch. Meinel, M. Mundhenk: "Mathematische Grundlagen der Informatik". (Grundlagen der Logik, Beweistechnik, Funktionen und Mengentheorie.)
  • A. Beutelspacher: "Das ist o.B.d.A. trivial!". (Best Practices für die Notation von Sätzen und Argumenten)
  • D. Velleman: "How to Prove It: A Structured Approach". (Lesen und Schreiben von Beweisen)
  • Aufgaben zu Exponential- und Logarithmusgleichungen (Gibt es zahlreich im Internet)

Organisation

Die Verwaltung der Vorlesung geschieht über das HPI Moodle. Dort könnt ihr euch mit dem 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. Bitte beachtet, dass ihr euch zusätzlich dazu noch regulär im Moodle für die Kursbelegung (beim Studienreferat) registrieren müsst.

Wöchentliche Veranstaltungen

Alle Veranstaltungen finden hybrid (in HS 1 und via Zoom) statt; die Zugangsdaten werden im Moodle bereitgestellt.

  • Vorlesung: Donnerstags, 13:30 Uhr in HS 1
  • Übungsgruppen (Beginn in der zweiten Vorlesungswoche):
    • Kirschbaum mit Georg: Montags, 15:15 - 16:45 in A-2.1
    • Wisterie mit Ben: Montags, 17:00 - 18:30 in K-2.03
    • Nordmanntanne mit Till: Montags, 17:00 - 18:30 in A-1.1
    • Apfelbaum mit Janni: Dienstags, 17:00 - 18:30 in K-1.02
    • Ahorn mit Lukas: Dienstags, 17:00 - 18:30 in K-1.03
    • Palme mit Fynn: Mittwochs, 15:15 - 16:45 in A-2.2
    • Binärbaum mit Hannes: Mittwochs, 15:15 - 16:45 in K-1.03
  • Office Hour: einfach in K-2.13 vorbeikommen (und ggf. vorher schreiben)

Klausurtermine und -zulassung

Die Endnote dieser Vorlesung wird durch eine Abschlussklausur ermittelt. Diese findet am 27.02.2023 ab 10:00 Uhr statt. Ein zweiter Prüfungstermin wird am 03.04.2023 ab 10:00 Uhr angeboten.
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 15.12.2022 wird im Vorlesungsslot ein Übungsblatt in Einzelarbeit 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)
  • Neubert: Grundkurs Theoretische Informatik.

Vorlesungsteam

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

Dozent

Vorlesung: Donnerstags 13:30, HS 1 und voraussichtlich via Zoom (siehe Moodle)

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

Übungsleiter

Office Hours: einfach in Raum K-2.13 vorbeikommen (am besten vorher formlos anschreiben) oder digitalen Termin ausmachen.
E-Mail: Merlin.delaHaye(at)hpi.de

Ben Bals

Tutor

Gruppe: Wisterie
E-Mail: Ben.Bals(at)student.hpi.de

Fynn Kröger

Tutor

Gruppe: Palme
E-Mail: Fynn.Kroeger(at)student.hpi.de

Georg Tennigkeit

Tutor

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

Hannes Spitz

Tutor

Gruppe: Binärbaum
E-Mail: Hannes.Spitz(at)student.hpi.de

Janni Röbbecke

Tutorin

Gruppe: Apfelbaum
E-Mail: Janni.Roebbecke@student.hpi.de

Lukas Hagen

Tutor

Gruppe: Ahorn
E-Mail: Lukas.Hagen@student.hpi.de

Till Bergmann

Tutor

Gruppe: Nordmann-Tanne
E-Mail: Till.Bergmann(at)student.hpi.uni-potsdam.de