Höhere Algorithmik Wintersemester 2016/17

Wolfgang Mulzer, Boris Klemz

Aktuelles

Allgemein

Die Übungszettel werden ausschließlich online erscheinen und zwar hier auf dieser Seite.

Themenübersicht

  • Grundlagen
    • Berechnungsmodelle
    • Rekursionsgleichungen
    • O-Notation
    • elementare Wahrscheinlichkeitstheorie
  • Techniken
    • Teile und Herrsche
    • Dynamisches Programmieren
    • Abschneiden und Suchen
    • Gierige Algorithmen
    • Lineares Programmieren
    • Hashing und Fingerprinting
    • untere Schranken
  • Paradigmen
    • Worst-Case Analyse
    • Average-Case Analyse
    • Probabilistische Algorithmen
    • Amortisierte Analyse
    • Online-Algorithmen und kompetitive Analyse
    • Approximationsalgorithmen
  • Algorithmen und Datenstrukturen
    • Suchen, Sortieren und Auswählen
    • Viterbi-Algorithmus
    • TSP
    • Datenstrukturen: Splaybäume, Erdbebenheaps, Disjoint Set Union, Bloom Filter
    • Graphenalgorithmen: Flüsse, Paarungen, Schnitte, minimale aufspannende Bäume, kürzeste Wege
    • Simplex Algorithmus mit Anwendungen, Ellipsoid Algorithmus
    • Internet-Algorithmen: Page-Rank, konsistentes Hashing
    • Ski-Rental, Paging
  • Komplexität
    • Klassenzoo: LOGSPACE, P, NP, coNP, PSPACE, etc
    • NP-Vollständigkeit, Satz von Cook, Reduktionskonzept
    • Umgang mit schwierigen Problemen

Tatsächlicher Inhalt

  • Dienstag, den 18.10.2016
    • Administrativa
    • Einleitung
    • Auswahlproblem.
      • S: total geordnete Menge mit n paarweise verschiedenen Elementen. Rang eines Elements s aus S: 1 + Anzahl Elemente in S kleiner als s.
      • Gegeben: Menge S und Zahl k; Gesucht: das Element mit Rang k.
      • Annahme: haben eine Funktion splitter(S), welche garantiert eine Element mit Rang mindestens n/4 und höchstens 3n/4 findet. Wenn splitter nichts kostet, dann können wir das Auswahlproblem in O(n) Zeit lösen. Siehe hier.
  • Montag, den 24.10.2016
    • Implementierung von splitter
      • Einfache Möglichkeit: Wähle zufälliges Element. Mit Wahrscheinlichkeit 1/2 erwischt man einen guten Splitter. Dies liefert lineare Laufzeit im Erwartungswert (Hoares Quickselect).
    • Der BFPRT-Algorithmus
      • Unterteile S in Fünfergruppen. Bestimme Median jeder Gruppe, bestimme rekursiv den Median der Mediane, verwende Ergebnis als Splitter.
      • Durch genaue Analyse anhand eines Bildes sieht man: der Median der Mediane ist ein guter Splitter.
      • Durch Induktion sieht man, dass die Laufzeit auch mit dem zusäzlichen rekursiven Aufruf noch linear bleibt (denn 3/4 + 1/5 < 1, also nimmt die Problemgröße weiterhin geometrisch ab. Achtung: die Rechnung verkompliziert sich etwas durch die Rundungsproblematik.)
    • Prune and Search (Abschneiden/Stutzen und Suchen): in jedem Schritt wird ein konstanter Anteil der Eingabe (z.B., ein Viertel) verworfen (abgeschnitten) und auf den Rest wird rekurriert (weitergesucht).
  • Dienstag, den 25.10.2016
    • Grundlagen und Modellierung:
      • Berechnungsmodell Registermaschine: eine mathematische Abstraktion für die von-Neumann-Maschine
      • Laufzeit und Speicherbedarf: Gesamtkosten der ausgefürten Anweisungen und gesamter Platzbedarf der Registermaschine bei einer festen Eingabe
      • Einheitskostenmdell: Jede Anweisung und jede Speicherzelle hat Kosten 1.
      • logarithmisches Kostenmodell: Die Kosten für eine Anweisung und eine Speicherzelle entspricht der Anzahl der Bits zur Darstellung der beteiligten Zahlen
      • Bei kombinatorischen Algorithmen benutzt man normalerweise das EKM, bei zahlentheoretischen Algorithm das LKM
      • worst-case Laufzeit: Ordnet jeder Eingabegröße die maximale Laufzeit zu, die eine Eingabe dieser Größe benötigt
      • O-Notation, Pseudocode
  • Montag, den 31.10.2016 (vertreten von Boris Klemz)
    • Grundlegende Entwurfstechniken
      • Teile und Herrsche (Divide and Conquer): Unterteile in Teilprobleme, löse diese rekursiv, setze Teillösungen zur Gesamtl&oum;sung zusammen
    • Karatsuba-Multiplikation
      • Gegeben zwei n-bittige Zahlen a und b, berechne das Produkt ab.
      • Die Schulmethode benötigt quadratisch viele elementare Additionen und Multiplikationen.
      • Karatsuba: Verwende den Teile und Herrsche Ansatz. Unterteile die n-bittigen Zahlen in vier n/2-bittige Zahlen, führe die Berechnung rekursiv aus, und setze das Ergebnis zusammen.
      • Der naive Ansatz benötigt 4 rekursive Multiplikationen. Dadurch lässt sich keine Verbesserung erreichen.
      • Durch eine geschickte rekursive Beziehung kann man die Anzahl der rekursiven Multiplikationen auf 3 reduzieren.
      • Die resultierende Rekursionsgleichung ergibt eine wesentlich bessere Laufzeit.
    • Techniken für Rekursionsgleichungen
      • Methode 1: Rate eine Lösung und beweise die Korrektheit durch Induktion.
      • Methode 2: Setze wiederholt ein, bis ein Muster zu Tage tritt. Werte die resultierende Summe aus.
      • Methode 3: Rekursionsmethode: visualisiere die Rekursion als Baum:
        • ein Knoten für jeden Funktionsaufruf, beschriftet mit der Problemgröße.
        • Berechne den Gesamtaufwand auf jeder Ebene.
        • Summiere über alle Ebenen.
      • Methode 4: Master Theorem:
        • Allgemeines Rezept zur Lösung vieler Rekursionsgleichungen. Nicht immer anwendbar, aber oft.
        • Siehe auch hier und hier.
  • Dienstag, den 01.11.2016 (vertreten von Boris Klemz)
    • Bestimmen des engsten Punktpaars mit Teile und Herrsche
    • Dynamisches Programmieren: Rucksackproblem
  • Montag, den 07.11.2016
    • Dynamisches Programmieren: Rundreiseproblem
    • Dynamisches Programmieren: Versteckte Markov Modelle
      • Motivation und Beispiel
      • Definition
  • Dienstag, den 08.11.2016
    • Viterbi-Algorithmus
      • Notizen
      • Mehr Informationen zum Viterbi-Algorithmus gibt es hier oder hier.
    • Gierige Algorithmen: Intervallauswahl
  • Montag, den 14.11.2016
    • gierige Algorithmen: Intervallauswahl
      • Gegeben: n Intervalle
      • Gesucht: grtößtmögliche Teilmenge paarweise disjunkter Intervalle
      • Algorithmus: gehe Intervalle aufsteigend nach Endpunkten durch, nimm Intervall, wenn es nicht mit bisherigen Intervallen im Konflikt steht.
      • Laufzeit: O(n log n).
      • Korrektheitsbeweis durch Austauschargument: können optimale Lösung schrittweise in gierige Lösung überführen, ohne die Anzahl der Intervalle zu verringern.
      • Elegante Formulierung des Korrektheitsbeweises: Indirekter Beweis. Nimm optimale Lösung, die gieriger Lösung am meisten ähnelt. Entweder sind Lösungen identisch, oder wir können sie durch Austauschargument ähnlicher machen, im Widerspruch zur Annahme.
    • Intervallunterteilung
      • Gegeben: n Intervalle
      • Gesucht: Partition der Intervalle in minimale Anzahl von Mengen, den nur paarweise disjunkte Intervalle enthalten.
      • Algorithmus: gehe Intervalle aufsteigend nach Anfangspunkten durch. Füge Intervall I zur ersten Menge hinzu, die kein Intervall enthält, das I von links überlappt. Eröffne ggf. eine neue Menge.
      • Laufzeit: O(n log n).
      • Korrektheitsbeweis: Tiefe d der Intervallmenge: Maximale Anzahl an Intervallen, die einen gemeinsamen Punkt haben.
      • Beobachtung: Jede gültige Lösung benötigt mindestens d Mengen.
      • Fakt: Der gierige Algorithmus benötigt höchstens d Mengen.
  • Dienstag, den 15.11.2016
    • Gierige Algorithmen: Offline-Caching
  • Montag, den 21.11.2016
    • Datenstrukturen: Das Problem der disjunkten Mengen
    • Gegeben: Feste Menge S von n Elementen
    • Ziel: Speichere Partition von S in paarweise disjunkte Mengen
    • Operationen:
      • Find(s): Finde Menge der aktuellen Partition, die s entält
      • Union(Si, Sj): Vereinige Mengen Si und Sj in der aktuellen Partition
    • Anwendungen: Zusammenhangskomponenten eines Graphen, Algorithmus von Kruskal, Perkolation, Segmentierung eines Bildes, FORTRAN
    • Einfache Datenstruktur: Darstellung als Wald von disjunkten Mengen
      • Jedes Element wird durch ein Objekt dargestellt
      • Jede Menge wird durch ein festes repräsentatives Element dargestellt
      • Jedes Element besitzt einen Nachfolgerzeiger. Die Nachfolgerzeiger der repräsentativen Elemente sind NIL, bei den anderen Element ist garantiert, dass die Nachfolgerzeiger zum repräsentativen Element f¨hren
    • Find: folge Nachfolgezeigern bis zum repräsentativen Element
    • Union: Mache ein repräsentatives Element zum Nachfolger des anderen
    • Die Laufzeit kann sehr schlecht werden, wenn die Bäume hoch werden
    • Union-by-Rank Heuristik: Hänge immer den niedrigeren Baum unter den höheren Baum. Speichere den Rang eines Knoten, um die Höhen zu verfolgen
  • Dienstag, den 22.11.2016
    • Analyse der UNION-FIND-Struktur mit Pfadkompression und Union by Rank I
  • Montag, den 28.11.2016
    • Analyse der UNION-FIND-Struktur mit Pfadkompression und Union by Rank II
  • Dienstag, den 29.11.2016
    • Abschluss UNION-FIND
    • Amortisierte Analyse
  • Montag, den 5.12.2016
    • Universelles Hashing
  • Dienstag, den 6.12.2016
    • Universelles Hashing
    • Perfektes Hashing
  • Montag, den 12.12.2016
    • Perfektes Hashing
    • Bloom-Filter
  • Dienstag, den 13.12.2016
    • Bloom-Filter
    • Page-Rank
  • Dienstag, den 03.01.2017
    • Page-Rank
    • Prioritätswarteschlangen
  • Montag, den 09.01.2017
    • Prioritätswarteschlangen
    • Quake-Heaps
  • Dienstag, den 10.01.2017
    • Quake-Heaps
  • Montag, den 16.01.2017 (vertreten von Boris Klemz)
    • Abschluss der amortisierten Analyse von Quake-Heaps
    • Flüsse in Netzwerken: Definitionen und Beispiele
  • Dienstag, den 17.01.2017 (vertreten von Boris Klemz)
    • Restnetze und der Algorithmus von Ford-Fulkerson
  • Montag, den 23.01.2017
    • Der Algorithmus von Edmonds-Karp
  • Dienstag, den 24.01.2017
    • Lineares Programmieren: Motivation und Definitionen
  • Montag, den 30.01.2017
    • Simplex-Algorithmus
  • Dienstag, den 31.01.2017
    • Abschließende Bemerkungen zum Simplex-Algorithmus
    • Effiziente Algorithmen und schwierige Probleme
  • Montag, den 06.02.2017 (vertreten von Boris Klemz)
    • NP-Vollständigkeitstheorie: Motivation, Definitionen, Beispiele
  • Dienstag, den 07.02.2017 (vertreten von Boris Klemz)
    • NP-Vollständigkeitstheorie: Reduktionen
  • Montag, den 13.02.2017
    • NP-Vollständigkeitstheorie: Satz von Cook-Levin
  • Dienstag, den 14.02.2017
    • Klausur
  • Freitag, den 17.02.2017 (SR 053, 08:00–08:55 Uhr)
    • Klausureinsicht
  • Dienstag, den 18.04.2017 (SR 006, 16:00–18:00 Uhr)
    • Nachklausur
  • Freitag, den 21.04.2017 (SR 055, 09:00–09:55 Uhr)
    • Einsicht der Nachklausur und der Klausur

    • Literatur

    Schein/Klausur

    Es wird eine Klausur am Ende des Semesters geben, sowie eine Ersatzklausur vor Beginn des nächsten Semesters. Dabei gilt die Freiversuchsregel. Das heißt, man kann die Ersatzklausur nutzen, um das Ergebnis aus der Hauptklausur zu verbessern (nur bei erstmaligem Absolvieren des Moduls).

    Die Klausur findet statt am Dienstag, den 14.02.2017 von 10–12 Uhr im SR 005. Die Nachklausur findet statt am Dienstag, den 18.04.2017, von 16–18 Uhr im SR 006.

    Für den Scheinerhalt muss man

    Die erfolgreiche Teilnahme am Übungsbetrieb und Teilnahme an der Klausur sind unabhängige Leistungen.

    Die Scheine sind benotet. Die Note beruht nur auf den Klausurergebnissen.

    Termin/Tutorium

    Die Vorlesung findet statt Montag und Dienstag, 10–12 Uhr, im SR 005 in der Takustraße 9. Die Tutorien werden betreut von Boris Klemz.

    Mittwoch
    12:00–14:00 Arnimallee 7, Seminarraum 140 Boris Klemz
    14:00–16:00 Takustr. 9, Seminarraum 053 Boris Klemz

    Sprechzeit des Dozenten: Dienstag 16–17 Uhr in Zimmer 114 und nach Vereinbarung.

    Übungszettel

    Die Übungszettel werden jede Woche hier verlinkt. Sie werden ausschließlich online erscheinen. Die normale Bearbeitungszeit ist von Dienstag zum Freitag 10 Tage später. Die Zettel sind vor 12 Uhr in den Briefkasten neben Raum 111, Takustraße 9, einzuwerfen. Die Bearbeitung erfolgt in Zweiergruppen.

    Übungszettel, die nach dem angegebenen Termin abgegeben werden, zählen als nicht bearbeitet.

    Nr.AusgabeAbgabe pdftexBemerkungen
    1 01.10.2016 28.10.2016  
    2 25.10.2016 04.11.2016  
    3 01.11.2016 11.11.2016  
    4 08.11.2016 18.11.2016  
    5 15.11.2016 25.11.2016  
    6 22.11.2016 02.12.2016 Leichte Anpassungen in Aufgaben 1b und 3b.
    7 29.11.2016 09.12.2016  
    8 06.12.2016 16.12.2016  
    9 13.12.2016 06.01.2017 Weihnachtszettel
    10 03.01.2017 13.01.2017  
    11 10.01.2017 20.01.2017  
    12 17.01.2017 27.01.2017 vorletztes Blatt
    13 24.01.2017 03.02.2017 letztes Blatt
    Impressum