Dozent: Prof. Dr. Tobias Friedrich
Übungsleiter: Martin Krejca
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 zum Inhalt, formalen Voraussetzungen, Leistungserfassung etc. finden sich auf der zentralen Seite. Hier finden Sie alle Informationen für die Durchführung der Veranstaltung im Wintersemester 2017/2018.

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 11:00 Uhr in HS 2
• Office-Hour: Fr. von 15 bis 16 Uhr in A-1.1

Ablauf

• 0. Vorlesung am 18. 10. 2017: Organisatorisches, Eingangstest
• 0. Übungsblatt ohne Abgabe: korrekt argumentieren, formale Beweise
• 1. Übungsblatt mit Abgabe am 25. 10. 2017: While-Sprache, Paarfunktion, Stack
• 1. Vorlesung am 25. 10. 2017: Loop-Sprache, Ackermannfunktion, Church-Turing-These, Gödelisierung, Universalität
• 2. Übungsblatt mit Abgabe am 1. 11. 2017: While-Berechenbarkeit
• 2. Vorlesung am 1. 11. 2017: Unentscheidbarkeit, Halteproblem, Reduktionen
• 3. Übungsblatt mit Abgabe am 8. 11. 2017: Turingmaschinen, Reduktionen und Entscheidbarkeit
• 3. Vorlesung am 8. 11. 2017: Vollständigkeit, Satz von Rice, gödelscher Unvollständigkeitssatz
• 4. Übungsblatt mit Abgabe am 15. 11. 2017: O-Notation und Indexmengen
• 4. Vorlesung am 15. 11. 2017: Postsches Korrespondenzproblem, Zeitkomplexität
• 5. Übungsblatt mit Abgabe am 22. 11. 2017: Reduktionen und Komplexität
• 5. Vorlesung am 22. 11. 2017: Platzkomplexität, Multiplikation, Sortieren
• 6. Übungsblatt mit Abgabe am 29. 11. 2017: Mastertheorem, Sortieren
• 6. Vorlesung am 29. 11. 2017: Mastertheorem, untere Schranken für Sortieren, Quicksort
• 7. Übungsblatt mit Abgabe am 13. 12. 2017: Adversay-Argument, Sortieren
• 7. Vorlesung am 13. 12. 2017: Average-Case von Quicksort, Median der Mediane, Dual-Pivot-Quicksort
• 8. Übungsblatt mit Abgabe am 20. 12. 2017: Heaps
• 8. Vorlesung am 20. 12. 2017: Linearzeitsortieren, Sortiernetzwerke
• 9. Übungsblatt mit Abgabe am 10. 1. 2017: Linearzeitsortieren
• 9. Vorlesung am 10. 1. 2018: Suchbäume, AVL-Bäume, Rot-Schwarz-Bäume
• 10. Übungsblatt mit Abgabe am 17. 1. 2018: Suchbäume
• 10. Vorlesung am 17. 1. 2018: Hashing
• 11. Übungsblatt mit Abgabe am 24. 1. 2018: Hashing
• 11. Vorlesung am 24. 1. 2018: Dynamische Programmierung
• 12. Übungsblatt mit Abgabe am 31. 1. 2018: Dynamische Programmierung
• 12. Vorlesung am 31. 1. 2018: Power of two choices, Volumenberechnung

Klausurtermine

Die Klausurtermine werden im Laufe des Semester hier bekannt gegeben:

• Zwischenklausur: 6. 12. 2017, 11:00—13:00 Uhr, HS 1 und HS 2
• Endklausur: 16. 2. 2018, 10:00—13:00 Uhr, HS 1, HS 2 und HS 3
• Nachklausur: 26. 3. 2018, 10:00—13:00 Uhr, 3.06.H05 (UP!)

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 der ersten und 50 % der Punkte der zweiten Vorlesungshälfte.

Die Endnote dieser Vorlesung berechnet sich aus der Punktsumme der Zwischen- und Endklausur. Die Punkte der Zwischenklausur werden dabei mit 30 %, die der Endklausur mit 70 % gewichtet.

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: