Algorithmen, Datenstrukturen und Datenabstraktion Wintersemester 2017/18

Wolfgang Mulzer, Katharina Klost

Aktuelles

Allgemein

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

Themenübersicht

  • Algorithmen
    • Grundlagen
      • Maschinenmodell
      • Laufzeit und Speicherbedarf
      • Ansätze zur Algorithmenanalyse
      • O-Notation
      • Lösung von Rekursionsgleichungen
      • Wofür effiziente Algorithmen?
    • Datenstrukturen
      • Listen: einfach und doppelt verkettet
      • Bitvektor
      • Halden
      • Suchbäume
        • balanciert: AVL, rot-schwarz, ...
        • extern: B-Bäume, (a,b)-Bäume
        • digital: tries
      • Skip-Listen
      • Hashtabellen
        • Konfliktbehandlung (Chaining, offene Adressierung, Kuckuck)
        • universelles Hashing
    • abstrakte Datentypen
      • für Mengen und Listen
        • Stapel, Schlange
        • Prioritätswarteschlange
        • Map, Ordered Map
        • Iteratoren
      • Relationen, Graphen, Bäume
      • geometrische Objekte
    • Entwurfsparadigmen
      • Teile und Herrsche
      • dynamisches Programmieren
      • Backtracking
      • gierige Algorithmen
      • Plane-sweep
      • Zufallsalgorithmen
      • amortisierte Analyse
    • diverse Algorithmen
      • Graphenalgorithmen
        • Breitensuche, Tiefensuche
        • topologisches Sortieren
        • kürzeste Weg (Dijkstra, Bellman-Ford)
        • minimale aufspannende Bäume
      • Suche in Zeichenketten
      • Huffman-Kompression
      • Spielbäume
      • FFT
  • Programmierung
    • Merkmale guter Software
      • Wiederverwendbarkeit
      • Wartbarkeit
      • Übersichtlichkeit
      • geringe Fehleranfälligkeit
    • Hilfsmittel
      • Abstraktion/Geheimnisprinzip
      • Modularisierung
      • Generizität
      • Objektorientierung
    • Entwurfsmuster
      • Adapter
      • Iterator
      • Komposition
      • template method
      • Komparator
      • Decorator
    • sprachliche Ausdrucksmittel
      • Objekte und Vererbung, Zugriffsmodifizierer
      • Polymorphie
      • Interfaces und abstrakte Klassen
      • Java collections framework
      • Generics in Java
      • Pakete in Java
      • Annotations in Java
      • Persistenz und Serialisierung in Java
      • Module in Haskell
      • algebraische Datentypen in Haskell
    • Spezifikation und Korrektheit
      • natürlichsprachliche Spezifikation
      • formale Spezifikation (modellierend/algebraisch/funktional)
      • Hoare-Kalkül
    • Speicherverwaltung
      • Keller und Haufen/Halde
      • Speicherverwaltung in C/C++
      • Speicherbereinigung
      • Freispeicherverwaltung/Fragmentierung

Tatsächlicher Inhalt

  • Dienstag, den 17.10.2017
    • Administrativa
    • Einleitung
      • Es geht um Daten: wie man sie darstellt, manipuliert, auf sie zugreift und sie speichert?
    • Einführendes Beispiel: Polynome
      • Darstellung eines Polynoms vom Grad n als Koeffizientenform
        • Addition zweier Polynome in O(n) Operationen
        • Auswerten an einer Stelle z in O(n) Operationen mit dem Horner Schema
        • Multiplikation zweier Polynome in O(n^2) Operationen
      • Darstellung eines Polynoms vom Grad n durch Auswertung an mindestens n+1 verschiedenen Stellen
  • Donnerstag, den 19.10.2017
    • Darstellung eines Polynoms vom Grad n durch Auswertung an mindestens n+1 verschiedenen Stellen
      • Addition zweier Polynome in O(n) Operationen
      • Auswerten an einer Stelle z in O(n^2) Operationen durch Polynominterpolation (z.B., Newton oder Lagrange Interpolation)
      • Multiplikation zweier Polynome in O(n) Operationen
    • Durch geschickte Wahl der Stellen kommt man von der Koeffizienten- zur Wertedarstellung mit O(n log n) Operationen (schnelle Fourier Transformation, FFT)
    • FFT ist einer der wichtigsten Algorithmen überhaupt, mit Anwendungen in der Signalverarbeitung, der Datenkompression, für schnelle Quantenalgorithmen zur Faktorisierung von großen Zahlen uvam; siehe dazu auch Seite 27ff des MafI2 Skripts.
  • Dienstag, den 24. 10. 2017
    • Algorithmen: Definition und Qualitätsmerkmale
    • Arten der Evaluation von Algorithmen: experimentell und theoretisch
      • Experimentelle Analyse (Testen/Benchmarking): sehr konkrete Ergebnisse, aber problematisch.
      • Theoretische Analyse: liefert leicht vergleichbare und allgemeine Aussagen, ist oft mit geringerem Aufwand verbunden als experimentelle Analyse, kann aber auch wesentliche Aspekte vernachlässigen.
    • Theoretische Analyse benötigt ein abstraktes Maschinenmodell, um die erlaubten elementaren Schritte festzulegen.
    • Definition Registermaschine/Random Access Machine (RAM)
    • Definition: Laufzeit und Speicherplatz auf der RAM
  • Donnerstag, den 26. 10. 2017
    • Programmierung und Laufzeitbestimmung auf der RAM sind anstrengend, also: Pseudocode,
    • O-Notation und asymptotische Analyse, um von konstanten Faktoren und Termen niedriger Ordnung zu abstrahieren (Achtung: kann manchmal irreführend sein)
    • Rekursion
  • Dienstag, den 31. 10. 2017
    • Reformationstag (keine Vorlesung)
  • Donnerstag, den 02. 11. 2017 (vertreten von Katharina Klost)
    • Einfache Datenstrukturen: Stapel und Schlange
      • Implementierungen: verkettete Liste oder Array fester Grösse oder dynamisch wachsendes Array
    • dynamisch wachsendes Array
      • amortisierte Analyse: betrachte eine Folge von m Operationen. Wenn jede solche Folge f(m) Zeit benötigt, dann sind die amortisierten Kosten pro Operation f(m)/m.
      • Beweis, dass PUSH im dynamischen Array O(1) amortisierte Kosten benötigt, mit der Buchhaltermethode: bezahle 3 € pro Operation; argumentiere, dass dies ausreicht, um alle Kopieraktionen zu bezahlen
  • Dienstag, den 07. 11. 2017
    • guter Softwareentwurf: gute Software ist wartbar, flexibel, übersichtlich, von geringer Fehleranfälligkeit
    • Mittel dazu: Geheimnisprinzip
      • Teile besitzen eine genau spezifizierte Schnittstelle zur Kommunikation nach außen.
      • Das Innenleben ist geheim.
    • abstrakter Datentyp (ADT)
      • ein Typ, dessen Objekte nur über eine klar spezifizierte Schnittstelle manipuliert werden können, nicht durch direkten Zugriff auf die Daten.
    • Java ist eine objektorientierte Programmiersprache.
      • Das zentrale Konzept sind Objekte.
      • Wesentliche Merkmale sind Kapselung und Vererbung/Polymorphie.
    • ADTs in Java
      • Definiere Schnittstelle als Oberklasse/Interface, Implementierung als Unterklasse
      • Verwende Kapselung, um die Implementierungsdetails nach außen zu verbergen.
    • Spezifikation des ADT Prioritätswarteschlange
      • verbal: gib für alle Operationen Vor- und Nachbedingungen auf natürlichsprachliche Weise an. Vorteile: einfach und verständlich; Nachteile: lang und leicht unpräzise
  • Donnerstag, den 09. 11. 2017
    • Spezifikation des ADT Prioritätswarteschlange
      • modellierend: definiere ein abstraktes Modell für den Datentyp, spezifiziere die Operationen anhand des Modells. Vorteile: knapp und genau; Nachteile: erfordert Vorwissen, kann umständlich werden; Gefahr des Überspezifizierens. Als Modelle können z.B. mathematische Objekte oder Haskell-Datentypen gewählt werden.
    • kurze Bemerkungen zur algebraischen Spezifikation: kein Modell für die Daten; Spezifikation erfolgt durch axiomatische Beziehungen der Operationen untereinander. Eignet sich gut für mathematische und formale Analyse, wird aber schnell kompliziert und abstrakt.
    • Implementierungen des ADT Prioritätswarteschlange:
      • unsortierte und sortierte verkettete Liste
      • verkette Liste mit zwei Ebenen: fixiere Parameter m. Speichere Elemente in mehreren sortierten verketteten Listen, alle bis auf die letzte mit genau m Elementen, die letzte Liste mit höchstens m Elementen, verkette die Minima der Listen untereinander. Bei den Operationen (vor allem deleteMin) gibt es einen trade-off zwischen der Anzahl und der Läge der Listen. Wenn die maximale Größe der Prioritätswarteschlagen N bekannt ist, lässt sich Laufzeit O(sqrt(N)) pro Operation erreichen
  • Dienstag, den 14. 11. 2017
    • weitere Implementierungen des ADT Prioritätswarteschlange
  • Donnerstag, den 16. 11. 2017
    • Bottom-Up Heap Konstruktion
    • ADT Wörterbuch/Dictionary/Map: kann Eintrage speichern, nachschlagen und löschen
    • Hashing
      • K Schlüsselmenge, V Wertemenge, Ziel: speichere Teilmenge S von K x V. Übliche Situation: S ist viel kleiner als K
      • Idee: speichere S in einem Array, indiziert durch K. Problem: K ist sehr groß und besteht nicht notwendigerweise aus Zahlen. Lösung: wähle eine Hashfunktion h : K -> {0, ..., N-1}, welche jedem Schlüssel einen Platz in dem Array zuweist.
      • Wenn K größer ist als N, kann es zu Kollisionen kommen (zwei verschiedene Schlüssel erhalten den gleichen Platz im Array). Möglichkeiten der Kollisionsbehandlung:
        • Verkettung: alle Einträge im selben Platz.
        • offene Adressierung: wenn Platz schon besetzt, suche einen neuen.
        • Kuckuck: wenn Platz schon besetzt, schaffe Platz
  • Dienstag, den 21. 11. 2017
    • Hashtabelle: Array + Hashfunktion + Strategie zur Kollisionsbehandlung
    • Wahl der Hashfunktion: hashCode von K nach Z (ganze Zahlen), Kompressionsfunktion von Z nach {0, ..., N-1}.
    • Hashfunktion soll die Schlüssel möglichst gut streuen und soll alle Muster in den Schlüsseln in S zerstören (d.h., h soll sich wie eine zufällige Funktion verhalten.
    • Verkettung: Beschreibung der Operationen.
    • Analyse von Hashing mit Verkettung
      • Annahme: die Hashfunktion verhält sich zufällig.
      • Dann: die erwartete Zeit pro Operation ist O(1+|S|/N).
      • |S|/N heißt Belegungsfaktor. Wenn der Belegungsfaktor O(1) ist, so auch die Laufzeit. In der Praxis möchte man den Belegunsfaktor konstant halten (etwa bei 0,75) (-> dynamisches Array)
      • Vorteile: einfach, schnell
      • Nachteile: Platzbedarf, Cacheperformance
  • Donnerstag, den 23. 11. 2017
    • universelles Hashing
      • Die Annahme einer zufälligen Hashfunktion ist unrealistisch (müssen die zufällige Funktion wählen und speichern).
      • Aber: wir können die Funktion aus einer wesentlich kleineren Menge wählen, und die Laufzeitanalyse gilt immer noch
    • offene Adressierung mit linearem Sondieren
      • speichere alle Einträge im Array
      • wenn ein Platz besetzt ist, suche im Array nach dem nächsten freien Platz
      • bei suche bis zum ersten NULL Eintrag
      • Markiere gelöschte Einträge mit einem speziellen Eintrag DELETED, baue die Tabelle regelmäßig neu auf
    • Pseudocode und theoretische Garantien für offene Adressierung
      • im Erwartungswert benötigen alle Operation O(1) Zeit (wenn der Belegungsfaktor klein genug und die Hashfunktion zufällig ist)
      • Vorteile: geringer Platzbedarf, Nachteile: DELETED Einträge müllen die Tabelle zu; Klumpenbildung (wenn viele Schlüssel in eng beieinander liegende Positionen abgebildet werden)
  • Dienstag, den 28. 11. 2017
    • Kuckuck
      • verwende zwei Hashfunktionen, jeder Eintrag kann an zwei möglichen Positionen stehen (O(1) worst-case Nachschlagen und Löschen)
      • beim Einfügen kann die Position schon besetzt sein verschiebe den vorhandenen Eintrag an die Alternativposition. Falls diese schon besetzt ist, verschiebe den dortigen Eintrag, usw. Falls die Tabelle voll ist oder ein Kreis entsteht, baue die Tabelle mit neuen Hashfunktionen neu auf. Pseudocode
      • Wenn der Belegungsfaktor klein genug und die Hashfunktionen zuällig sind, so benötigt Einfügen O(1) erwartete amortisierte Zeit. Beweis noch ein Beweis
      • Vorteile: O(1) worst-case Laufzeit für Lookups, einfach; Nachteile: viele Verschiebeoperationen, Einfügen kann zu vollständigem Neuaufbau der Tabelle führen
    • Weitere Anwendungen von Hashfunktionen
      • Hashfunktionen bieten eine Möglichkeit, eine große, potentiell unendliche Schlüsselmenge auf einen kleinen Bereich abzubilden.
      • Dabei sollen Kollissionen möglichst unwahrscheinlich sein: wenn der Wertebereich N Elemente besitzt, ist bei einer zufälligen Hashfunktion die Kollisionswahrscheinlichkeit bei 1/N.
      • Wenn N mittelgroß ist, z.B., N=2^128 oder N=2^256, so sind Kollisionen bei zufäliger Hashfunktion praktisch ausgeschlossen.
      • Einsicht aus der Komplexitätstheorie: Wenn eine Funktion genügend kompliziert ist, lässt sie sich praktisch nicht von einer zufälligen Funktion unterscheiden.
      • Verwendung von komplizierten Hashfunktionen als Message Digest/Prüfsumme/Fingerabdruck, um die Integrität von großen Daten sicherzustellen
      • Hoffnung: Ein Widersacher hat keine andere Möglickeit, als N verschiedene zufällige Urbilder zu probieren, bis eine Kollision gefunden ist. Der Hashwert legt das Urbild praktisch fest.
      • Anwendung in Datenstrukturen: Hashzeiger. Speichere mit dem Verweis auf ein Objekt auch einen Hashwert der Daten in dem Objekt. Dadurch wird die Integriät des Zeigers sicher gestellt.
      • Verwendung von Hashzeigern in einer verketteten Liste ermöglicht ein tamper proof write only log. Diese Datenstruktur nennt man Blockchain.
  • Donnerstag, den 30. 11. 2017 (vertreten von Jonas Cleve)
    • der ADT geordnetes Wörterbuch
      • wie Wörterbuch, aber die Schlüsselmenge K ist geordnet.
      • put(k,v), get(k), remove(k)
      • max, min: liefere maximalen und minimalen Schlüssel
      • pred(k): liefere den größten Schlüssel kleiner k im Wörterbuch (Vorgänger)
      • succ(k): liefere den kleinsten Schlüssel größer k im Wörterbuch (Nachfolger)
    • Skiplisten
      • speichere eine Hierarchie von Listen L0, L1, .... L0 speichert alle Einträge, L(i+1) speichert jeden Eintrag von L(i) mit Wahrscheinlichkeit
      • Pseudocode für die Operationen
      • Erwarteter Platzbedarf O(n), erwartete Höhe O(log n), erwartete Suchzeit O(log n), wenn n Einträge gespeichert werden
      • Originalarbeit
  • Dienstag, den 05. 12. 2017
    • Analyse von Skiplisten: erwartete Suchzeit ist O(log n).
    • Bäume: Baum, gewurzelter Baum, Höhe, Blatt, Elternknoten, Kindknoten, binärer Baum
    • binärer Suchbäum: gewurzelter geordneter binärer Baum, welcher die Einträge in den Knoten speichert und die binäre Suchbaumeigenschaft hat: für jeden Knoten mit Schlüssel k sind alle Schlüssel im linken Teilbaum kleiner als k und alle Schlüssel im rechten Teilbaum größer als k.
  • Donnerstag, den 07. 12. 2017 (vertreten von Jonas Cleve)
    • Operationen auf einem binären Suchbaum am Beispiel.
    • Pseudocode für die Operationen.
    • Alle Operationen haben worst-case Laufzeit O(Höhe des Baums).
    • Im schlimmsten Fall kann der Baum degenerieren und Höhe n-1 haben (z.B., wenn man 1, 2, ..., n in dieser Reihenfolge einfügt).
    • AVL-Bäume
  • Dienstag den 12. 12. 2017 (vertreten von Jonas Cleve)
    • AVL-Bäume
      • höhenbalancierte Bäume; für jeden inneren Knoten unterscheiden sich die Höhen der Unterbäume um höchstens 1.
      • Die Höhenbalancierung gewährleistet Höhe O(log n).
      • Strukturelle Operationen auf Binärbaumen:
        • Einfachrotationen: Linksrotation (l-Rotation), Rechtsrotation (r-Rotation)
        • Doppelrotationen: lr-Rotation (erst links, dann rechts), rl-Rotation (erst rechts, dann links)
      • Wenn u ein Knoten ist, bei dem sich die Höhen der Unterbäume um genau 2 unterscheiden, und alle Nachkommen von u ausgeglichen sind, so gibt es immer eine (l-,r-,lr-, oder rl-)Rotation, die den Teilbaum bei u ausgleicht.
      • Einügen und Löschen in AVL-Bäume: füge ein bzw. lösche wie in einem herkömmlichen BSB, verfolge dann den Pfad zur Wurzel zurück und führe geeignete Rotationen durch, um alle Knoten auf dem Pfad auszugleichen.
      • Vorteile: O(log n) worst-case Laufzeit; geringer Speicherbedarf
      • Nachteile: umständliche Implementierung (Fallunterscheidung); ggf. sind viele Rotationen nötig
    • Bemerkungen zu rot-schwarz Bäumen
      • Lockern die Baumstruktur im Vergleich zu AVL-Bäumen weiter, um weniger Umstrukturierungen beim Einfügen und Löschen vornehmen zu müssen
      • Jeder Knoten ist rot oder schwarz. Die Färbung muss gewisse Bedingungen erfüllen. Dies gewährleistet Höhe O(log n).
      • Einfügen und Löschen ist ähnlich wie in AVL-Bäumen, aber nun kann die Struktur auch durch Umfärben der Knoten wiederhergestellt werden. Dadurch muss man weniger oft rotieren, aber es sind viele Fälle zu unterscheiden
      • Populäre Datenstruktur, die oft implementiert wird. Zum Beispiel in der Java-Bibliothek, der C++-STL, oder im Completely-Fair-Scheduler des Linux-Kernel.
  • Donnerstag, den 14. 12. 2017
    • Probeklausur
  • Dienstag, den 19. 12. 2017
    • (a,b)-Bäume
      • a,b sind natürliche Zahlen, mit b >= 2a-1 und a >= 2.
      • Jeder Knoten hat Grad höchstens b. Die Wurzel hat Grad mindestens 2, jeder andere innere Knoten hat Grad mindestens a.
      • Die Wurzel speichert zwischen 1 und b-1 Schlüssel, alle anderen Knoten speichern zwischen a-1 und b-1 Schlüssel,
      • Die binäre Suchbaumeigenschaft wird entsprechend auf mehrere Kinder verallgemeinert.
      • Alle Blätter haben die gleiche Tiefe.
      • Die Tiefe ist O(log n/log a).
      • Die Suche funktioniert wie bei BSBs, entsprechend angepasst für die Mehrwegknoten. Die Laufzeit ist O(b log n/log a).
      • Einfügen in (a,b)-Bäumen: suche bis zum Blatt, füge den Eintrag in das entsprechende Blatt ein. Wenn das Blatt überläuft (b Einträge), spalte es und füge den mittleren Schlüssel in den Elternknoten ein. Falls nötig, spalte diesen, usw., bis zur Wurzel. Laufzeit O(b log n / log a).
      • Löschen in (a,b)-Bäumen
        • Wenn der zu löschende Eintrag in einem inneren Knoten liegt, ersetze ihn durch seinen Nachfolger und lösche diesen aus einem Blatt.
        • Löschen aus einem Blatt: entferne den Eintrag, wenn das Blatt mindestens a Einträge enthält, ist nichts zu tun; ansonsten, versuche, einen Eintrag von einem Geschwisterknoten zu borgen; wenn das nicht geht, verschmelze mit einem Geschwisterknoten; evtl. läut nun der Elternknoten unter, wiederhole, die Prozedur bis es nicht mehr nötig ist.
      • Anwendungen: (2,4)-Bäume sind äquivalent zu Rot-Schwarz-Bäumen; als externe Datenstrukturen in Datenbanksystemen oder Dateisystemen (z.B., Btrfs, NTFS)
      • Mehr Details zu den Operationen gibt es hier.
  • Donnerstag, den 21. 12. 2017
    • Zeichenketten: endliche Folgen von Symbolen aus einem Alphabet Sigma
    • Kodes:
      • weise jedem Symbol aus dem Alphabet eine Bitfolge zu.
      • Zum Kodieren eines Strings, hänge die entsprechenden Bitfolgen aneinander.
      • Desiderata: (i) eindeutige Dekodierbarkeit, (ii) möglichst kurzes Kodewort (alternativ: (ii) hohe Fehlertoleranz)
      • präfixfreie Kodes sind Kodes, bei denen kein Kodewort Präfix eines anderen Kodeworts sind
      • präfixfreie Kodes lassen sich immer eindeutig dekodieren
      • präfixfreie Kodes lassen sich als Baum darstellen
    • Huffman-Kompression
      • liefert einen optimalen Präfixkode für gegebene Häufigkeiten
      • gieriger Algorithmus: treffe lokal optimale Entscheidungen, und hoffe, ein global optimales Ergebnis zu erzielen
      • Baue den Kodierbaum inkrementell: starte mit einem Blatt für jedes Zeichen, beschrifte die Blätter mit den Häufigkeiten; vereinige diejenigen Unterbäume, welche die geringsten Häufigkeiten haben, addiere die Häufigkeiten, wiederhole, bis nur noch ein Baum übrig ist. Das Ergebnis heißt Huffman-Baum
  • Dienstag, den 09. 01. 2018
    • Huffman-Kodes sind optimal.
      • Lemma: Für zwei Zeichen a, b mit geringsten Häufigkeiten existiert immer ein optimaler Präfixkode, in dem a und b Geschwister sind.
      • Beweis des Satzes durch Induktion nach der Alphabetgröße k: für k=2 ist die Aussage klar. Argument für den Schritt: wenn es für ein Alphabet der Größe k einen besseren Präfixkode gäbe als den Huffman-Kode, könnte man mit Hilfe des Lemmas auch einen besseren Präfixkode als den Huffmankode für Alphabetgröße k-1 konstruieren, im Widerspruch zur Induktionsannahme.
    • Bemerkungen zur Datenkompression
      • Huffmankodes sind optimal, aber wir machen drei Annahmen: 1. der Kode ist präfixfrei; 2. wir kodieren Zeichen für Zeichen; 3. die Kompression ist verlustfrei
      • Annahme 2 kann man auf verschiedene Weisen umgehen: (i) Lauflängenkodierung: speichere sich wiederholende Zeichen nur einmal mit der Anzahl. Verwendet z.B. für das PCX-Bildformat. (ii) Kode mit Wörterbuch: z.B. LZW. Sich wiederholende Zeichenketten werden durch ein Zeichen abgekürzt. Benutzt z.B. im GIF Format. LZW war seinerzeit patentiert, was große Diskussionen auslöste.
      • Um Annahme 3 zu umgehen nehmen wir an, dass es akzeptabel ist, unwichtige Informationen zu entfernen. Unwichtige Information wird durch eine geeignete Transformation der Daten identifiziert. Verwendet z.B. in JPEG oder MP3
  • Donnerstag, den 11. 01. 2018
    • Ähnlichkeit von Zeichenketten: diff, fc, längste gemeinsame Teilfolge, Editierabstand
    • finden einer lägsten gemeinsamen Teilfolge (LGT) der Zeichenketten s und t.
      • Zunächst berechnen wir nur die Länge einer solchen LGT (LLGT).
      • Rekursiver Ansatz: betrachte das jeweils letzte Zeichen von s und t (oder auch das erste). Wenn diese beiden Zeichen gleich sind, so ist LLGT= 1 + die LLGT von s' und t', die Wörter, die man aus s und t erhält, indem man jeweils das letzte Zeichen streicht. Wenn diese beiden Zeichen nicht gleich sind, bestimme rekursiv die LLGTs von s' und t sowie von s und t' und nimm das Maximum der beiden Lösungen.
      • Sobald man diese Rekursion hat, kann man sie unmittelbar als Formel aufschreiben und implementieren.
      • Problem: Die Implementierung ist ineffizient und hat exponentielle Laufzeit.
      • Aber: Viele Teilprobleme wiederholen sich. Daher können wir eine Tabelle zur Speicherung der Zwischenergebnisse benutzen. Dies nennt man dynamisches Programmieren.
      • Zwei Möglichkeiten der Implementierung: (i) top down als Rekursion, die aber immer in der Tabelle nachschaut, ob ein erneuter Rekursionsaufruf wirklich nötig ist; (ii) bottom up, indem man die Tabelle von unten durch Schleifen auffüllt. Möglichkeit (ii) ist oft vorzuziehen, da sie zu kürzerem und effizienterem Code führt.
      • Sobald man die Tabelle hat, kann man die LGT bestimmen, indem man einen optimalen Weg durch die Rekursion rekonstruiert (bzw. in einer zweiten Tabelle mitspeichert).
      • Eine Beispielimplementierung im Pseudocode gibt es hier.
  • Dienstag, den 16. 01. 2018
    • Suche in Zeichenketten. Der naive Algorithmus und der Algorithmus von Rabin-Karp: Notizen.
  • Donnerstag, den 18. 01. 2018
    • Wörterbücher für Zeichenketten: Tries
      • Tries sind eine spezialisierte Datenstruktur, die eine Menge von Zeichenketten speichern und die Operationen des ADT geordnetes Wörterbuch zur Verfügung stellen.
      • Ein Trie ist ein gewurzelter Mehrwegbaum: jeder Knoten hat zwischen einem und S Kinder, wobei S = |Sigma| die Alphabetgröße ist.
      • Die Kanten sind mit Zeichen aus Sigma beschriftet, so dass für jeden Knoten jedes Zeichen höchstens einmal als Label einer Kindkante vorkommt.
      • Die gespeicherten Zeichenketten lassen sich erhalten, indem man für jedes Blatt v die Kantenbeschriftungen von der Wurzel zu v aneinanderhängt.
      • Problem: Was, wenn ein String Präfix eines anderen ist? Lösung 1: Führe zusätzliche Markierungen im Baum ein, um das Wortende anzuzeigen. Nachteil: Verkompliziert die Algorithmen und die Strukture. Lösung 2: Führe ein spezielles Zeichen ein, welches das Wortende anzeigt und nicht im Alphabet vorkommt, und füge dieses Zeichen implizit an jede gespeicherte Zeichenkette an. Beachte: Lösung 2 ist im wesentlichen äquivalent zu Lösung 1, aber konzeptionell simpler, da man die Algorithmen einfacher halten kann.
    • Tries unterstützen die Operationen des ADT geordnetes Wörterbuch in Zeit O(r|Sigma|), wobei r die Gesamtläange der Zeichenketten ist, die von der Operation angefragt bzw. zurückgegeben werden.
    • Der Platz für einen Trie ist proportional zur Gesamtlänge der darin gespeicherten Schlüssel.
    • Komprimierte Tries/Patricia-Tries: ersetze lange Ketten von Knoten mit nur einem Kind durch eine Kante, die mit dem entsprechenden Teilstring beschriftet ist. Dadurch hat der Trie nur O(l) Knoten (l = Anzahl der im Trie gespeicherten Schlüssel. Asymptotisch ändert sich aber nichts am Platzbedarf.
    • Suffixbaum: ein komprimierter Trie für alle Suffixe einer gegebenen Zeichenkette s. Um die Gesamtgröße linear zu halten, speichert man an den Kanten anstelle von Teilstrings aus s nur Zeiger an die entsprechenden Stellen in s.
    • Ein Suffixbaum lässt sich in mit einem speziellen Algorithmus in linearer Zeit berechnen (Das naive Einfügen aller Suffixe könnte quadratische Zeit benötigen).
    • Suffixbäume haben viele Anwendungen im Bereich der Stringsuche. Ein paar sind auf der Wikipedia-Seite aufgelistet.
    • Graphen–Grundbegriffe, Beispiele
  • Dienstag, den 23. 01. 2018
    • einige Algorithmische Probleme auf Graphen: Sind zwei Knoten verbunden? Zusammenhangskomponenten finden; kürzeste Wege finden (ohne und mit Kantengewichten); topologisches Sortieren; Bestimmung eines minimalen aufspannenden Baums; Bestimmung einer minimalen Kantenmenge, die man entfernen muss, um Knoten zu trennen.
    • Zwei Möglichkeiten der Darstellung im Rechner: Adjazenzmatrix und Adjazenzliste. Im Allgemeinen liefern Adjazenzlisten eine bessere Laufzeit, wenn der Graph nicht zu viele Kanten hat.
    • Tiefensuche und Breitensuche Siehe hier.
  • Donnerstag, den 25. 01. 2018
    • Breitensuche
    • Single Pair Shortest Path Problem: Finde einen kürzesten Weg von s nach t.
    • Single Source Shortet Path Problem: Finde kürzeste Wege von s zu allen anderen Knoten im Graphen
    • Teilpfadoptimalitätseigenschaft: Teilwege eine kürzesten Weges sind wieder kürzeste Wege
    • Darstelleng der kürzesten Wege von s zu allen anderen Knoten: als kürzeste-Wege-Baum: jeder Knoten v speichert einen Zeiger zu seinem Vorgänger auf einem kürzesten Weg von s nach v. Man findet den kürzesten Weg selber, indem man den Vorgängerzeigern folgt
    • Kürzeste Wege in ungewichteten Graphen: modifiziere BFS so dass sie Vorgängerzeiger und Abstände zu s speichert. Siehe hier.
  • Dienstag, den 30. 01. 2018
    • kürzeste Wege in gewichteten Graphen: der Algorithmus von Dijkstra
      • Annahme: alle Kantengewichte sind nichtnegativ
      • Modifiziere den BFS-Algorithmus für ungewichtete Graphen auf zwei Arten: 1. verwende eine Prioritätswarteschlange statt eine Warteschlange, 2. wenn die Nachbarn eines Knoten untersucht werden, müssen wir überprüfen, ob sich der Weg zum Nachbarn verkürzen lässt
      • Pseudocode hier.
      • Die Laufzeit hängt ab von der Implementierung der Prioritätswarteschlange. Wir führen |V| inserts, |V| extractMins, und O(|E|) decreaseKeys durch. Wenn ein binärer Heap zugrunde liegt, ist die Laufzeit O(|V| log |V| + |E| log |V|).
    • Dijkstra: Korrektheitsbeweis
      • Grundidee: Nenne einen Knoten verarbeitet, wenn er nicht mehr in der Prioritätswarteschlange enthalten ist. Die Werte v.d und v.pred beziehen sich auf kürzeste Wege, die nur Knoten benutzen, die schon verarbeitet sind (ggf. mit Ausnahme von v). Alle Wege zu noch nicht verarbeiteten Knoten sind mindestens so lang wie alle kürzesten Wege zu schon verarbeiteten Knoten. Wenn wir einen neuen Knoten verarbeiten, bleiben all diese Invarianten erhalten, da alle Kantengewichte nichtnegativ sind und wir den Knoten mit minimalem Abstand verarbeiten.
  • Donnerstag, den 01. 02. 2018
    • A*-Suche mit konsistentem Schätzer:
      • Wollen einen kürzesten s-t-Pfad.
      • Zusätzlich zu dem Graphen kennen wir noch einen Schätzer: eine Funktion h: V -> R+, die den Abstand von jedem Knoten v nach t schätzt.
      • h heißt konsistent, wenn für jede Kante e=uv gilt: h(u) <= e.length + h(v)
      • A*-Suche entspricht Dijkstras Algorithmus mit veränderten Kantengewichten: Für eine Kante e = uv ist e.length' := e.length + h(v) - h(u)
      • Konsistenz stellt sicher, dass die neuen length' Längen nichtnegativ sind.
      • Kanten, die auf das Ziel zuführen werden kürzer, Kanten, die vom Ziel weggehen werden länger.
      • Die Länge eines jeden Weges von s nach t ändert sich um h(t) - h(s) (Teleskopsumme). Daher ist ein kürzester Weg für die neuen Gewichte auch ein kürzester Weg für die alten Gewichte (die Änderung hängt nicht vom Weg ab, nur von Endpunkten).
      • Wenn der Schätzer gut ist, müssen wir wesentlich weniger Knoten besuchen als bei normalem Dijkstra
      • Wenn der Schätzer gut ist, müssen wir wesentlich
      • Anwendungen: Routenplanung; Suchprobleme in der künstlichen Intelligenz
  • Dienstag, den 06. 02. 2018
    • All-Pairs-Shortest-Paths: Floyd-Warshall
      • APSP-Problem: Finde einen kürzesten Weg von u nach v für alle Knotenpaare u und v.
      • Wenn alle Kantengewichte nichtnegativ sind und der Graph wenig Kanten enthält, kann man Dijkstra für jeden Knoten ausführen
      • Allgemeiner Algorithmus mit dynamischem Programmieren: nummeriere Knoten beliebig von 1 bis n. Für k = 0 bis n, finde rekursiv die Längen aller kürzeten Wege, welche nur Zwischenknoten mit Nummer 1 bis k benutzen.
      • Der Algorithmus von Floyd-Warshall lässt sich mit O(n^3) Zeit und O(n^2) Platz implementieren (n = Anzahl der Knoten). Mit O(n^3) Platz kann man auch die kürzesten Wege selbst finden.
    • MST-problem (minimum spanning tree)
      • gegeben: Graph G=(V, E), ungerichtet, gewichtet, zusammenhängend
      • gesucht: Kantenmenge T mit minimalem Gewicht, so dass (V, T) ein Baum ist
      • allgemeine Strategie: gierig, beginne mit leerer Kantenmenge, füge sukzessive sichere Kanten hinzu.
      • Eine Kantenmenge A heißt sicher, falls es einen MST gibt, der A enthält
      • Schnittlemma: Sei A eine sichere Kantenmenge, und S ein Schnitt, welcher von keiner Kante aus A überquert wird. Sei e eine Kante von minimalem Gewicht, die S überquert. Dann ist A vereinigt mit e sicher.
  • Donnerstag, den 08. 02. 2018
    • Beweis des Schnittlemmas
    • Benutze Schnittlemma, um sichere Kanten zu finden.
    • Zwei Umsetzungen: der Algorithmus von Prim-Jarník-Dijkstra und der Algorithmus von Kruskal
    • Prim-Jarník-Dijkstra: lasse den MST von einem Startknoten s aus wachsen, nimm immer die leichteste Kante inzident zur aktuellen Zusammenhangskomponente. Implementierung wie bei Dijkstras Algorithmus für kürzeste Wege, nur mit anderem Gewichtsmanagement. Selbe Laufzeit wie bei Dijkstra.
    • Der Algorithmus von Kruskal: sortiere die Kanten, nimm immer die nächste Kante, die zwei verschiedene Zusammenhangskomponenten verbindet
  • Dienstag, den 13. 02. 2018
    • Komplexitätstheorie: Berechenbarkeitstheorie und Komplexitätstheorie; Effizienzbegriff; These von Cobham-Edmonds; Erweiterte Church-Turing These
    • Entscheidungsprobleme, Laufzeit, Turingmaschinen, Komplexitätsklassen
    • Die Komplexitätsklasse P, die Menge aller effizient entscheidbarer Sprachen: formale Definition und Beispiele.
    • Zeithierarchiesatz: Es gibt "beliebig schwierige" entscheidbare algorithmische Probleme.
    • Probleme, die wahrscheinlich nicht in P liegen: Sudoku und Sokoban.
    • Wenn ein Sudokupuzzle eine Lösung hat, kann man diese effizient aufschreiben und überprüfen.
    • Bei Sokoban ist das wahrscheinlich nicht so. Wenn ein Sokoban-Puzzle eine Lösung hat, kann diese extrem lang sein, so dass man sie nicht effizient darstellen kann
  • Donnerstag, den 15. 02. 2018
    • NP: Die Klasse der Entscheidungsprobleme, für die es effizient überprüfbare Zertifikate von polynomieller Länge gibt.
    • Alle Probleme aus P sind in NP. Sudoku ist in NP, Sokoban wahrscheinlich nicht.
    • Weitere Probleme in NP: Clique, Rucksack, Circuit-SAT.
    • Reduktionen und NP-vollständige Probleme
    • Sudoku ist NP-vollständig, Sokoban ist PSPACE-vollständig.
    • Das P-NP-Problem
    • Schluss
  • Dienstag, den 20. 02. 2018
    • Klausur
  • Montag, den 26. 03. 2018
    • Klausureinsicht
  • Donnerstag, den 12. 04. 2018
    • Nachklausur
  • Dienstag, den 24. 04. 2018 (geplant, SR006)
    • Einsicht der Klausur und der Nachklausur

Empfohlene Vorkenntnisse

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, d.h., 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 20. Februar 2018, von 14–16 Uhr, im Henry-Ford-Bau. Die Nachklausur findet statt am Donnerstag, den 12. April 2018, von 10–12 Uhr, im Hörsaal 2 der Silberlaube.

Für den Scheinerhalt muss man

Die erfolgreiche Teilnahme am Übungsbetrieb und das Bestehen der Abschlussprüfung sind unabhängige Leistungen. Das Modul wird benotet. Die Note beruht nur auf dem Ergebnis der Abschlussprüfung.

Termin/Tutorium

Die Vorlesung findet statt Dienstag und Donnerstag, 14–16 Uhr, im großen Hörsaal in der Takustraße 9. Zusätzlich gibt es eine Zentralübung. Diese wird von Katharina Klost gehalten und findet Freitag von 14–16 Uhr im großen Hörsaal in der Takustraße 9 statt. In der Zentralübung werden die Übungausfgaben besprochen und vertieft. Die Teilnahme an der Zentralübung ist freiwillg. Die dezentralen Tutorien werden von vier studentischen Tutor_innen durchgeführt (Benjamin Aram Berendsohn, Tobias Gleißner, Florian Hartmann und Anja Wolffgramm).

Dienstag
12:00–14:00 Takustraße 9, Seminarraum 055 Benjamin Aram Berendsohn
16:00–18:00 Takustraße 9, Seminarraum 051 Florian Hartmann
Mittwoch
08:00–10:00 Takustr. 9, Seminarraum 046 Benjamin Aram Berendsohn
08:00–10:00 Takustr. 9, Seminarraum 053 Tobias Gleißner
10:00–12:00 Takustraße 9, Seminarraum 055 Anja Wolffgramm
12:00–14:00 Takustraße 9, Seminarraum 006 Florian Hartmann
12:00–14:00 Takustraße 9, Seminarraum 051 Benjamin Aram Berendsohn
12:00–14:00 Takustraße 9, Seminarraum 055 Anja Wolffgramm
16:00–18:00 Arnimallee 6, Seminarraum 032 Tobias Gleißner
16:00–18:00 Takustraße 9, Seminarraum 049 Florian Hartmann
Freitag
14:00–16:00 Takustr. 9, großer Hörsaal Zentralübung
Katharina Klost

Sprechzeit des Dozenten: Dienstag 13–14 Uhr in Zimmer 112 und nach Vereinbarung.

Übungszettel

Die Übungszettel werden jede Woche hier verlinkt. Sie werden ausschließlich online erscheinen. Die normale Bearbeitungszeit ist von Montag bis zum Freitag 11 Tage später. Die Zettel sind bis 10 Uhr in die entsprechenden Tutorenfächer abzugeben. Die Bearbeitung erfolgt in Zweiergruppen. Eine LaTeX-Schablone für die Übungszettelabgabe findet sich hier (mit Beispielprogramm).

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

Nr.AusgabeAbgabe pdftexBemerkungen
1 06.10.2017 27.10.2017  
2 23.10.2017 03.11.2017  
3 30.10.2017 10.11.2017  
4 06.11.2017 17.11.2017  
5 13.11.2017 24.11.2017 Heaps
6 20.11.2017 01.12.2017 Hashing (aktualisiert!)
Aufgabe 2(c) verbessert
7 27.11.2017 08.12.2017  
8 04.12.2017 15.12.2017 Skiplisten
Kuckucks-Hashing
binäre Suchbäume
9 11.12.2017 22.12.2017  
Probeklausur 14.12.2017 keine Englisch
10 18.12.2017 12.01.2018 Weihnachtszettel
11 08.01.2018 19.01.2018 (a, b)-Bäume
12 15.01.2018 26.01.2018 LCS
Suche in Zeichenketten
13 22.01.2018 02.02.2018 Vorletztes Aufgabenblatt.
14 29.01.2018 09.02.2018 Letztes Aufgabenblatt.
Impressum