gehaltene Vorlesungen über Algorithmen und Programmierung III, WS 2010/11

Dienstag, den 19. 10. 2010
- Administrativa
- Einleitung
  - In ALP3 geht es um Daten: wie kann man sie darstellen, manipulieren, auf sie zugreifen und sie speichern?
- Ein erstes Beispiel: Polynome
  - Darstellung eines Polynoms vom Grad n als Koeffizientenform
    - Addition zweier Polynome in O(n) Operationen
    - Auswerten an einer Stelle x0 in O(n) Operationen mit dem Horner Schema
    - Multiplikation zweier Polynome in O(n^2) Operationen
  - Darstelleung eines Polynoms vom Grad n durch Auswertung an mindestens n+1 verschiedenen Stellen
    - Addition zweier Polynome in O(n) Operationen
    - Auswerten an einer Stelle x0 in O(n^2) Operationen mit dem Horner Schema
    - 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)
Donnerstag, den 22. 10. 2010
- Wiederholung und Abschluss FFT
- Algorithmen: Definition und Qualitätsmerkmale
- Arten der Evaluation von Algorithmen: experimentell und theoretisch
  - Experimentelle Analyse (Testen/Benchmarking) gibt sehr konkrete Ergebnisse, ist 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.
- Zur theoretischen Analyse benötigen wir ein abstraktes Maschinenmodell, um uns über die erlaubten elementaren Schritte im Klaren zu sein.
- Definition Registermaschine/Random Access Machine (RAM)
Dienstag, den 26. 10. 2010
- Definition: Laufzeit und Speicherplatz auf der RAM
- Ein Beispielprogramm auf der RAM mit genauer Analyse
- 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)
Donnerstag, den 28. 10. 2010
- Rekursion
  - Fibonacci-Zahlen
  - Rekursionsbäume zur Veranschaulichung und Analyse
  - dynamisches Programmieren: Rekursion + Tabelle, um wiederkehrende Resultate zwischenzuspeichern
- Einfache Datenstrukturen: Schlange und Stapel/Keller
  - Möglichkeiten der Implementierung: verkettete Liste oder Array fester Grösse oder dynamisch wachsendes Array
  - Relevantes Material aus ALP2
Dienstag, den 02. 11. 2010
- 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
- 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.
Donnerstag, den 04. 11. 2010
- Erweiterung von Queue zur LNUQueue mit drei Prioritäten LOW, NORMAL, URGENT;
  - Implementiere durch Klasse mit drei Queues (low, normal, urgent), implementiere das Einfügen und Löschen durch Einfügen und Löschen in den entsprechenden Queues
  - Um Redundanzen zu vermeiden, verwenden wir eine abstrakte Oberklasse, die das Queue-Management übernimmt
  - Problem: wie können wir die Queues in einer abstraken Klasse erzeugen?
  - Lösung: das Entwurfsmuster factory method: schreibe eine abstrakte Methode zur Erzeugung in die Oberklasse, schreibe die konkreten Erzeuger in die Unterklassen
- Entwurfsmuster/Design patterns: Motivation und Definition
- ADT Prioritätswarteschlange: Definition und Anfang verbale Spezifikation
Dienstag, den 09. 11. 2010
- 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
  - 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 zB mathematische Objekte oder Haskell-Datentypen gewählt werden.
- kurze Bemerkungen zur algebraischen Spezifikation: kein Modell für die Daten, die Spezifikation erfolgt durch axiomatische Angabe der 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
Donnerstag, den 11. 11. 2010
- weitere Implementierungen des ADT Prioritätswarteschlange
  - verkette Liste mit zwei Ebenen: fixiere einen Parameter m. Speichere Elemente in mehreren verketteten Listen, alle bis auf die letzte mit genau m Elementen, die letzte Liste hat höchstens m Elemente, 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)) erreichen
  - binärer Heap: speichere Elemente in den Knoten eines vollständigen binären Baums mit der Heap-Eigenschaft (das Element im Elternknoten ist kleiner als die Elemente in den Kindknoten). Beschreibung der Operationen bubble-up und bubble-down.
- der ADT Wörterbuch: erlaubt es, Eintrage zu speichern, nachzuschlagen und zu löschen
Dienstag, den 16. 11. 2010
- 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.
  - Da K in der Regel größer ist als N, kann es zu Kollisionen kommen (d.h., 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 18. 11. 2010
- Analyse von Hashing mit Verkettung
  - Wir nehmen an, die Hashfunktion h ist zufällig gewählt
  - Unter dieser Annahme ist die erwartete Zeit pro Operation 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 von Verkettung: einfach, schnell
  - Nachteile: verschwendet Platz für die verketteten Listen
- universelles Hashing
  - Die Annahme einer zufälligen Hashfunktion in der obigen Analyse ist inpraktikabel (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 in der Hashtabelle
  - wenn ein Platz besetzt ist, suche durch das 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 Marker DELETED, baue die Tabelle in regelmäßigen Abständen neu auf
Dienstag, den 23. 11. 2010
- 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
- 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 25. 11. 2010
- 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 im Wörterbuch, der kleiner als k ist (Vorgänger)
  - succ(k): liefere den kleinsten Schlüssel im Wörterbuch, der größer als k ist (Nachfolger)
- Skiplisten
  - speichere eine Hierarchie von Listen L0, L1, ..., wobei L0 alle Einträge speichert und L(i+1) jeden Eintrag von L(i) mit Wahrscheinlichkeit 1/2 enthält
  - 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 30. 11. 2010
- Abschluss der Analyse der erwarteten Suchzeit in Skiplisten.
- 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 2. 12. 2010
- AVL-Bäume
  - höhenbalancierte Bäume; für jeden inneren Knoten gilt: der Betrag der Differenz zwischen der Höhe des linken Unterbaums und der Höhe des rechten Unterbaums ist höchstens 1.
  - Die Höhenbalancierung gewährleistet, dass ein AVL-Baum immer Höhe O(log n) hat.
  - 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, so dass sich die Höhen der Unterbäume von u um 2 unterscheiden, und alle Nachkommen von u ausgeglichen sind, so gibt es immer eine (l-,r-,lr-, oder rl-)Rotation, die den Teilbaum mit Wurzel 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 7. 12. 2010
- abschließende Worte zu AVL-Bäumen
  - Vorteile: O(log n) worst-case Laufzeit; geringer Speicherbedarf
  - Nachteile: umständlich zu implementieren (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 Umstruktierungen beim Einfügen und Löschen vornehmen zu müssen
  - Jeder Knoten hat eine Farbe: rot oder schwarz. Die Färbung muss gewisse Bedingungen erfüllen. Dadurch wird gewährleistet, dass der Baum Höhe O(log n) hat.
  - 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, so dass man weniger oft rotieren muss, aber man muss viele Fälle 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, so dass 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 viele Schlüssel, alle anderen Knoten speichern zwischen a-1 und b-1 viele 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: 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).
Donnerstag, den 9. 12. 2010
- Löschen in (a,b)-Bäumen
  - Wenn der zu löschende Eintrag in einem inneren Knoten liegt, ersetzte ihn durch seinen Nachfolger und lösche diesen aus einem Blatt.
  - Löschuen aus einem Blatt: entferne den Eintrag, wenn das Blatt mindestens a Einträge enthät, 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, d.h., 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)
  - Nachtrag, 6. 1. 2011: 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 14. 12. 2010
- 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 16. 12. 2010
- Abschluss Huffman-Kompression
- Bemerkungen zur Kompression allgemein
  - 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 zB für das PCX-Bildformat. (ii) Kode mit Wörterbuch: zB LZW. Sich wiederholende Zeichenketten werden durch ein Zeichen abgekürzt. Benutzt zB 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 zB in JPEG oder MP3
- Ähnlichkeit von Zeichenketten: diff, längste gemeinsame Teilfolge, Editierabstand
Dienstag, den 4. 1. 2011
- 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.
Donnerstag, den 6. 1. 2011
- Suche in Zeichenketten: der Algorithmus von Rabin-Karp. Details siehe hier.
- 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üre 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 11. 1. 2011
- 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 13. 1. 2011
- 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.
- Tiefensuche, die Geschichte von Theseus, Ariadne und dem Minotaurus
- Details und Pseudocode gibt es hier.
Dienstag, den 18. 1. 2011
- Breitensuche: verwende eine Schlange, um die Knoten zu speichern, gehe jeweils einen Schritt in jede Richtung.
- 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.
- 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 v untersucht werden, müssen wir überprüfen, ob sich der Weg zum Nachbarn verkürzen lässt
  - Pseudocode hier.
Donnerstag, den 20. 1. 2011
- Dijkstra: Laufzeit
  - 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 gelegt wird, 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.
- A*-Suche mit konsistenter Heuristik:
  - Wollen einen kürzesten s-t-Pfad finden.
  - Zusätzlich zu dem Graphen kennen wir noch eine Heuristik: 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=ab gilt: h(a) <= e.length + h(b)
  - A*-Suche entspricht Dijkstras Algorithmus mit veränderten Kantengewichten: Für eine Kante e = ab ist e.length' := e.length + h(b) - h(a)
  - 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 die Heuristik gut ist, müssen wir wesentlich weniger Knoten besuchen als bei normalem Dijkstra
Dienstag, den 25. 1. 2011 (vertreten durch Klaus Kriegel)
- All-Pairs-Shortest-Paths, Der Algorithmus von Floyd-Warshall
- Minimale aufspannende Bäume, eine Algorithmenschablone
Donnerstag, den 27. 1. 2011 (vertreten durch Klaus Kriegel)
- der generische MST-Algorithmus, Korrektheitsbeweis
- Zwei Umsetzungen: der Algorithmus von Prim-Jarnik-Dijkstra und der Algorithmus von Kruskal
- Prim-Jarnik-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
- 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-SET)
Dienstag, den 1. 2. 2011
- 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
  - MAKE-SET(u) erzeugt einen Singleton-Knoten für u und liefert einen Zeiger auf diesen Knoten
  - FIND-SET(u) bekommt einen Zeiger auf den Knoten für u und läft in dem entsprechenden Baum bis zur Wurzel
  - UNION(U1, U2): bekommt zwei Zeiger auf die Wurzeln für die Bäume für U1 und U2 und hängt die Wurzel für U2 unter die Wurzel für U1
- Problem: die Bäume können entarten, und FIND-SET kann sehr lange dauern
- Zwei Heuristiken schaffen Abhilfe:
  - Union-by-size: Speichere die Anzahl der Elemente für jeden Baum in der Wurzel, hänge bei UNION den kleineren Baum unter den größeren (garantiert O(log n) worst-case Laufzeit für FIND-SET)
  - Pfadkompression: bei FIND-SET, hänge alle Knoten auf dem Pfad von u zur Wurzel unter die Wurzel
  - Satz: Union-by-size und Pfadkompression zusammen resultieren in O(alpha(n)) amortisierter Laufzeit pro Operation. Hierbei ist alpha(n) die inverse Ackermann-Funktion, eine Funktion, die unheimlich langsam wächst
- Der MST-Algorithmus von Borůvka: Mischung aus Kruskal und Prim: lasse mehrere Zusammenhangskomponenten gleichzeitig wachsen. Pseudocode hier.
Donnerstag, den 3. 2. 2011
- Laufzeitanalyse Borůvka
- Bemerkungen zu schnellen MST-Algorithmen
- Graphen für Puzzles und Spiele; Spielbäume; der Minimax und Alpha-Beta-Algorithmus
Dienstag, den 8. 2. 2011 (vertreten durch Klaus Kriegel)
Donnerstag, den 10. 2. 2011 (vertreten durch Klaus Kriegel)
- Einführung in die NP-Vollständigkeitstheorie
Dienstag, den 15. 2. 2011
- Fragestunde
- Rückblick
- Ausblick
- Schlussmonolog
Donnerstag, den 17. 2. 2011
- Klausur