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.
- 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