Algorithmen & Datenstrukturen
Wintersemester 2000/2001

Martin Steffen

1   Einleitung

Literatur: Baut auf Kapitel 1 von [CLR90] auf.

Inhalt Algorithmus ·Analyse von Algorithmen ·Zeitkomplexität und Speicherkomplexität ·Algorithmenentwurf

• Einleitung und Überblick
• Sortieren
• Suchen
• dynamische Datenstrukturen
• Bäume, Graphen ...
• Problemlösungs stragegien:
  • Divide and Conquer
  • Rekursion und Iteration
  • Greedy-Algorithmen
  • Relaxation
  • ...

• Namensgeber: Abu Ja'far Mohammed ibn Mûsâ al-Kwoarizmî: Kitab al jabr w'al-muqabala (Regeln zur Wiederherstellung und Reduktion)
• heutige (informelle) Bedeutung ([Knu73a])
  • (endliche Beschreibung)
  • Definiertheit
  • Terminierung
  • besitzt Input¹ und Output
  • Effektivität/ effectivness, jeder Einzelschritt ist effektiv ausführbar
  • zur Lösung eines wohlspezifizieren Berechnungsproblems

• Eingabe: endliche Sequenz von s = (a₁, a₂, ..., a_n)
• Ausgabe: Permutation (a₁', ... a_n') von s mit a_i' £ a_i+i' für alle i Î {1,... n}
• Algorithmus korrekt/ löst das Problem, falls für alle Eingaben
  • Algorithmus hält nach endlicher Zeit
  • liefert das korrekte Ergebnis

• Sortieren durch Einfügen
• Imperative Lösung:
  • Eingabe: Array A fester Länge n von Zahlen
  • Ausgabe: monoton-steigend sortierter Array, Permutation von A.
  • direktes Einfügen (``in situ'' sortieren)
• inkrementelle Lösung
• Bild: Verhalten von Insertion sort

Insertion_sort(A)

  for j = 2 to length[A]
    do key := A[j];
         i :=  j-1;
       while   i > 0 and A[i] > key
          do
               A[i+1] := A[i]
                    i := i-1;

       A[i+1] := key;

  
   

• Analyse: mathematische Abschätzung des (vorraussichtlichen) Resourcenverbrauches abhängig von der Größe der Eingabe
• Fragestellungen:
  • (Korrektheit, Terminierung)
  • Zeitkomplexität: Anzahl elementarer Schritte
  • Speicherkomplexität:
  • Sonstiges (Kommunikationsbandbreite, ...)
• Idealisierungen:
  • abstraktes Maschinenmodell (Turingmaschine, RAM-Maschine)
  • asymptotisches Verhalten (O-Notation).
    • Abschätzung nach oben: worst-case
    • Abschätzung nach unten: best-case
    • mittlere Komplexität: average-case
• Untersuchung/Vergleich/Klassifizierung der Komplexität von Algorithmen: Komplexitätstheorie (s. [Pap94], auch [AHU89])

• Abhängig vom Input
• sei t_j die Anzahl der while-tests für den Wert von j

Insertion_sort(A)

 for j = 2 to length[A]            // c1    n
   do key := A[j];                 // c2    n-1
        i :=  j-1;                 // c4    n-1    
      while  i > 0 and A[i] > key  // c5    sum(j=2 to n) t_j
         do
              A[i+1] := A[i]       // c6    sum(j=2 to n) (t_j-1)
                   i := i-1;       // c7          -"-
         od
       A[i+1] := key;              // c8    n-1

Insertion_sort(A)

 for j = 2 to length[A]            // c1    n
   do key := A[j];                 // c2    n-1
        i :=  j-1;                 // c4    n-1    
      while  i > 0 and A[i] > key  // c5    sum(j=2 to n) t_j
         do
              A[i+1] := A[i]       // c6    sum(j=2 to n) (t_j-1)
                   i := i-1;       // c7          -"-
         od
       A[i+1] := key;              // c8    n-1

• Zussammenfassen aller Konstanten c_i:

• für große n: nur der höchste Exponent des Polynoms zählt:
  • Bester Fall: lineare Zeitkomplexität ( O(n))
  • schlechtester Fall quadratische Zeitkomplexität ( O(n²))
• Komplexität darstellbar durch ein Polynom über der Problemgröße: polynomielle Komplexität ( O(n^c))

• Inkrementell: vgl. Sortieren durch Einfügen.
  
  
• Divide-and-Conquer: rekursive Zerlegung des Problems:
  1. Divide: Zerlegen des Problem in (gleichartige, aber kleinere) Unterprobleme
  2. Löse die Teilprobleme rekursiv
  3. Conquer: Zusammenfügen zur Gesamtlösung.

• klassisches Beispiel für D&C
  1. Divide: Zerlege die Sequenz in zwei Hälften
  2. Sortiere sie rekursiv
  3. Conquer: Verschmelzen (``merge'') der sortierten Sequenzen
• Aufruf: Merge_Sort(A, 1, length(A))

Merge_Sort(A,p,r)
  
  if p < r
     then   q := floor(p+r/2);   // the ``middle''
        Merge_Sort(A,p,q);
        Merge_Sort(A,q+1,r);
        Merge(A,p,q,r);

• rekursiver Algorithmus Þ Komplexität durch Rekurrenzgleichung
• im schlimmsten Fall

  T(n) =

  ì í î

  O(1) falls n=1 2T(n/2) + O(n) falls n >1

• Vereinfachung: Länge = 2ⁿ
• Ansatz:

  T(n) =

  ì í î

  0 falls n=1 2T(n/2) + n falls n = 2k, k³ 1

• Þ T(n) = n log₂ n

2   Sortieren

Literatur: Kapitel 7 und 8 aus [CLR90]. Knuth [Knu73b] enthält mehr über Sortieren als man wissen will. Heapsort stammt von Williams [Wil64], Quicksort von Tony Hoare [Hoa62]

Inhalt Heaps ·Heapsort ·Quicksort

• (gerichteter) Graph G = (V,E):
  • V: Menge von Knoten (vertices),
  • E: Kanten, binäre Relation auf V (edges)
• ungerichteter Graph: E: Menge ungeordneter Paare {u,v} von Knoten mit u¹v (keine self-loops)
• Wurzelbaum: (rooted tree): verbundener, azyklischer, ungerichteter Graph mit einem ausgezeichnetem Knoten = Wurzel
• Heap: voller, geordneter, binärer Wurzelbaum.
  • Binär: Anzahl der Kinder £ 2.
  • voll: entweder Blatt oder genau zwei geordnete Kinder
  • geordnet: Reihenfolge der Kinder spielt eine Rolle, d.h. hier man kann linkes und rechtes Kind unterscheiden.²
• + Heap-Eigenschaft: Für alle Teilbäume t gilt: t = Node(l, a, r) Þ l = Leaf (und r = Leaf) oder a ³ Key(l) und a ³ Key(r)
• Bild: Heap als Baum

• Implementierung von Heaps als Array: Knoten als Arrayelemente
• Þ weitere Zusatzbedingung: alle Ebenen des Baums gefüllt bis auf evtl. die letzte, diese kann von links nach rechts teilgefüllt sein.³
• Füllung des Arrays von 1 bis heapsize (Bild)
• Repräsentierung des Binärbaumes:

  Parent(i) = ë i 2 û Left(i) = 2 i Right(i) = 2 i + 1

• Ein weiteres Mal das Bild: Heap + Implementierung

• Ausgangspunkt: Unsortierter Array
• zwei Schritte:
  1. "` Teilsortierung"': Bilden eines Heaps
  2. inkrementelle Sortierung des Heaps
• unsortiert ¾® Heap ¾® sortiert

• Heapify: Einfügen, Erhalt der Heapbedingung
• Annahme: der rechte und der linke Teilbaum erfüllen die Heapbedingung!
• rekursive Prozedur: `` Einsickern'' des neuen Elementes

Heapify (A, i)                  
  l := Left(i); r := Right(i);  // Left(i), Right(i) are heaps   

  if l <= heapsize(A) and A[l] > A[i]
     then largest := l  else largest := i;
  if r <= heapsize(A) and  A[r] > A[largest]
     then largest := r;

  if largest != i                 // Verletzung der Heapbedingung?
     then exchange (A[i] , A[largest]);
          Heapify(A, largest);

• repariere alle Verletzungen der Heapbedingung mit Heapify
• Bottom-up mittels Heapify
• Blätter erfüllen Heap-Eigenschaft Þ Start bei den untersten nicht-Blatt Knoten (ë length(A)/2 û).

Build-Heap(A)  
  heapsize[A]  := length[A];
  for i= floor(length(A)/2)) downto 1
      do 
         heapify(A,i);

• Heap als unsortiertes, aber teilsortiertes Reservoir, der Rest des Arrays ist bereits sortiert
• Wurzel des Heaps: Maximum
• Þ Aufbau der sortierten Elemente von hinten
• Entfernen aus dem Heap ist billig (Heapify log₂(n))

Heapsort(A)

   build_heap(A);
   for i = length(A) downto 2
   do  exchange A[1] A[i];
       heapsize[A] := heapsize[A] - 1;
       Heapify(A,1);

• Divide & Conquer
• im Gegensatz zu Mergesort: Verschmelzen trivial, investiere dafür mehr in das Divide
• D&C-Schritte:
  1. Divide: Teile die Sequenz s in zwei Teilsequenzen s₁ und s₂, sodaß s₁£ s₂ (punktweise)
  2. Sortiere Teilsequenzen s₁ und s₂
  3. Conquer: Zusammenfügen trivial

(* $Id: quicksort.ml,v 1.6 1999/11/11 10:43:28 ms Exp $ *)

open Basic;;
open Sort;;

module QuicksortFun (E: ORDERED) : (SORT with type elem = E.t) =
    struct
      type elem = E.t 
     
      let rec filter p l = match l with 
     []     -> []
      | x :: tl ->  
   if   (p x) 
   then  x::(filter p tl)
   else  filter p tl
     
      let rec sort (l : elem list) =   match l with  
        []  -> []
      | x :: tl  -> 
   sort (filter (function y -> E.lt(y,x)) tl)
   @ [x] @                                     (* Pivot *)
   sort (filter (function y -> E.geq(y,x)) tl)
    end

• Zwei rekursive Aufrufe
• das Divide: Partition liefert den Index für die Trennung in die kleinere und größere Hälfte

Quicksort(A,p,r)
if  p < r 
    then   q := Partition(A,p,r)   
           Quicksort(A,p,q);
           Quicksort(A,q+1,r);

• Wähle ein Element des Arrays: das Pivot x
• Partitionieren: trenne/ordne A in 2 Hälften, links alle £ x, rechts alle ³ x.
• Invariante:

• Abbruch: (i ³ j) & I₁, d.h., A[p... i-1] £ x £ A[j+1... r], daraus folgt A[p... j] £ x £ A[j+1... r]

Partition(A,p,r)                      /* p <= r         */
  x := A[p];
  i := p-1;
  j := r+1;
 
  while true                          /* Invariante I_2 */
  do     repeat j := j-1
           until A[j] <= x;
         repeat i := i+1
           until A[i] >= x;
         if   i < j                   /* Invariante I_1 */
         then exchange A[i] <-> A[j]  /* Invariante I_2 */
         else return   j;             /* j <= i         */
  od;
  
         

• Schlechtester Fall: Partitionierung trennt den Ausschnitt [p... r] der Länge n = r-p+1 in einen Teile der Größe 1 und n-1.
• Kosten der Partitionierung: O(n)
• Rekurrenz: T(n) = T(n-1) +O(n) Þ T(n) = å_k=1ⁿ O(k) = O(n²)
• Schlimmster Fall: Falls A bereits sortiert

3   Lineares Sortieren

Literatur: Kapitel 9 [CLR90].

Inhalt O-Notation ·Einführung ·Vergleichssortieren ·Counting sort ·Bucket sort

• Bisher: die Algorithmen O(nlog n) oder O(n²)
• Gemeinsamkeit:

  Die Ordnung die die Algorithem bestimmen, beruht ausschließlich auf dem Vergleich zwischen Elementen

• Þ

  Vergleichssortieren

---

Verfahren	Tmin	Tmax	Tav
Auswahl	O(n2)	O(n2)	O(n2)
Einfügen	O(n)	O(n2)	O(n2)
Bubblesort	O(n)	O(n2)	O(n2)
Mischen	O(n log n)	O(n log n)	O(nlog n)
direktes Mischen	O(n log n)	O(n log n)	O(nlog n)
natürliches Mischen	O(n)	O(n log n)	O(nlog n)
Quicksort	O(nlog n)	O(n2)	O(nlog n)
Heapsort	O(n log n)

Table 1: Vergleich

---

• Vorraussetzung: Sortieren einer Sequenz (a₁,... a_n) (oBdA: alle Elemente verschieden, wichtig ist nur < oder das Gegenteil.)
• mögliche Eingaben der Länge n: alle Permutationen
• Entscheidungsbaum: Darstellung der Entscheidungen eines Sortieralgorithmusses
  • interner Knoten: a_i:a_j wobei 1£ i<j£ n, repräsentiert den Vergleich von a_i mit a_j, seine Unterbäume die Vergleiche, je nachdem wie sein Vergleich ausgefallen ist.
  • Blatt: Permutation
  • Lauf der Sortierung: Pfad durch den Baum
• Þ Höhe des Baumes @ worst-case der Vergleiche @ worst-case der Laufzeit
• Folie: insertion sort

• gegeben: Entscheidungsbaum für einen Algorithmus

• worst-case = Tiefe des Baumes

• Þ Abschätzung für die Laufzeit:

• Mischsortierung und Heapsort sind asymptotisch optimal.

• Es gibt ³ n! Blätter
• Eigenschaft eines binären Baumes: n! £ n^h, d.h., h³ lg(n!)
• mit Stirling-Approximation n! > ( n/e)ⁿ
• Þ h³ n lg n - nlg e
• Þ Untere Schranke O(nlg n).

• Beispiel für einen Algorithmus, der kein Vergleichssortieren ist
• man braucht zusätzliche Information
• Counting Sort: Information, daß der Wertebereich der Elemente endlich ist: 1..., k mit k =O(n).
• Þ Zählen der Elemente =i möglich (im Hilfsarray C[1... k])
• kein Vergleich im Algorithmus

Counting-Sort(A,B,k)
  for i := 1 to k do C[i] := 0;

  for j := 1 to length[A]
  do  C[A[j]] := C[A[j]] + 1  /* C[i]: Anzahl der Elemente = i */

  for i := 2 to k             /* Erlaubter Input von 1...k     */
  do  C[i] := C[i] + C[i-1];  /* C[i]: Anzahl Elemente <= i    */

  for j := length[A]  downto  1
  do
       B[C[A[j]]] :=   A[j];  /* C[A[j]] gibt Pos. in B        */
         C[A[j]]  := C[A[j]] - 1;   
  od;

1. erste Schleife: O(k)
2. zweite Schleife: O(n)
3. dritte Schleife: O(n)

• Insgesamt: O(k+n), und falls k =O(n) Þ lineare Laufzeit: O(n)

• Annahme von Bucketsort: uniforme Verteilung der Eingabe im Intervall I = [0, 1[
• Teilung von I in n Unterintervalle ( Buckets)
  1. Verteilen der Elemente in die Buckets
  2. Sortieren der Buckets
  3. Aneinanderhängen der sortierten Teillisten

BucketSort(A) 
  n := length(A);

  for i=1 to n
    do insert A[i] into list B[floor (n * A[i])];

  for i=0 to n-1
    do sort list B[i] with insertion sort;

  concatenate lists B[0], B[1], B[n-1] together;

• Alles linear bis auf Insertionsort = quadratisch
• Zufallsvariable n_i: Anzahl der Elemente in B[i].
• Insertionsort quadratisch Þ erwarteter Gesamtaufwand:

  n-1 å i=0

  O ( E(ni2)) = O

  æ ç ç è

  n-1 å i=0

  ( E(ni2))

  ö ÷ ÷ ø

• Verteilung von n_i: Binomialverteilung B(k,n,p=1/n)
  P(n_i = k) = n kp^k q^n-k
• E(n_i) = 1 und Var(n_i) = 1- 1/n.
• E(n_i²) = Var(n_i)+ E(n_i)² = 2 - 1/n = O(1)
• Þ
  T(n) = O(n)

4   Analyse

Literatur: Verschiedene Kapitel aus [CLR90]. Daneben Abschnitt 2.5 aus [Heu97].

Inhalt Analyse von Divide and Conquer ·lineare, O(nlog n), polynomielle Komplexität

• Aufstellen einer Rekurrenzgleichung:

  T(n)	=	O(1)   für n£ n0
  T(n)	=	a å i=1 T(ni) + D(n) + C(n)   für n > n0

• T(n): Laufzeit für Problem der Größe n, D und C Kosten für das Divide resp.  Conquer
• Vereinfachung: Teilprobleme gleichgroß, n₀ = 1. ferner f(n) ::= D(n) + C(n).
• Þ

  T(n) = a T(n/b) + f(n)

    a³ 1, b > 1 konstant
• Beispiel: Merge-Sort:
  • Zwei rekursive Aufrufe a=2
  • Halbierung der Problemgröße: b=2
  • Kosten des Mergens: O(n).

• Sei f(n) = D(n) + C(n) linear, f(n) = c n.

• Summe der Größen der Teilprobleme (a n/b) echt kleiner
• Þ a < b

• Summe der Größen der Teilpobleme = Größe des Ausgangsproblems:Þ a = b

• Beispiel: Mergesort

• Summe der Größen der Teilpobleme größer als das Ausgangsproblem Þ a > b

5   Elementare Datenstrukturen

Literatur: Kapitel 11 [CLR90].

Inhalt Stacks und Queues ·verzeigerte Listen ·Bäume ·Implementierungsmöglichkeiten

• "`dynamische Mengen"': veränderbar
• viele verschiedene Varianten
• Unterschieden nach
  • Zugriffsmöglichkeiten (Schnittstelle)
  • Repräsentierung
• zwei Arten von Zugriffen
  • modifizend
  • lesend (queries)
• Beispiele für Zugriffe:
  • Suchen
  • Einfügen, Löschen
  • Minumium, Maximum bestimmen
  • Vorläufer, Nachfolger bestimmen
  • ...
• Beispiele für Repräsentierungen:
  • (einfach o. doppelt) verzeigerte Listen
  • Bäume unterschiedlichster Art (balanciert, Heaps ...)
  • Hashstrukturen

• Stack/Queue: dynamische (Multi-)Mengen mit spezifischer Strategie zum Einfügen und Löschen:
  • Stack: Lifo: last-in, first-out
    • Push: Einfügen
    • Pop: Entfernen
  • Queue: Fifo: first-in, first-out
    • Enqueue: Einfügen
    • Dequeue: Entfernen

• Implementiert als Array 1... n
• dynamischer Inhalt: Elemente S[1], ... S[top]
• Komplexität: O(1)

Stack-empty(S)
  if top == 0 then return true else false;

Push(S,x)
  top    := top + 1;
  S[top] := x;

Pop(S)
  if Stack-empty(S)
  then error "underflow"
  else top  := top  -1;
       return S[top+1];

• Array als Ringpuffer (circular buffer)
• zwei Pointer: head and tail: erste benutzte und erste freie
• Komplexität: O(1)

Enqueue(Q,x) =
  Q[tail] := x;
  if tail == length(Q)
     then tail := 1       // start again with 1
     else tail := tail + 1;


Dequeue(Q) =
  x := Q[head]
  if head == length(Q)
     then head := 1        // start again with 1
     else head := head + 1
  return x;
  

• lineare Datenstuktur
• keine wahlfreier Zugriff wie beim Array, sonder über Zeiger
• Verschiedene Varianten:
  • einfach verzeigert: nur prev
  • doppelt verzeigert: prev und next
  • zirkulär

List-search(L,k)     // k: key  
  x  := head
  while  x != nil and x.key != k
     do  x := next(x);

  return x;

List-insert(L,x)            // vorne Einfuegen
  next(x) := head;
  if head != nil then prev(head) := x
     head := x
  prev(x) := nil

List-delete(L,x)
  if prev(x) != nil
     then next(prev(x)) := next(x)
     else          head := next(x)
  if next(x) != nil
     then prv(next(x)) := prev(x); 

6   Hashstrukturen

Literatur: Kapitel 12 aus [CLR90]. Hashfunktionen werden auch in [Knu73b] diskutiert.

Inhalt Hashstrukturen ·Hashing mit externer Verkettung ·Hashing mit offener Adressierung ·Hashfunktionen

• drei Operationen eines Wörterbuches (dictionaries)
  • Suchen
  • Einfügen
  • Entfernen
• Hashtabellen: effizient zur Implementierung von Dictionaries

• implementiert mit Arrays, Zugriff direkt über Index = Schlüssel (key, eindeutig)
• Suchen, Einfügen, Entfernen: in konstanter Zeit (O(1)).

Search(T,k)   = return T[k];

Insert(T,x)   = T[key(x)] := x;

Delete(T,x)   = T[key(x)] := nil;

• Problem:
  • machbar nur für kleine Bereiche der Schlüssel, Platzverschwendung
  • nur destruktives Einfügen möglich
• Þ Hashtabellen

• Verallgemeinerung von Arrays mit direkten Zugriff
• gegeben: Bereich U der Schlüssel (``Universum'')
  
  
• hash-Funktion: h : U ® {0,... , m - 1}
  • |U|> m
  • Þ h nicht injektiv Þ Kollision
  • h(k): Hashwert von k
  • ``zufällige'' Funktion

• Verkettung (chaining, auch external chaining)
• Bild
• Varianten: Eindeutiger Schlüssel, implementierbar durch
  • Überschreibendes Einfügen, oder
  • Löschen nur mittels key (Delete(k)) und Löschen von allen Elementen mit passendem key, search gibt nur den ersten Treffer zurück.

Insert(T,x) = T[h(key(x))] := insert x at the head of T[h(key)];

Search(T,k) = Search for an element with key k in T[h(k)];

Delete(T,x) = Delete x  from list  T[h(k)];

• Worst-case: alle Elemente mit dem selben Schlüssel Þ O(n)
• im Mittel:
  • Annahme: Gleichverteilung = einfaches, uniformes Hashing
  • Hashfunktion h(k) mit konstantem Aufwand O(1)
  • Þ Suchen nach Element mit Schlüssel k: linear in der Länge von T[h(k)]

• eine Liste wird bis zum Ende durchsucht
• durchschnittliche Länge der Listen: a = n/m
• ÞO(1+ a)

• alle Schlüssel gleichwahrscheinlich, kein Schlüssel doppelt, Anfügen ans Ende

• Ziel: Gleichverteilung der Ergebnisse j von h(k) (aus dem Bereich 0 bis m-1):

  å {k| h(k) = j}

  P(k) =

  1 m

• falls keys gleichverteilt aus [0,1[ Þ h(k) = ë k m û Î {0, ..., m-1}
• ansonsten: Heuristiken

• Divisionsmethode	h(k) = k mod m
  Multiplikationsmethode	h(k) = ë m(k A - ë k A û) û (mit 0<A<1)
  Universal hashing	``zufällige'' Auswahl von h

• wichtig: Auswahl der Parameter, abhängig auch von den keys
  • Divisionsmethode: m prim, möglichst nicht nahe 2er-Potenz
  • Multiplikation: m egal

• alle Elemente in der Hashtabelle gespeichert (keine Pointer, keine externen Listen) Þ Verkettung wird errechnet
• Belegungsfaktor £ 1
• Sondierung (probe): Suche nach freiem Slot
• Þ Hashfunktion
  h: U * {0,... m-1} ® {0,...,m-1}
• Sondierungs-Sequenz (probe sequence) für Schlüssel k:
  (h(k,0), h(k,1), ..., h(k, m-1))
• gute Hashfunktion: Vermeidung von Häufungen (clusters)

• lineares Probing
  • gegeben: h': U ®{0,... m-1}: gewöhnliche Hashfunktion
    h(k, i) = ((h'(k) + i) mod m)
  • Probe-Sequenz: T[h'(k), h'(k)+1, ...]
  • Problem: primäre Häufung
• Quadratisches Probing
  • h' wie oben
    h(k, i) = ((h'(k) + c₁ i + c₂ i²) mod m)
• Doppeltes Hashing
  • gute Methode
  • h₁, h₂: zwei gewöhnliche Hashfunktionen
    h(k, i) = (h₁(k) + i h₂(k)) mod m
  • h₂(k) sollte relativ prim zu m sein!

7   Binäre Bäume

Literatur: Kapitel 13 aus [CLR90]. Balancierte Bäume stammen aus [AVL62].

Inhalt Binäre Bäume ·Baumoperationen

• Unterstützung vieler Wörterbuchoperationen
• Baumstrukturen effizient
• Effizienz der Operationen proportional Höhe des Baumes = O(log n) (falls der Baum ``ausgeglichen'')
• Viele Varianten, abhängig von der Anwendung
  • Rot/Schwarz-Bäume [Bay72]
  • B-Bäume
  • AVL-Bäume [AVL62]
  • Splay-Trees
  • (a,b)-Bäume, z.B. (2,3)-Bäume (2-3-Bäume)
  • selbst-balancierende Bäume
  • ...

• Die Elemente des Baumes sind `` sortiert''
• Þ Ausgeben der sortierten Elemente = rekursives Durchlaufen des Baumes (in-order tree walk)⁴

InOrder-Tree-Walk(t) =
  if   t != nil
  then InOrder-Tree-Walk(left(t));
       print (key(t));
       InOrder-Tree-Walk(right(t));

• wichtige Operation auf Suchbäumen
• Komplexität: O(h), wobei h die Höhe
• Minimum/Maximum bestimmen: genauso einfach (der linkeste/rechteste Knoten im Baum)

Search(t,k) =                // t : tree, k : key
  if         t == nil    then raise error("Not found")
  else if    k == key(t) then return t
  else if    k <  key(t) 
       then Search( left(t),k)
       else Search(right(t),k)

Search(t,k) =                // t : tree, k : key
  while (t != nil) and (k != key(t))
  do
    if k < key(t)
       then t :=  left(t)
       else t := right(t)
  od;
  if   (t == nil) 
  then raise error("Not Found")
  else return t

• Einfügen immer an den Blättern
• Komplexität: O(h)

Insert(T,z) =              // T : tree, z : node to insert
  y := nil; x := root(T);  // zwei Hilfsvariablen
  while  x != nil          // finde das passende Blatt
  do
    y := x;                // y zum merken des Vaters
    if   key(z) < key(x)
    then x := left(x) 
    else x := right(x)
  od;                     
  p(z) := y;               // => x ist nil, y sein Vorgaenger
  if   y = nil             // Sonderfall: y = Wurzel;
  then root(T) := z
  else if   key(z) < key(y)// f"uge an der passenden Stelle
       then  left(y) := z  // z als neues Blatt ein.
       else right(y) := z 

• Problem (s. Bild):
  • Erhalt der Baumeigenschaft: innere Knoten müssen ersetzt werden
  • Erhalt der Sortierungseigenschaft: der Ersatz muß passen
• Baumnachfolger eines Knotens x: Nachfolger in der in-order-Baumordnung
  • falls Knoten mit rechtem Kind:
  • Þ Nachfolger = der ``linkeste'' Knoten im rechten Teilbaum.
  • Þ Nachfolger hat kein linkes Kind!
  • Þ key(left(x)) £ key(x) £ keysucc(x) £ key(right(x))⁵
• Þ
  Nachfolger ersetzt zu löschenden inneren Knoten
• Komplexität: O(h)

Delete(T,z)           // T = tree, z = zu loeschender Knoten
  if   left(z) = nil or right(z) = nil
    then y := z              // y tritt an die Stelle von x
    else y := Successor(z);  // wobei: y hat <= 1 Kind!

  if left(y) != nil          // Bestimmung des Kindes x
     then x :=  left(y)      // von y.
     else x := right(y);
                                 // Ver"andern der Verzeigerung
  if x != nil then p(x) = p(y);  // y herausgenommen => x mit 
                                 // neuem Vater
  if p(y) = nil                  // Spezialfall: wurzel
    then root(t) = x
    else if  y = left(p(y))
           then  left(p(y)) := x
           else right(p(y)) := x  // y ist nun  vom
                                  //  urspr. Platz entfernt

  if y != z then key(z) := key(y);// z durch y ersetzen

  return y;

8   Rot-schwarz-Bäume

Literatur: Kapitel 13 aus [CLR90]. Die Rot/Schwarz-Bäume wurden von [Bay72] eingeführt.

Inhalt Rot/schwarz-Bäume ·Rotation ·Erhalt der Rot-Schwarzeigenschaft bei Einfügen und Löschen

• Hauptproblem der Suchbäume: Effizienz hängt von der Höhe ab
• Þ je balanzierter desto "`besser"' der Baum
• für die Suche: ja; andererseits
  • dauerndes Rebalanzieren kostet auch Zeit ÞBalanciertheitsanforderungen am besten nicht zu strikt (vor allem bei vielen Lösch- und Einfügeoperationen
  • Wie stellt man fest ob ein Baum balanciert ist? (Laufzeit!)
  • speichert man Zusatzinformationen darüber ab? (Speicherplatz!)

• zwei Arten von Knoten: Schwarze werden strikt balanciert, rote dienen als Schlupf.
• Anteil des Schlupfes muß beschränkt sein

• Bild
• Schwarzhöhe bh(x) eines Knotens: die Anzahl der schwarzen Knoten auf den Pfaden (ausschließlich x) zu den Blättern

• Þ die Operationen Suchen, Minimum, Maximum, Successor, Predecessor: O(lg n).
• Einfügen und Löschen?

• Rotation
• Erhalt der In-Ordnung der Schlüssel
• Komplexität O(1)
• Bild

Rotate-l(t,x) =                   // t = Baum, x = Knoten
  if    (x = nil) or (right(x) = nil)
  then  raise error "illegal rotation"
  else  y := right(x);          // rette y
       p(y) := p(x);              // ver"andere y's Verwandschaft
       if   y != nil              
       then right(x) := left(y);  // beta
       if   (left(y)) != nil
       then p(left(y)) := x;
 
       left(y):= x                // x != nil
       if   root(t) = x           // Spezialfall
       then root(t) := y
       else if   x = left(p(x))  // p(x) definiert
            then  left(p(x)) := y
            else right(p(x)) := y

       left(y) := x              // zum Schluss: x als Kind von y
       p(x)  := y;               

• Zunächst Einfügen wie im gewöhnlichen binären Suchbaum
• Þ neues rotes Blatt.
  • keine Schwarz-Verletzung, aber u. U.
  • Rot-Verletzung
• Bei rot-Verletzung:
  • Reparieren durch Umfärben und Rotation
  • keine Neueinführung von Schwarzverletzungen

insert(T,x) 
  tree_insert(T,x);                          // normal einfuegen 
  color(x)  := red                           // am Anfang rot
 
  while x != root(t) and color(p(x)) = red   // Rot-verletzung
  do
    if  p(x) = left(p(p(x));                 // Vater ist linker Sohn
       then  y := right(p(p(x))              // y = Onkel, d.h.
                                             // rechter Sohn des Opas
             if  color(y) = red              // Onkel rot
                then  color(p(x))  := black; // => umfaerben
                      color(y)     := black;
                     color(p(p(x)) := red;
                                 x := p(p(x))
                else if x = right(p(x))      // Onkel schwarz
                        then x := p(x);      // x ist rechtes Kind
                             left_rotate(T,x) 

                     color(p(x)) := black;   // Vater <- schwarz
                     color(p(p(x)) := red;   // Opa   <- rot
                    right_rotate(T,p(p(x))); // Ausgleich
        else ....... // analog
  done;
  color(root(T)) := black;

9   Graphen

Literatur: Kapitel 23 aus [CLR90]. Breitensuche stammt von Moore [Moo59]. Der Erfinder der Tiefensuche scheint unbekannt. Der angegebene Algorithmus für die starken Zusammenhangskomponenten ist von Tarjan [Tar72].

Inhalt Graphen ·Repräsentierungen ·Erreichbarkeit ·Breitensuche ·Tiefensuche ·backtracking ·topologisches Sortieren ·Berechnung starker Zusammenhangskomponenten

• Wichtige Klasse von Algorithmen, viele Anwendungen
• Problem: Durchlaufen eines gegebenen Graphen, mit Besuch der Knoten + Berechnung von Strukturinformation über den Graphen
• Unterscheidung nach
  • Durchlaufordnung und (davon abhängig)
  • Art der Zusatzinformation über den Graphen und seine Struktur: z. B.
    • gegenseitige Erreichbarkeit von Knoten
    • Zyklen
    • Bäume als Teilstrukturen im Graphen
    • (stark) zusammenhängende Teilgraphen
• Zwei Klassiker:
  1. Tiefensuche
  2. Breitensuche

• Zwei Standardmöglichkeiten:
  1. Adjazenzlisten
  2. Adjazenzmatrix
• Speicherbedarf:
  • Adjazenzliste: O(V+E)
  • Adjazenzmatrix: O(V²)

• klassischer Graphsuchalgorithmus, Reihe von Verallgemeinerungen
• ursprüngliches Problem [Moo59]: kürzeste Wege in Labyrinthen
• Problem:
  • gegeben: G = (V,E) + einen ausgezeichneten Knoten (Quelle) sÎ V.
  • gesucht: Alle von s aus erreichbaren Knoten
  • Zusatzinfo:
    • Abstand d(s,u) jeden Knotens u zu s⁷
    • Breitensuchbaum: Baum mit kürzesten Pfaden von s zu jedem Knoten.

• Grundgedanke der Breitensuche:

  Suche ``in die Breite'': Bevor Knoten mit Abstand k+1 von der Quelle entdeckt (bzw. abgehandelt) werden, sind alle Knoten mit Abstand k" entdeckt (bzw. abgehandelt)

• Sicherstellung der Breitendurchlaufordnung:

  Behandlung der entdeckten Knoten in Fifo-Manier (Queue)

• Zur Erkennen von bereits gesehenen Knoten: 3 Farben:⁸
  1. weiß: unentdeckt
  2. grau: entdeckt, aber noch nicht fertigbehandelt
  3. schwarz: fertig (und damit auch entdeckt)
• Reihenfolge: weiß Þ grau Þ schwarz⁹
• Zusatzinfo:
  • Distanz: Distanz des Knotens, von dem man entdeckt wird + 1
  • Breitensuchbaum: Merken des Knotens, von dem man entdeckt wird.

bfs (G,s) =      // Graph und Quellknoten 
  for each vertex u in V[G] - {s}
  do color[u] := white
     d[u]     := $\infty$;
     p[u]     := nil
  done;
  color[s]    := gray;
  d[s]        := 0;
  p[s]        := nil;
  Q.enqueue(s);                 // beginne mit der Quelle

  while not Q.isempty()
  do
     u := Q.head();             // noch kein dequeue!
     for each v in Adj[u]       // alle Nachbarn.
     do
        if   color[v] = white
        then color[v] := gray;
             d[v]     := d[u] + 1;
             p[v]     := u
             Q.enqueue(v)      // speichere den Nachbarn
        fi;
     done;
     Q.dequeue()            // u ist abgearbeitet
     color(u) := black;     // und als fertig markiert
  done

• Zeitkomplexität:
  • jeder Knoten wird höchstens einmal in Q eingereiht, und damit auch höchstens einmal aus ausgereiht: O(V)¹⁰
  • für jeden Knoten wird die Adjazenzliste durchlaufen, insgesamt höchstens O(E)
• Þ O(E+V)

• Suche zunächst in die Tiefe¹¹
• Wie bei Breitensuche: Farben zur Suchsteuerung
  1. Weiß: ungesehen
  2. Grau: entdeckt
  3. Schwarz: fertig
• anstelle von Queue: Stack
• ``Backtracking''
• Teilgraph der Vorgänger G_p= (V, E_p):

  E

  p

  ={(p(v),v) | vÎ V, p(v) ¹ ^}

• Þ Menge von Tiefensuchbäumen (= Tiefensuchwald, depth-first forest)
• Zusatzinformation: Zeitstempel d[v] (discovered) und f[v] (finished) wobei d[v] < f[v].

DFS(G)                           // Gerichteter Graph
  for all vertices $v \in V[G]$  // Initialisierung
  do 
     color[u] := white;          
      pred[u] := nil; 
  od
  time := 0;                     // Ende der Initialisierung
  for all vertices  $u \in V[G]$
  do
      if color[u] = white then DFS-Visit(u); // eigentl. Tiefensuche
  done;
 

DFS-visit(u)                       // Eigentliche Tiefensuche
  color[u] := gray;                // Knoten entdeckt
  time := time + 1;  d[u] := time; // merke Entdeckungszeit
  for each v in Adj[u]             // erkunde Kante (u,v)
  do  if   color[v] = white
      then pred[v] := u            // pred = Entdeckerknoten
           DFS-visit(v)            // rek. Abstieg
  done;
  color[u] := black;               // u ist fertig, merke
  time := time + 1; f[u] := time;  // die Fertigstellzeit

• Bild 23.5(1)
• Komplexität:
  • O(V) für DSF
  • O(E) für DFS-Visit
  • Þ Laufzeit für Tiefensuche: O(E+V)

1. [d[u],f[u]] ist echtes Teilintervall von [d[v], f[v]], u ist Nachfahre von v in Tiefensuchbaum
2. Symmetrisch.
3. [d[u],f[u]] und [d[v], f[v]] disjunkt

• Þ Verschachtelung der Intervalle:

• Klassifikation von Kanten:
  • Baumkante: Kanten des Tiefensuchwaldes
  • Rückwärtskante: Kanten von Nachfahren zu Vorfahren in einem Tiefensuchbaum (inkl. Selbst-Schleifen)
  • Vorwärtskante: Kante von Vorfahren zu Nachfahren gemäß einen Tiefensuchbaumes, die nicht im Baum sind
  • Querkante: alle anderen

• Anwendung der Tiefensuche
• algorithmische Umsetzung der bekannten Tatsache: jede Halbordnung läßt sich zu einer totalen/linearen Ordnung erweitern.
• Graphdarstellung einer Halbordnung: DAG = "`Gerüst"' der Ordnung

• Eine topologische Sortierung eines DAGs G ist eine lineare Ordnung der Knoten von G, Kompatibilität: falls (u,v) eine Kante auf G, dann u < v in der linearen Ordnung.
• d.h., kein Sortieren wie bei den Sortieralgorithmen
• Bild
• Lineare Ordnung = Zeitstempel der Schwarzfärbung = f-Zeit.

• Eingabe: DAG ("`="' Halbordnung), Ausgabe: verzeigerte Liste ("`="' lineare Ordnung)

Topological-Sort(G)               // G ist ein DAG

  call DFS(G) to compute  finishing-times f[v] for all v;
  as each vertex is finished, insert it onto the front of a list;
  return the linked list

• Komplexität: Laufzeit O(V+E).

• klassische Anwendung der DFS: Zerlegen eines Graphen in stark-zusammenhängende Komponenten

• Idee: G und G^t haben die selben starken Zusammenhangskomponenten Þ zweimaliges Anwenden von DFS, auf G und auf den transponierten Graphen¹³ G^t
• Komplexität: lineare Zeitkomplexität O(E+V)

Strongly-connected-components(G)    // G: gerichteter Graph

  call DFS(G) to obtain finishing times f[u] for the vertices;

  compute $G^t$ = transpose(G)        // transponiere G

  call DFS($G^t$), but in the main loop of DFS, 
       consider the vertices in order of 
       decreasing f[u]

  output the vertices of each tree in the depth-first 
      forest from the previous step as a separated strongly 
      connected component.

• Vorvater f(u) eines Knoten u ist derjenige Knoten w mit u®^* w und maximalen f[w].

• es gilt also: für jede SCC ist der Vorvater
  • der erste Knoten der entdeckt wird und
  • der letzte Knoten der beendet wird!
• Þ

  die starke Zusammenhangskomponente von r sind diejenigen Knoten die von r in Gt erreichbar sind.

10   Spannbäume

Literatur: Kapitel 24 aus [CLR90].

Inhalt Kantengewichte ·minimale Spannbäume·greedy-Strategien ·Kruskals Algorithmus ·Prims Algorithmus

• Motivation: Verknüpfung¹⁴ einer geg. Anzahl von Knoten mit minimalen Kosten (Verkabelung, Routing, ...)
• Verknüpfung von n Knoten: mit n-1 Kanten
• Kosten: modelliert als "` Kantengewicht"'
• Gegeben:
  • G = (V, E) ungerichtet, verbunden, und mit E Í V × V Menge potentieller Verbindungen
  • Kantengewicht: w: V² ® R.
• Gesucht: TÍ E sodaß
  • azyklisch (Baum)
  • Verbindung aller Knoten (aufspannend, spanning)
  • minimale Kosten

    w(T) =

    å (u,v) Î T

    w(u,v)

    minimal.
• Þ Problem des minimalen Spannbaums
• Beispiel für greedy-Strategie
• Bild

• greedy-Strategie:
  • Heuristik für Optimierungsprobleme
  • falls eine Entscheidung zu treffen ist: entscheide dich für die augenblicklich beste Alternative (ohne auf mögliche Nachfolge-Vorteile zu achten)
• iterativer Aufbau eines minimalen Spannbaumes
• Þ schrittweises Hinzufügen von Kanten.

Generic-MST(G,w) =
  A := 0;
  while A does not form a spanning tree
  do 
    find an edge (u,v) that is safe wrt. A
    A := A $\cup$ {(u,v)}
  done;
  return A

• Problem: wie findet man sichere Kanten?

• während der Algo läuft: A immer azyklisch (Invariante)
• Þ G_A = (V, A) Wald
• zu Beginn: Wald mit |V| (einknotigen) Bäumen
• jede hinzugefügte sichere Kante verknüpft zwei Bäume
• Þ Schleife |V| -1-mal durchlaufen

• G = (V,E) zusammenhängend, ungerichtet, Gewichtungsfunktion W: E ® R.
• A Í E, A Teil eines min. Spannbaumes
• C eine Zusammenhangskomponente (hier Baum) im Wald G_A = (V, A).

• Spezialisierung des generischen Algorithmus'
• greedy-Strategie
• direkt Umsetzung des Korollars 10
• Þ sichere Kante = die mit dem geringsten Gewicht, die zwei Bäume verbindet.
• Þ nimm immer die Kante mit geringstem Gewicht: wenn sie zwei Komponenten verbindet: hinzufügen, wenn nicht, ignorien
• Hilfsfunktionen + Hilfsdatenstrukturen:
  • Wald = disjunkte Mengen/Partition (von Knoten)
  • find-set: finde Repräsentanten
  • Union: Vereinigung
  • Makeset: ein-elementige Menge

mst-kruskal(G,w) 
  A := 0;                   // A: Kantenmenge
                            // Invariante: A Teil eines min. S-B
  for all $v \in  V[G]$
  do Make-Set(v) done;      // Wald aus lauter Knoten

  sort the edges of $E$ by non-decreasing weight $w$;
 
   for all edges $(u,v) \in E$ (in order)
   do
     if   Find-Set(u) $\not=$ Find-Set(v) // nicht im selben Baum?
     then 
       A := A $\cup$ {(u,v)};// fuege Kante hinzu
       Union(u,v);           // vergroebere Partition
     fi;
   done;
   return A;

• Laufzeit von Kruskal:
• hängt von der Implementierung der Hilfsstukturen ab

  Initialisierung	O(V)
  Sortieren	O(Elog(E))
  innere Schleife	O(E)
  Datenrepräsentierung	a(E,V).

• Þ O(Elog(E))¹⁶

• Spezialisierung des generischen Algorithmus'
• A: kein Wald, sondern ein einzelner Baum¹⁷
• Wachsen des Baumes startend von beliebiger Wurzel r
• Baum bestimmt den Schnitt
• Þ Iterationsschitt: füge leichte Kante vom Baum nach außerhalb des Baumes hinzu
• greedy: mit jedem Schritt wird der Baum minimal schwerer
• Datenstruktur
  • Ordnen der Knoten außerhalb des Baumes
  • Þ Priority Queue (z.B. wieder mittels Heap)

mst-prim(G,w,r)            // G = Graph, w = Gewichtung,  r: Wurzel
  Q := V(G);               // priority queue von Knoten
                           // Q : Knoten noch nicht im Baum

  for all $u \in  Q$ do key[u] := $\infty$ done;
  key[r] := 0;                 
  p(r)   := nil;           // r ohne parent
  while  Q $\not= \emptyset$
  do
    u := extract_min(Q);   // u dem Baum hinzugefuegt
    for all $v \in Adj(u)$ // bewerte alle Nachbarn
    do
       if   $v \in$ Q and $w(u,v) < key(v)$
       then p(v)   := u;   // parent
            key(v) := w(u,v)   
       fi
    done
  done

11   K"urzeste Pfade

Literatur: Teile von Kapitel 25/26 aus [CLR90]. [Ski97]

Inhalt Einleitung ·Varianten ·Relaxation ·Dijkstras Algorithmus ·Bellman-Ford ·lineare Programmierung

• Motivation: Routing, Streckenplanung
• klass. Beispiel f"ur ein (gutartiges) Optimierungsproblem
• gegeben: gerichteter Graph mit Gewichtungsfunktion w: E ® R
• Problem: finde einen Verbindung/Pfad mit minimalen Kosten

• spezifizierte Quelle (single-source): finde einen k"urzesten Pfad von einem gegeben Knoten f"ur jeden Zielknoten
• spezifiziertes Ziel: (single-destination): duales Problem
• spezifizierte Quelle und Ziel (single-pair)
• k"urzeste Pfade f"ur alle Knotenpaare.

• Hier: single-source
• Eingabe: Gerichteter Graph G = (V,E) + Quelle s Î V.
• Ausgabe: nicht nur minimales Gewicht, sondern auch Pfad
• Þ Baum k"urzester Pfade bei gegebenem Startknoten s:¹⁸ G' = (V', E') mit:
  • V' Í V: Menge der von s aus erreichbaren Knoten
  • G': bewurzelter Baum mit Wurzel s
  • der (eindeutige, einfache) Pfad von s nach v in V' ist ein k"urzester Pfad von s nach v in G.
• Repr"asentierung: Im Lauf des Graphtraversierung: merke den Vorg"anger p f"ur jeden Knoten Þ G_p = (V_p, E_p).¹⁹
• Problem: Kanten mit negativen Kosten, insbesondere Zyklen mit negativen Kosten.

• Þ gutartiges Problem, viele Techniken anwendbar
  • greedy
  • Relaxation
  • dynamische Programmierung....

• Þ Zerlegung: Sei s v k"urzester Pfad mit s u v, dann d(s,v) = d(s,u) + w(u,v).
• "`Dreiecksungleichung"'
  • d(s,v) £ d(s,u) + w(u,v) (mit (u,v) Î E)
  • d(s,v) £ d(s,u) + d(u,v)

• Methode zur Optimierung bei gutartigen Probleme
• pessimistische (worst-case) Absch"atzungen
• im Laufe des Algos immer weiter verbessert
• gutartig: ``monoton'', neue Information verbessern die Sch"atzung nur
• f"ur k"urzeste Pfade: f"ur alle v Î V: d(v) als obere Schranke f"ur den Pfad von s nach v.

• generischer Relaxationsalgorithmus
  • Initialisierung: f"ur all v Î V:
    • d(v) = ¥ (au"ser s)
    • d(s) = 0
    • p(V) = ^
  • Relaxierung einer Kante: Anwendung der Dreiecksungleichung: [mathescape=true,tabsize=2] Relax(v1, v2) = if d(v2) > d(v1) + w(v1,v2) then p(v2) := v1; d(v2) := d(v1) + w(v1,v2) fi <\code>
• Unterschiedliche Algorithmen, je nachdem wann und wieoft Kanten relaxiert werden.

Dijkstra(G,w,s)
  Intitialise(G,s);       // siehe generischer Algo.
  S := $\emptyset$;                 // Knoten mit bekannter Distanz 
  Q := V;                 // priority queue               

  while $Q \not= \emptyset$
  do
    u := extract-min(Q); 
    S := $S \cup \{u\}$;
    for all vertices $v  \in Adj(u)$
    do
        relax(u,v)
    done
  done
  

Bellmann-Ford(G,w,s)              // G = (V,E), Gewichtung w

  initialize(G,s);                // s. generischer Algo.
  for i := 1 to size(V)-1
  do
    for all edges $(u,v) \in  E$
    do 
      relax(u,v) 
    done
  done;
  for all edges $(u,v) \in E$     // Test auf negative Zyklen
  do
    if d(v) > d(u) + w(u,v) 
       then return false
       else return true
  done;