gehaltene Vorlesungen über Algorithmen und Programmierung III, WS 2013/14

• Dienstag, den 15. 10. 2013
  • 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 17. 10. 2013
  • 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 22. 10. 2013
  • 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.
  • Theoretischen 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
  • Ein Beispielprogramm auf der RAM mit genauer Analyse
• Donnerstag, den 24. 10. 2013
  • 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
    • Die überschätzten Fibonacci-Zahlen
    • Rekursionsbäume zur Veranschaulichung und Analyse
    • dynamisches Programmieren: Rekursion + Tabelle, um wiederkehrende Resultate zwischenzuspeichern
• Dienstag, den 29. 10. 2013
  • Einfache Datenstrukturen: Schlange und Stapel/Keller
    • Implementierungen: verkettete Liste oder Array fester Grösse oder dynamisch wachsendes Array
    • Relevantes Material aus ALP2
  • 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
• Donnerstag, den 31. 10. 2013
  • 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
• Dienstag, den 05. 11. 2013
  • 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 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
• Donnerstag, den 07. 11. 2013
  • weitere Implementierungen des ADT Prioritätswarteschlange
    • binärer Heap: Notizen
    • Bottom-Up Heap Konstruktion
• Dienstag, den 12. 11. 2013
  • 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
    • 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.
• Donnerstag, den 14. 11. 2013
  • 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
  • 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 get und remove, suche bis zum ersten NULL Eintrag
    • Markiere gelöschte Einträge mit einem speziellen Eintrag DELETED, baue die Tabelle regelmäßig neu auf
• Dienstag, den 19. 11. 2013
  • 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)
  • 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
    • Vorteile: O(1) worst-case Laufzeit für Lookups, einfach; Nachteile: viele Verschiebeoperationen, Einfügen kann zu vollständigem Neuaufbau der Tabelle führen
  • Entwurfsmuster/Design patterns: Motivation und Definition
  • Iteratoren
    • Problem: wollen alle Einträge in einem Wörterbuch (allgemeiner: in einer Kollektion) effizient durchlaufen. Dabei soll das Geheimnisprinzip gewahrt bleiben.
    • Entwurfsmuster Iterator: lagere die Funktionalität zum Durchlaufen in eine eigene Klasse aus.
    • Teilnehmer:
      • AbstractCollection: biete Methode iterator(), die ein Iterator-Objekt erzeugt. Teil des ADT
      • AbstractIterator: stellt den aktuellen Zustand eines Durchlaufungsvorgangs dar, bietet Methoden hasNext(), next(), remove(). Teil des ADT
      • ConcreteCollection: Implementierung des ADT. Erzeugt einen konkreten Iterator
      • ConcreteIterator: Implementierung eines Iterators, ist an eine ConcreteCollection gekoppelt
    • Vorteile: mehrere Duchläufe gleichzeitig möglich; die Schnittstelle des ADT bleibt schlank; verschiedene ConcreteIterators können verschiedene Durchlaufungsstrategien anbieten
    • In Java: Interfaces Iterable und Iterator werden von praktisch allen Collections unterstützt; for each Schleife: for (E e: Collection) {...} ist äquivalent zu Iterator<E> iter = Colletion.iterator(); while(iter.hasNext()) {E e = iter.next();...}
• Donnerstag, den 21. 11. 2013
  • 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 26. 11. 2013
  • 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.
  • 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).
• Donnerstag, den 28. 11. 2013
  • 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.
• Dienstag, den 03. 12. 2013
  • Abschluss AVL-Bäume
    • 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.
  • (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).
• Donnerstag, den 05. 12. 2013
  • 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.
  • 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
• Dienstag, den 10. 12. 2013
  • 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
  • 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.
• Donnerstag, den 12. 12. 2013
  • Abschluss Huffman-Kompression
  • 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
  • Ähnlichkeit von Zeichenketten: diff, fc, längste gemeinsame Teilfolge, Editierabstand
• Dienstag, den 17. 12. 2013 (vertreten durch Paul Seiferth)
  • 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.
  • Suche in Zeichenketten. Der naive Algorithmus und der Algorithmus von Rabin-Karp: Notizen.
• Donnerstag, den 19. 12. 2013 (vertreten durch Paul Seiferth)
  • Abschluss Rabin-Karp
  • 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.
• Dienstag, den 07. 01. 2014 (vertreten durch Yannik Stein)
  • 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
• Donnerstag, den 09. 01. 2014 (vertreten durch Yannik Stein)
  • 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.
  • Die Operationen des ADT Graph.
  • 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 14. 01. 2014
  • 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|).
• Donnerstag, den 16. 01. 2014
  • 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.
• Dienstag, den 21. 01. 2014
  • 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(b) - h(v)
    • 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
  • Negative Kantengewichte
    • Anwendungen: Geldumtausch, kürzeste Wege mit Mitnahmeeffekten
• Donnerstag, den 23. 01. 2014
  • Algorithmus von Bellman-Ford
    • Negativer Kreis: gerichteter Kreis, dessen Kantengewichte zu einer negativen Zahl addieren.
    • Annahme: G enthält keine negativen Kreise. Sonst ist das SSSP-Problem nicht wohldefiniert.
    • Operation improve: Gegeben eine Kante e=ab, teste, ob der bisher beste Weg zu b verbessert werden kann, indem man den bisher besten Weg zu a nimmt und danach über e geht.
    • Andere Sicht auf Dijkstra: benutze eine Prioritätswarteschlange, um improve in der richtigen Reihenfolge für jede Kante genau einmal aufzurufen. Das funktioniert nicht mehr bei negativen Gewichten.
    • Bellman-Ford: Rufe improve oft genug für jede Kante auf. Es genügen |V|-1 Aufrufe pro Kante.
    • Lemma: Nach i Iterationen von Bellman-Ford haben wir alle kürzesten Wege mit höchstens i Kanten gefunden.
    • Bellman-Ford findet alle kürzesten Wege von s in O(|E||V|) Schritten. Man kann den Algorithmus so modifizieren, dass er auch negative Kreise findet, falls vorhanden.
  • 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.
• Dienstag, den 28. 01. 2014
  • MST-problem (minimum spanning tree)
    • gegeben: Graph G=(V, E), gerichtet, 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.
    • Benutze Schnittlemma, um sichere Kanten zu finden.
    • Drei Umsetzungen: der Algorithmus von Prim-Jarník-Dijkstra, der Algorithmus von Kruskal und der Algoirthmus von Borůvka-Sollin
    • 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.
• Donnerstag, den 30. 01. 2014
  • Der Algorithmus von Kruskal: sortiere die Kanten, nimm immer die nächste Kante, die zwei verschiedene Zusammenhangskomponenten verbindet
  • Zur Verwaltung der Zusammenhangskomponenten brauchen wir eine Union-Find-Struktur: Verwalte eine Partition eines Universums in Teilmengen, so dass wir zwei Teilmengen der Partition vereinigen können (UNION) und für jedes Element des Universums die Menge der Partition bestimmen können, die es enthält (FIND)
  • Union-Find Struktur: Stelle die Partition des Universums als Wald dar. Jede Menge in der Partition entspricht einem Baum, die Menge wird repräsentiert durch die Wurzel
    • INIT(U) erzeugt einen Singleton-Knoten für jedes Element des Universums und liefert Zeiger auf diese Knoten
    • FIND(u) bekommt einen Zeiger auf den Knoten für u und läuft in dem entsprechenden Baum bis zur Wurzel, dem Repräsentanten der entsprechenden Menge
    • UNION(u1, u2): bekommt zwei Zeiger auf Elemente im Universum, läuft zu den entsprechenden Wurzeln, und hängt die Wurzel für u2 unter die Wurzel für u1, oder umgekehrt
  • Problem: die Bäume können zu hoch werden, und FIND kann sehr lange dauern
  • Zwei Heuristiken schaffen Abhilfe:
    • Union-by-rank: Speichere die Höhe eines jeden Baumes, hänge bei UNION den kleineren Baum unter den höheren (garantiert O(log n) worst-case Laufzeit für FIND-SET)
    • Pfadkompression: bei FIND, hänge alle Knoten auf dem Pfad von u zur Wurzel unter die Wurzel
    • Satz: Union-by-rank und Pfadkompression resultieren zusammen in O(alpha(n)) amortisierter Laufzeit pro Operation. Hierbei ist alpha(n) die inverse Ackermann-Funktion, eine Funktion, die sehr langsam wächst
• Dienstag, den 04. 02. 2014
  • Der Algorithmus von Borůvka-Sollin: Mischung aus Kruskal und Prim: lasse mehrere Zusammenhangskomponenten gleichzeitig wachsen. Pseudocode hier.
  • Bemerkungen zu schnellen MST-Algorithmen
  • Graphen für Puzzles und Spiele; Spielbäume;
• Donnerstag, den 06. 02. 2014
  • Spielbäume; der Minimax und Alpha-Beta-Algorithmus
  • Komplexitätstheorie: Berechenbarkeitstheorie und Komplexitätstheorie; Effizienzbegriff; These von Cobham-Edmonds; Erweiterte Church-Turing These
• Dienstag, den 11. 02. 2014
  • Grundlagen der Komplexitätstheorie: 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
  • 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.
• Donnerstag, den 13. 02. 2014
  • Reduktionen und NP-vollständige Probleme
  • Sudoku ist NP-vollständig, Sokoban ist PSPACE-vollständig.
  • Der Satz von Cook-Levin
  • Das P-NP-Problem
  • Schluss
• Donnerstag, den 20. 02. 2014
  • Klausur
• Dienstag, den 15. 04. 2014
  • Nachklausur