1
eventuell leer
2
nicht zu verwechseln mit voll: entweder Blatt oder genau zwei geordnete Kinder. Vollständig heißt, es gibt keine teilgefüllten ``Ebenen'' des Baumes.
3
'a Btree = Leaf | Node of ('a Btree * 'a * 'a Btree) oder, genauer auch 'a Btree = Leaf of 'a | Node of ('a Btree * 'a * 'a Btree), was mehr [CLR90] entspricht
4
Länge des Arrays l = 2n -1 mit 2n - 1 ³ heapsize für minimales n. Da die letzte Ebene teilgefüllt sein kann ist streng genommen der Baum nicht mehr vollständig.
5
es gibt daneben Durchlaufen in Präordnung und Postordnung.
6
Beachte: die rekursive L"osung ist endrekursiv.
7
Wenn die Schlüssel alle unterschiedlich sind, gilt für die beiden ersten Ungleichungen schärfer < anstelle £. Die erste Ungleichung gilt nur falls das linke Kind existiert.
8
einfacher Pfad: alle Knoten (des Pfades) unterschiedlich. Falls die Pfade nur von der Eltern zu den Kindern erlaubt sind, sind alle Pfade einfach!
9
= Länge des kürzesten Pfades von s zum Knoten, falls unerreichbar, Abstand = ¥.
10
Daß man 2 Farben braucht, sollte klar sein, die dritte kennzeichnet Knoten die man bereits entdeckt hat, deren adjazierene Knoten man aber noch nicht kennt. Wg. Breitenstrategie arbeitet man die Nachbarn eines neuentdeckten Knotens nicht sofort ab. Das sind die grauen Knoten.
11
graue Knoten: auf der ``Grenze'' der Breitensuche: ein schwarzer Knoten kann nie einem weißen benachbart sein.
12
Queue-Operationen enqueue und dequeue kosten O(1), siehe Kapitel 5.
13
der vorgestellte Algorithmus wendet dies auf alle Knoten der Reihe nach an, das ist aber nicht zentral. Die eigentliche Tiefensuche ist DFS-Visit.
14
Ein weißer Pfad ist ein Pfad, der nur weiße Knoten enthält.
15
Sei G = (V, E) gegeben, dann ist Gt = (V, Et) wobei (v, u) Î Et, gdw. (u,v) Î E. Die starken Zusammenhangskomponenten von G und Gt stimmen überein.
16
jeder von jedem erreichbar. Zum Vergleich mit den starken Zusammenhangskomponenten: der Graph ist hier ungerichtet!
17
Es kann natürlich mehrere leichte/minimale Kanten geben.
18
unter der Voraussetzung, daß a(E,V) = O(log E), z.B., heap-Implementierung.
19
genauer: alle anderen Bäume des Waldes sind nur Einzelknoten.
20
es kann mehrere Bäume mit kürzesten Pfaden geben. In der Regel will man einen davon.
21
Vergleiche Breitensuche und Vorgängergraph. Der Vorgängergraph des Breitensuchalgorithmus entspricht für den Spezialfall, daß alle Kanten das Gewicht 1 haben, den Baum der kürzesten Pfade.
22
extrahieren kostet O(V) (z.B. Arrayimplementierung), wenn man nicht noch Zusatzannahmen macht.
23
konkrete Beispiele aus der Vorlesung: Problem der k"urzesten Pfade. Speziell f"ur D&C: Quicksort, Mergesort.
24
nach Leonardo von Pisa, ``Sohn des Bonacci'' [dPF02].
25
Das Beispiel wird manchmal mi"sinterpretiert als: ``Fibonacci zeigt, wieviel schlechter rekursive L"osungen gegen"uber iterativen sind''. Das ist hier nicht der Punkt. Man erh"alt eine effiziente rekursive L"osung mittels Parameterakkumulation.
26
Punkt 1 und 2 des Vorgehens bei DP
27
zweifache Schleife, eine f"ur min, eine f"ur die Summe.
28
der Algorithmus l"auft tats"achlich mit nur mit O(k n2), denn bei der Berechnung der Summen åj=i+1n si kann man ebenfalls sparen, in dem man Teilsummen wiederverwendet.
29
Die Wahl der Strategie h"angt nat"urlich auch von der Struktur des Problems ab; wenn man keine speziellen Eigenschaften des Suchraums kennt/ausnutzen will, ist Tiefensuche meist die erste Wahl, Breitensuche eher selten.
30
Anwendbar meint: im Prinzip anwendbar, aber das faktorielle Wachstum macht das Problem ``unbehandelbar'' (intractable).
31
die charakteristische Funktion
32
die Abst"ande/Kosten seien als immer ³ 0 angenommen
33
Es gibt Algorithmen, die Gausselimination in O(b n2) machen, wobei b die Bandbreite ist.
34
man kennt nichtmal Approximationen mit garantierter G"ute. Allerdings gibt es ad-hoc Heuristiken
35
von denen sehr viele ``hart'' sind
36
zumindest komplexit"atsm"a"sig
37
alternativ: gibt es eine Rundreise mit Kosten £ k