text: Teaching > TI1Theoretische Informatik 1 (Wintersemester 2015/2016)Dozent: Prof. Dr. Tobias FriedrichLinks: Lehrveranstaltungen IT-Systems Engineering, Algorithm Engineering Moodle
  BeschreibungIn 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" weg und betrachten nur sehr einfache Programmiersprachen. In dem Kontext lernen wir zeitgleich formal korrektes Arbeiten, mathematische Denkweisen und saubere Beweisführung. Auf dem Programm stehenLandau bzw. O-NotationWHILE-Programmierung, Turing Maschinen und Endliche AutomatenDas Halteproblem und NichtentscheidbarkeitP vs. NPZeit vs. PlatzkomplexitätAuf der anderen Seite 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 beispielsweiseGraphalgorithmen (kürzeste Wege, Tiefen/Breitensuche, Spannbäume, Flüsse, etc.)Arrayalgorithmen (Sortieren, Suchen, Partition, Median, etc.)Dynamische ProgrammierungAlgorithmische GeometrieDabei 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.VoraussetzungenFormal sind keine Voraussetzungen notwendig. Spaß an kniffeligen Aufgaben ist aber eine exzellente Grundlage!OrganisationDie 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 Moodle-Registrierung ist verpflichtend für alle Teilnehmer, da darüber auch die Verwaltung der Übungsblätter und deren Bewertung läuft. Wöchentliche VeranstaltungenVorlesung: Montag 15:15, HS 3.Church-Übung: Montag 11:00 A.2-1Cook-Übung: Montag 11:00 A.2-2Dijkstra-Übung: Montag 13:30 A.1-1Gödel-Übung: Dienstag 13:30 A.1-1Turing-Übung: Dienstag 17:00 A.1-2InhalteVorlesung 12.10.2015: Einführung, Organisation, Maximum-Subarray-ProblemÜbung: WHILE-Sprache, Paarfunktion, StackVorlesung 19.10.2015: LOOP-Sprache, Ackermannfunktion, Church-Turing-These, Gödelisierung, UniversalitätÜbung: Turing-Maschinen, WHILE-Berechenbarkeit, S-m-n TheoremVorlesung 26.10.2015: Unentscheidbarkeit, Halteproblem, ReduktionenÜbung: Reduktionen und EntscheidbarkeitVorlesung 02.11.2015: Vollständigkeit, Satz von Rice, Gödelscher UnvollständigkeitssatzÜbung: O-Notation und IndexmengenVorlesung 09.11.2015: PCP, Zeit- und Platzhierarchie, KomplexitätstheorieÜbung: Einfache Sortierverfahren, PCP, Komplexitätstheorie, IndexmengenVorlesung 16.11.2015: Multiplikation, Average-Case von Sortierverfahren, MergesortÜbung: Master-Theorem, Berechenbarkeitstheorie, Analyse von AlgorithmenVorlesung 23.11.2015: Quicksort, Untere Schranke SortierenÜbung: InsertionSort Korrektheit, Sortieren, Untere Schranken, Minima findenVorlesung 30.11.2015: Quicksort, QuickSelectÜbung: Heaps, QuickSelect, Median, Divide & ConquerVorlesung 14.12.2015: Countingsort, RadixsortVorlesung 04.01.2016: Such- und AVL-BäumeÜbung: Such- und AVL-BäumeVorlesung 11.01.2016: Rot-Schwarz-Bäume und HashingÜbung: Dynamische Programmierung und HashingVorlesung 18.01.2016: Dynamische Programmierung, Fibonacci-Zahlen, LCS, Statische SuchbäumeÜbung: AVL-Bäume, Dynamische Programmierung und AlgorithmikVorlesung 25.01.2016: Balls-into-Bins, SondierungsverfahrenKlausurtermine
  Wir bieten ein Repetitorium zur Midterm an. Der Termin ist am 30.11.2015 um 17:00 nach der Vorlesung.Klausur 1: 07.12.2015 15:00 s.t. HS 2+3. Dauer: 110 Minuten.Klausur 2: 09.02.2016 10:00 s.t. HS 1+2. Dauer: 180 Minuten. Klausur 3: 04.04.2016 11:00 s.t. HS 2+3. Dauer: 180 Minuten.Erlaubte Hilfsmittel in den Klausuren ist jeweils ein beidseitig handbeschriebenes DIN A4-Blatt.
  Weiterhin werden auf den Übungsblättern regelmäßig besonders kniffelige Aufgaben ("Knobelaufgaben") gestellt. Diese bringen direkt Bonuspunkte für die Klausur.LiteraturSchö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)VorlesungsteamDie Vorlesung wird veranstaltet vom Fachgebiet Algorithm Engineering. An der Durchführung sind die folgenden Personen beteiligt:Prof. Dr. Tobias FriedrichDozent