Informatik

Studium
Kontakte
- hdh@minet.uni-jena.de
- grajetzki@minet.uni-jena.de
Lernplan
Literatur
- Cormen: Algorithmen - eine Einführun
  - ISBN 3-486-27515-1
- Ottmann online lecturnities
Inhalte nach Algorithmen
- Sortieren
  - insertion sort
  - Quicksort
  - Merge-Sort
  - Heap-Sort
  - Counting-Sort
  - Radix-Sort
- Select
- Gleitgeraden-Verfahren
  - Maximale Teilsumme
  - Segmentschnittproblem
- Post-Office-Problem
- Algorithmus von Dijkstra

Inhalte nach Lernplan

Einführung
- Problem
  - führt zu Lösungsansatz für Algorithmus
    - oft mehrere
    - führt zu Rechner- und Datenstruktur
    - Komplexität von Interesse
      - Speicherkomplexität
      - Zeit
        i.A. Messung der Rechenzeit T über Funktion der Inputlänge n
        T(n)
  - Algorithmus
    - Definiertes Verhalten, das aus Eingabewerten Ausgabewerte produziert
      - Input → Algorithmus → Output
      - Aufgabe ist also aus einem gegebenen Input den benötigten Output zu erzeugen
    - Rechenschritte T_a(n)
      a: spezieller Algorithmus
      n: Inputlänge
    - man geht aus von Registemaschine → worst case-Analyse
      Registermaschine
      RandomAccess Machine
      Zugriffszeiten gleich lang
      Rechenschritt =einmalige Ausführung einer Addition, Multiplikation, Division, Subtraktion, Größenvergleich usw. zweier Registerzellen
      immer konstanze Zeit benötigt
      m*O(1) Zeit benötigt
      Rechenschritte T_a(n) = max T_a(w)
      |w| = n
      maximal benötigte Schrittzahl bei Eingabe der Länge n
      z.B. T_a(n) =
      O(n log n), O(n²)
      obere Schranke, braucht höchstens g(n) Schritte
      Ω (n log n)
      untere Schranke
      alle denkbaren Verfahren brauchen mindestens g(n) Schritte im worst case
    - average-case-Analyse
      meist zu kompliziert, kaum berechenbar
      meist sind Algorithmen mit guten worst-case Werten auch im average case gut
    - Beispiel: Maximale Teilsumme
      INPUT: Folge ganzer Zahlen
      gewünschter OUTPUT: maximale Teilsumme
      Bsp: (2,-4,3,-1,4,-1,5,-9,2,-6,5,-3,5) → 10
      verschiedene Ansätze
      naiver Ansatz
      drei Schleifen
      Laufzeit asymptodisch wie n³
      Divide & Conquer-Ansatz
      T(n) = O(n log n)
      Ziel: T(n) = O(n)
      Gleitgeraden-Ansatz
      Input a₁,...,a_n
      Algorithmus
      T(n) = O(n)
      Linearzeitalgorithmus
    - Kriterien für Optimalität
      Laufzeit
      Speicher
      Programmieraufwand
      meist nicht alles gleichzeitig optimierbar
    - Beispiel: Segment-Schnitt-Problem
      INPUT
      Menge von horizontalen Strecken
      Menge von vertikalen Strecken
      z.B. Mikrochip auf dem Segmente aufgebracht werden sollen
      ohne Überschneidungen
      Anzahl der Strecken: |H| + |V| = n
      OUTPUT
      Schnittpunkte
      Annahme: Test auf Schnittpunkt einer senkrechten mit einer waagerechten Strecke geschehe in O(1)
      naiver Ansatz
      Testen jeder Strecke auf Schnittpunkte mit allen anderen
      ~n² Schnittpunkte (die alle ausgegeben werden müssen)
      besser als O(n²) geht es nicht!
      O(n²)
      ist optimal, da Ausgabe є Ω(n²)
      besserer Ansatz
      Zeit für Ausgabe wird extra berechnet
      "output-sensitive"
      Ziel: Algorithmus mit O(n log n + k)
      k = Mächtigkeit des Outputs
      Algorithmus "plane sweep"
      X[i] = X-Koordinaten der v aus V sowie linke und rechte Endpunkte der h aus H
      Ereignispunkte
      sortieren der Ereignispunkte: O(n log n)
      Y: kritische Menge zur dynamischen Verwaltung
      muss effizient erfolgen
      E: Liste der Ereignispunkte
      z.B. lineare Liste
      H: Menge der horizontalen Linien
      V: Menge der vertikalen Linien
      ist ein Gleitgeradenverfahren
      nur noch das, was auf der Gleitgerade passiert wird betrachtet
      drücken die Dimension des Problems um 1 nach unten
      notwendige Datenstruktur muss unterstützen
      INSERT
      SEARCH
      DELETE
      → lineare Liste nicht geeignet
      → Wordbook
      ADT
      abstrakter Datentyp
      hier: Menge von Operationen
      Eine Implementierung unterstützt die Operationen eines ADT, wenn die Laufzeit pro Operation O(log n) nicht überschreitet
      maximal =(log n)
      höhenbalancierter Suchbaum
  - Datenstrukturen
    bei bestimmten Algorithmen wichtig für Rechenzeit
    Beispiel: Post Office Problem
    in einigen Orten Postämter
    in manchen Orten keine
    Problem: zu welchem Postamt gehört Ort x
    Ansätze
    Brute force
    bei n Postämtern: Berechnung von Distanz von x zu jedem der n Postämter
    Preprozessing
    Mittelsenkrechten einzeichnen
    Voronoi-Diagramm
    Point-Location-Verfahren
    liefert zu jedem roten Punkt das zugehörige Voronoi-Gebiet
    in O(log n) möglich
    Überlegung: werden häufig solche Anfragen gestellt, so lohnt sich der Aufwand der Preprozessings
    Datenspeicherung hat Einfluss auf Schrittanzahl
    abstrakte Datentypen, siehe "plane sweep"
  - Problem-Typen
    prinzipiell nicht berechenbar (algorithmisch nicht lößbar)
    prinzipiell durch Algorithmus berechenbar
    praktisch berechenbar
    praktisch nicht berechenbar
    jenseits der Cookschen Linie
    zu große Laufzeit
    np-vollständig
    es ist nicht bewiesen, ob es für np-vollständige Probleme effiziente Algorithmen gibt
    wäre ein np-vollständiges Problem effizient lößbar, so wären alle effizient lößbar
    es gibt np-vollständige Probleme, die Problem ähnlich sind, für die effiziente Algorithmen existieren
- Big-O-Notation
  Wichtig: Übergang von konkreten Ausdrücken für T(n) zur Big-O-Notation
  Big-O
  O(g(n)) = Klasse von Funktionen, die asymptodisch maximal so schnell wie g(n) wachsen
  Beispiel: T(n) = 2n² - 7n
  T(n) є O (n²)
  schlimm aber üblich: T(n) = O(n²)
  O(g(n)) = { f(n) | Es gibt c > 0, n₀ є N : Für alle n≥n₀ : O ≤ f(n) ≤ c*g(n) }
  Es gibt noch eine andere Definition dieser Funktion!
  Big-Ω
  Ω(g(n)) = Klasse von Funktionen,
  die asymptodisch mindestens so schnell wie g(n) wachsen
  Ω(g(n)) = { f(n) | Es gibt c > 0, n₀ є N: Für alle n ≥ n₀ : f(n) ≥ c*g(n) ≥ 0}
  g(n) ist eine untere Schranke für das asymptodische Wachstum von f(n)
  Big-Θ
  f(n) є Θ(g(n)) ↔ f(n) є Ω (g(n)) ∩ f(n) є O(g(n))
  Θ(g(n)) = Klasse von Funktionen,
  die asymptodisch genauso schnell wie g(n) wachsen
  Θ ist eine Aquivalenzrelation auf der Menge der schließlich positiven Funktionen
  Eigenschaften
  reflexiv
  f(n) є O(f(n))
  f(n) є Ω(f(n))
  f(n) є Θ(f(n))
  transitiv
  f(n) є O(g(n)) ∩ g(n) є O(h(n)) → f(n) є O(h(n))
  f(n) є Ω(g(n)) ∩ g(n) є Ω(h(n)) → f(n) є Ω(h(n))
  f(n) є Θ(g(n) ∩ g(n) є Θ(h(n)) → f(n) є Θ(h(n))
  schiefsymmetrisch
  f(n) є Θ(g(n)) ↔ g(n) є Θ (f(n))
  Beispiel: Laufzeitanalyse für Merge-Sort
  PROCEDURE MergeSort(A,l,r); 1 IF l<r THEN 2 p:=(l+r)/2 3 MergeSort(A,l,p); 4 MergeSort(A,p+1,r); 5 Merge(A,l,p,r); // Mischt die beiden sortierten Teilfolgen
  A = Input-Array
  l, r = Positionen innerhalb des Arrays
  p = Position innerhalb des Arrays
  Rechenzeit
  Inputlänge := n
  Divide'n'Conquer des Mergesort: man teilt den Input in 2 Hälften und führt 2x Mergesort auf den halben Folgen aus:
  Teilen (Zeile 2, 3) braucht konstant viele Schritte → O(1)
  Merge (Zeile 5) beansprucht n*konstant viele Schritte → Merge є O(n)
  Rekurrenz
  T(n) = 2 T(n/2) + O(n) + O(1) ≤ 2 T(n/2) + cn
  T(1) = 1
  → T(n) є O(n log n)
  
  typische Funktionen g(n) =
  1
  konstante Laufzeit
  unabhängig von Eingabegröße
  log n
  logarithmische Laufzeit
  mit log ist nachfolgend immer der log₂ gemeint!
  n
  lineare Laufzeit
  n log n
  n²
  n³
  Cook'sche Linie
  2^{nexponentielle Laufzeit
  jenseits von gut und böse}
  Tabelle
  sei 0 < α < β, 0 < a < b, 1 < A < B
  geordnet, oben kleine, unten lange Laufzeiten
  log log n
  log^αn
  log^βn
  n^a
  n^a log^αn
  n^a log^βn
  n^b
  Aⁿ
  Aⁿn^a
  Aⁿn^b
  Bⁿ
- Klein-O-Notation
  o(g(n)) = { f(n) : Für alle c>0 Gibt es ein n₀>0, sodass für alle n > n₀ : 0 ≤ f(n) ≤ c*g(n) }
  transitiv
  nicht reflexiv
  nicht schiefsymmetrisch
  w(g(n)) = { f(n) : Für alle c>0 Gibt es ein n₀>0, sodass für alle n > n₀ : 0 ≤ c*g(n) ≤ f(n) }
  transitiv
  nicht reflexiv
  nicht schiefsymmetrisch
- Divide'n'Conquer
  Teile und Herrsche
  teile Problem
  berechne Teilergebnisse
  füge zu Ergebnis zusammen
  Beispiel: Merge-Sort
  Beispiel
  T(n) = 2 T (ⁿ/₂) + n, T(1) = 1
  T(n) = 4 T (ⁿ/₂) + 2n/log n, T(1) = ...
  T(n) = T (ⁿ/₂) + 1
- Segmentschnittproblem
Rekurrenzen
- Rekurrenzen sind Gleichungen für Funktionen f, bei denen die Funktion f durch kleinere Argumente und Anfangsbedingungen beschrieben wird.
- Beispiel: siehe Mergesort
- Veranschaulichung im Binärbaum
- allgemeine Methoden
  Substitutionsmethode
  vollständige Induktion
  Beispiel
  T(n) = 2 T (n/2) + b, b = const.
  Vermutung
  T(n) = O(n) ist Lösung
  T(1) = 1
  Ansatz 1
  T(n) ≤ cn,
  c = const.
  Voraussetzung
  T(1) = 1
  T(m) ≤ cm
  für m < n
  Behauptung
  T(n) = 2T(n/2) + b ≤ 2 c n/2 + b = cn + b
  ist nicht ausreichend!
  es muss genau der Ansatz rauskommen!
  Ansatz 2
  T(n) ≤ c n - b
  Voraussetzung
  T(1) = 1
  T(m) ≤ cm - b
  für m < n
  Behauptung
  T(n) = 2 T(n/2) + b ≤ 2 (cn/2 - b) + b = cn - b
  korrekt und ausreichend → Behauptung folgt, T(n) є O(n)
  Rekurrenzbäume
  Beispiel
  T(n) = 2 T(n/2) + n
  → T (n/2) = 2 T(n/4) + n/2
  → T (n/4) = 2 T (n/8) + n/4
  → O (n log n)
  Beispiel
  T(n) = cn² + 3 T(n/4)
  T(1) = 1
  T(n/4) = c(n/4)² + 3 T (n/16)
  T(n) = cn² + 3 [ c(n/4)² + 3 T (n/16) ]
  → T(n) = cn² + 3/16 cn² + (3/16)² cn² + (3/16)³ cn² ...
  = ∑_i=1^(log₄n)-1 (3/16)ⁱ cn² + Θ(n^log₄3)
  < ∑_i=1^∞ (3/16)ⁱ cn² + O(n^log₄3) = (∑_i=1^∞ (3/16)ⁱ) cn² + O(n^log₄3)
  = 1/(1-3/16)cn² + O(n^log₄3) = O(n²)
  Variablensubstitution
  Beispiel
  T(n) = 2 T (√n) + log n, T(1) =1
  k := log n → n=2^k
  T(2^k) = 2 T ( 2^k/2 ) + log 2^k
  T ( 2^k ) = 2 T (2^k/2) + k
  S(k) = T (2^k)
  Substitution
  S(k) = 2 S (k/2) + k
  → Lösung bekannt
  S(k) = O(k log k)
  Resubstitution
  T(2^k) = S(k)
  T(n) = T(2^k) = S(k) = O(k log k) = O (log n * log log n) = T(n)
  Master-Theorem
  Voraussetzungen
  a ≥ 1, b > 1 Konstanten
  f(n)
  T(n) sei definiert durch T(n) = a T(ⁿ/_b) + f(n)
  dann gilt
  wenn f(n) = O (n^log_ba-ε) mit ε > 0
  dann T(n) = Θ(n^log_ba)
  wenn f(n) = Θ (n^log_ba)
  dann T(n) = Θ(n^log_ba log n)
  wenn f(n) = Ω (n^log_ba+ε) mit ε > 0 und wenn EsGibt c < 1 : a*f(ⁿ/_b) ≤ c*f(n) FürAlle_n^∞
  dann T(n) = Θ(f(n))
  Anwendungsbeispiel
  sei a=1, b=2, f(n) = 1
  T(n) = T(n/2) + 1
  log_ba = log₂1 = 0
  Also: Θ(log n) ist die Zeit für die binäre Suche
  Anwendungsbeispiel
  a=4, b=2, f(n) = 2n² / log n
  T(n) = 4 T(n/2) + 2n²/log n
  f(n) = 2n²/log n → sicher: f(n) nicht є Θ(n²), nicht Fall 2
  Fall 1? Nein! Denn: f(n) wächst zwar langsamer als n²,
  aber nicht in der Potenz langsamer da log n < n^ε für beliebige ε>0
  Anwendungsbeispiel
  a = 9, b = 3
  T(n) = 9 T (n/3) + 3n log n
  ε = 1/2
  f(n) = O(n^3/2), es gilt f(n) = 3n log n = O(n^3/2)
  → ist Fall 1 des Master-Theorems: T(n) = Θ(n²)
Sortieren / Selektion
- Sortierproblem:
  INPUT = Zahlenfolge
  3 4 6 1
  OUTPUT = Zahlenfolge
  1 3 4 6
  algemein: Permutation der Inputfolge
  sortiert
  Ziel im Seriellen: O(n log n)
  in Sonderfällen O(n)
  im Parallelen - O(log n)
- insertion sort
  Algorithmus
  A: Input-Array
  Laufzeitanalyse
  Befehl 1
  n Aufrufe
  2
  n-1 Aufrufe
  3
  n-1
  4
  Σ_j=2ⁿ t_j
  5
  Σ_j=2ⁿ (t_j-1)
  6
  Σ_j=2ⁿ (t_j-1)
  7
  n-1
  n = Eingabegröße
  t_j = Häufigkeit des Tests in der while-Schleife
  t_j-1 = Häufigkeit der Ausführung der Schritte in der while-Schleife
  best case: Für alle j gilt:
  2 ≤ j ≤ n, t_j = 1
  T(n)=An+B
  T(n) є Θ(n)
  worst case: Für alle j gilt:
  2 ≤ j ≤ n, t_j = j
  T(n)=c/2*n² + (A+c/2)n - B
  T(n) є Θ(n²)
  average case
  bei Gleichverteilung
  E(T(n))= cn²/4 + (A - c/4)n - B
  T(n) є Θ(n²)
  Sortieren durch Einfügen an richtiger Stelle
- 1. Hauptsatz über das Sortieren
  allgemeines Sortieren auf der Basis von
  Schlüsselvergleichen geht nicht schneller als Ω(n log n)
  Schlüsselvergleich V(i,j) :=
  1 falls a_i < a_j
  0 sonst
  es sei a(i<j) = {a₁, ... , a_n} є Sⁿ : a_i < a_j (1 ≤ i, j ≤ n)
  für jeden Algorithmus gilt dabei
  Start = 1. Frage V(i,j)
  2. Frage: abhängig vom Ergebnis der 1. Frage
  → Entscheidungsbaum
  Beispiel
  a₁, a₂, a₃, a₄
  Allen Knoten entsprechen Mengen von Eingabetupeln mit bestimmten möglichen Eingabefolgen. Den Blättern müssen dann eindeutig bestimmte Reihenfolgen entsprechen, jeder Eingabereihenfolge muss mindestens 1 Blatt entsprechen!
  → man braucht mindestens n! Blätter.
  Binärbäume der Höhe h haben maximal 2ⁿ Blätter.
  → 2ⁿ ≥ n!
  → h ≥ log (n!)
  h ist hierbei ein Modell für die Rechenzeit des Algorithmus
  1 * 2 * 3 * ... * n/2 * ... * n ≥ (n/2)^n/2
  
  → log (n!) ≥ log (n/2)^n/2 = n/2*(log n - log 2)
  
  = n/3 log n + [n/6 * log n - n/2] ≥ n/3 log n
  also h≥1/3 n log n für n≥8,
  d.h. Für alle n bis auf endlich viele Ausnahmen gilt:
  Rechenzeit ist Ω(n log n)
  "untere Schranke" für beliebige serielle Algorithmen
  Verallgemeinerung auf lineares Modell
  nicht nur Schlüsselvergleich
  jetzt auch Fragen der Form g(x₁, x₂,...,x_n) = c₁x₁ + c₂x₂ + ... + c_nx_n + d < 0
  c₁, c₂,...,c_n: Konstanten
  Dieser Test geschehe in O(1)
  Aussage: 1. Hauptsatz über das Sortieren gilt auch linear
  Beweis
  M sei Teilmenge von Rⁿ
  ►M ist konvex ↔ Für alle p,q є M : pq ist Teilmenge von M
  ► M ist zusammenhängend ↔ Für alle p,q є M existiert ein
  Pfad p=p₁p₂...p_kq = p_ip_i+1 als Teilmenge von M
  Satz: wenn eine Menge M konvex ist, so ist sie auch zusammenhängend
  Die Tupel {(x₁,...,x_n) | g(x₁,...,x_n) = c₁x₁ + ... + c_nx_n + d = 0} definieren eine Hyperebene im Rⁿ.
  Hyperebene
  immer eine Dimension niedriger als der Raum in dem sie ist.
  Hyperebene im 3-D-Raum ist eine Ebene
  Hyperebene in der Ebene ist eine Gerade
  Dann ist über die Frage g(x₁,...,x_n) < 0 eine Einteilung gegeben
  (x₁,...,x_n) erfüllt g(....) < 0 ↔ (x₁,...,x_n) є "Halbraum der Dimension n"
  Satz: Halbräume sind konvex und daher auch zusammenhängend
  a_i < a_j ↔ a_i - a_j < 0, d.h. c_ia_i + c_ja_j + c_ka_k < 0 ist eine Verallgemeinerung
  Satz: Hat eine Menge M (Teilmenge von Rⁿ)
  m Zusammenhangskomponenten, so benötigt
  jeder Algorithmus für den einzelnen Elementtest
  im linearen Modell Ω(log n) Schritte
- 2. Hauptsatz über das Sortieren
  Sortieren auf Basis von Schlüsselvergleichen kostet bei
  Gleichwahrscheinlichkeit aller Permutationen der Eingaben im Mittel Ω(n log n)
- Ungleichung von Kraft
  Binärbaum
  Menge M
  Ø ist ein Binärbaum mit Knoten aus M.
  (w,L,R) ist dann ein Binärbaum, wenn
  L Binärbaum mit Knoten aus M
  R Binärbaum mit Knoten aus M
  K(L), K(R) sind die Knotenmengen von L und R
  K(L) ∩ K(R) = Ø
  w є M \ ( K(L) U K(R) )
  Pfadlängen von Wurzel zu Blättern := t_i
  1 ≤ i ≤ m
  es gilt dann:
  
  ∑_i=1^m 2^-t_i ≤ 1
  Beweis
  Induktion über m
  m = 1 → trivial
  m ≥ 2
  Baum hat 2 Teilbäume mit m₁ und m₂ Blättern.
  neue Pfadlängen: t_1/1...t_1/m1 und t_2/2.....t_2/m2
  es gilt:
  ∑^m1 2^-t[1/i] ≤ 1
  ∑^m2 2^-t[2/i] ≤ 1
- ε-closeness
  INPUT:
  n Zahlen a₁ ... a_n
  INPUT: ε > 0
  Frage
  Gibt es 2 Zahlen im INPUT, die einen Abstand kleiner als ε haben?
  existieren Indizies i≠ j : 1 ≤ i j ≤ n : | a_i-a_j | ≤ ε
  Satz: e-closeness ist reduzierbar (polynomiell) auf das Sortierproblem
  ε-closeness ≤_pol Sort
  Vorgehen
  1.) ε-closeness ist Spezielfasll von Elementtest
  → Ω (n log n)
  2.) Sortieren hat im linearen Modell die Komplexität Ω(n log n)
  Beweis
  Input für (1.) ist (x₁,...,x_n), ε
  Sortiere (x₁,...,x_n) : x_π(1) < .... < x_π(n)
  Test in O(n)
  der OUTPUT ist die Antwort auf die ε-closeness-Frage
  Das die Beantwortung der ε-closeness-Frage mind. Ω(n log n)
  benötgt, kann sortieren nicht schneller gehen.
- Quicksort
  einfach
  Quicksort(l,r)
  if r > l then
    i:= Partition(l,r);
    Quicksort(l,i-1);
    Quicksort(i+1,r);
  Pivotelement
  Element, das am Ende an seiner Stelle steht
  erweitert
  Quicksort(l,r)
  if r > l then
    v:=a[r]
    i:=l-1
    j:=r
    repeat
      repeat
        inc(i)      // I
      until a[i]≥v
      repeat
        dec(j)      // II
      until a[j]≤v
      t:=a[i]
      a[i]:=a[j]
      a[j]:=t
    until j≤i       // III
    a[j]:=a[i]      // IV
    a[i]:=a[t]      // IV
    a[r]:=t         // IV
    Quicksort(l,i-1)
    Quicksort(i+1,r)
  end if
  v ist hier das Pivot-Element
- konvexe Hülle
  endliche Punktmenge S
  |S| = n
  S ist Teilmenge von Rⁿ
  convex hull, CH(S)
  Die konvexe Hülle einer endlichen Punktmenge S ist der Durchschnitt aller konvexen Mengen, die die Punkte aus S umfassen
  Sortieren mit der konvexen Hülle
  INPUT
  x₁,...,x_n є R
  daraus gebildet
  (x₁,x₁²),(x₂,x₂²),...
  diese Punkte liegen auf der Normalparabel
  Konvexe Hülle berechnen
  Projektion auf die x-Achse
  ergibt OUTPUT
  Zeit dafür: O(n) + Berechnung für die konvexe Hülle
  es gilt: da Sortieren nicht schneller als n log n geht,
  muss auch die Berechnung der konvexen Hülle
  mindestens Ω(n log n) Zeit beanspruchen.
  Folgerung: die Berechnung der konvexen Hüle benötigt auch Ω (n log n) Schritte.
- Linearzeitsortierverfahren
  stellen Bedingungen (Einschränkungen) an den Input
  Countingsort
  beruht nicht auf Schlüsselvergleichen
  INPUT: n natürliche Zahlen aus (0,k]
  Idee: für jedes j є (a,k] zählen, wieviele Elemente ≤ j sind
  CountingSort(A,B,K):
  FOR i=0 TO k DO
  C[j] = 0;
  FOR j=1 TO #A DO
  C[A[j]] = C[A[j]]+1;
  FOR i=1 TO k DO
  C[i] = C[i] + C[i-1];
  FOR j = #A DOWNTO 1 DO
  B[C[A[j]]] = A[j];
  C[A[j]] = C[A[j]]-1
  warum B rückwärts aufbauen?
  Stabilität: relative Reihenfolge gleicher Elemente bleibt erhalten
  Beispiel
  k=5
  A=(2,5,3,0,2,3,0,3
  i= 0 1 2 3 4 5
  C= 2 2 4 7 7 8
  c[i] = Zahl der Elemente die ≤ i sind.
  Zeit:
  O(n+k)
  ist k є O(n) → Gesamtzeit ist O(n)
  k є O(n) → Gesamtzeit ist O(n)
  Radix-Sort
  Werte aus größerem Bereich in linearer Zeit sortieren
  Elemente aus [0,k^d-1]
  k,d є N, d konstant
  a є [0,k^d-1]
  a = ∑_i=0^d-1 a_ik_i
  a_i є [0, k-1]
  Bsp. k=10 → 397 = 3*10²+9*10¹+7*10⁰
  Algorithmus
  FOR r=0 TO d-1 DO
  Sortiere r-tes Bit (Stelle) mit einem geeigneten Verfahren
  Radix-Sort kann mit Counting-Sort für die einzelnen Bits n d-stellige Zahlen in O(d(n+k)) sortieren
  Beispiel mit k=10 und d=3
  unsortiert|
     |1.Stelle|
     |   |2.Stelle|
     |   |   |3.Stelle
  707 001 001 001
  502 502 502 123
  203 522 203 203
  273 203 604 273
  399 273 707 399
  322 123 522 502
  123 604 123 522
  604 707 273 604
  777 777 777 707
  001 399 399 777
- Selektion
  Input
  Aⁿ
  Array
  Elemente (nicht paarweise) verschieden
  k
  1 ≤ k ≤ n
  Beispiel
  A=(9, -5, 2, -7, 6, 0, 1)
  sei a_i є A
  es ist Rang (a_i, A) := # {k є A | k ≤ a_i}
  Rang(1,A) = 4
  es sei a_(k) das Element vom Rang k
  Output
  a_(k)
  Spezialfälle
  k = 1 → Minimum
  k = n → Maximum
  k = n/2
  Komplexität
  O(n log n)
  Aufgabe durch Sortieren des Arrays drastisch vereinfacht
  Sortieren = O(n log n), Auswählen des k-ten Elementes = O(1)
  Algorithmus
  Q: Konstante
  n= |A|
  2 Fälle
  Eingabe ist kleiner Q
  sortieren und A[k] ausgeben
  O(1)
  Eingabe ist größer als Q
  1. Aufteilen in n/Q Teilfolgen der Länge Q
  O(n)
  2. Bestimmen der Mediane jeder Teilfolge m₁...m_{n/Qdazu einzelne Teilfolgen sortierenO(n)}
  3. Bestimmen des Medians der Mediane, m
  T(n/Q)
  4. Bilden der Mengen A₁, A₂, A_{3A₁ = { x є A | x < m }Betrachte alle Teilfolgen deren Median kleiner ist als m
  aus diesen Teilfolgen wähle alle Elemente, die ≤ dem
  
  jeweiligen Median m_i der Teilfolge sind.
  A₂ = { x є A | x = m }es gilt |A₁| > n/4
  es gilt |A₃| > n/4
  |A₁| ≤ 3n/4
  |A₃| ≤ 3n/4
  A₃ = { x є A | x > m }Betrachte alle Teilfolgen, deren Median größer als m ist
  aus diesen Teilfolgen wähle alle Elemente, die ≥ dem
  jeweiligen Median m_i der Teilfolge sind
  O(n)}
  if k ≤ |A₁| then OUTPUT(Select(A₁,k))
  Element vom Rang i ist in Teilmenge A₁
  relatives Sortieren, links vom Median
  T(3n/4)
  if |A₁| < k ≤ |A₁| + |A₂| then OUTPUT(m)
  Element ist in Teilmenge A₂
  O(1)
  if k ≥ |A₁| + |A₂| then OUTPUT( Select(A₃, k-( |A₁| + |A₂| ) )
  Element ist in Teilmenge A₃
  relatives Sortieren, rechts vom Median
  T(3n/4)
  T(n) = O(1) + 3O(n) + T(n/Q) + T(3n/4) = O(n) + T(n/Q) + T(3n/4)
  ist O(n), falls n/Q+3n/4 < n
  O(n) ↔ ⁿ/_Q + ³/₄n < n
  → es gibt unendlich viele Algorithmen, die jeweils von Q abhängen
- S-Quicksort
  if n=2 und a₁ < a₂ then
    tausche a₁ und a₂
  else
    if n > 2 then
      m:=Select(A,n/2);
      A₁ := {x є A | x ≤ m} // |A₁| = n/2
      A₂ := {x є A | x ≥ m} // |A₂| = n/2
      S-Quicksort(A₁)
      S-Quicksort(A₂)
    end
  end
  hat keine praktische Bedeutung
- Heaps und Heap-Sort
  Datenstruktur Binärheap
  Definition
  Folge F = k₁,...,k_N
  k_i ≤ k_{i/2heap Property}
  also
  k_i ≥ k_2i
  k_i ≥ k_2i+1
  Kinder sind kleiner oder gleich dem Elter
  "Heap-Property"
  immer vollständiger Baum oder von links aufgefüllt
  wird verwendet um ADT Priority Queue zu implementieren
  Beispiel
  F=(8,6,7,3,3,4,5,2,1)
  i = 1 → 8 ≥ 6, 8 ≥ 7
  i = 3 → 7 ≥ 4, 7 ≥ 5
  Operationen
  PARENT
  Parent(i)
    return(i/2)
  end
  O(1)
  Linker Sohn
  LS(i)
    return(2i)
  end
  O(1)
  Rechter Sohn
  RS(i)
    return(2i+1)
  end
  O(1)
  BuildHeap
  BuiltHeap(A):
  Heapsize(A)=Länge(A);
  FOR i=Länge(A)/2 DOWNTO 1 DO
    Heapyfy(A,i); // Versickern der Werte
  O(n)
  1. Überlegung
  Size → O(1)
  Schleife → O(n)
  Heapyfy → O(log n)
  → BuildHeapy = O(n log n)
  geht aber eigentlich schneller!
  2. Überlegung
  In einem n-elementigen Heap gibt es höchstens ⁿ/2^h+1 Knoten der Höhe h
  Kosten für Heapyfy für Knoten der Höhe h ist O(h)
  ∑_h=0^{log n} n/2^h+1 *O(h) = O(n ∑_h=0^{log n} n/2^h+1) =O(2n) = O(n)
  Heapyfy
  Heapyfy (A,i):
  l := LS(i);
  r := RS(i);
  IF (l ≤ Heapsize(A)) und (A[l] > A[i]) THEN
    max:=l;
  ELSE
    max:=i;
  IF r ≤ Heapsize(A) und (A[r] > A[max] THEN
    max:=r;
  If max ≠ i THEN
    Tausche(A[i],A[max]);
    Heapyfy(A,max);
  Stellt Heap-Property wieder her
  O(log n)
  O(1) für das ermitteln der Beziehungen zwischen A(i), A(LS(i)) und A(RS(i))
  Zeit für Heapyfy auf einem Teilbaum der von einem Kind ausgeht.
  Diese Teilbaume haben maximal die Größe 2n/3
  also: T(n) = T(2n/3) + Θ(1)
  Zweiter Fall des Master-Theorems → log n
  HeapSort
  HeapSort(A):
  BuildHeap(A);
  FOR i:=Länge(A) DOWNTO 2 DO
    Tausche(A[i],A[1]);
    HeapSize(A):=HeapSize(A)-1;
    Heapyfy(A,1);
  O(n log n)
  O(n) für BuidHeap
  O(n) für Schleife
  O(1) für Tauschen der Werte
  O(1) für verkleinern des Heaps
  O(log n) für Heapyfy
  
  ist ein ADT
- Priority Queue
  Implementierungsmöglichkeit: Heap
  Anwendung: Algorithmus von Dijkstra
  Problem:
  Gelände mit Hindernissen
  gesucht: kürzester Weg (Start → Ziel) im Gelände
  unter Umgehung des unüberwindbaren Bereichs
  ►Satz (Lorenzo Perez):
  Der kürzeste Weg erfolgt innerhalb des Sichtbarkeitsgraphen.
  → Graph (V,E)
  V: Menge aller Ecken
  E: Menge aller sichtbaren Kanten
  zwei Kanten heißen Sichtbar, wenn man sie durch eine Kante verbinden kann, die gänzlich im inneren des freien geländes liegt
  Abstraktion: Algorithmus von Dijkstra:
  INPUT
  ein beliebiger Graph (V,E)
  gerichtet
  sog. Digraph, directed graph
  STARTecke aєV
  Kantenmarkierungen der gerichteten Kanten
  Algorithmus von Dijkstra:
  1 FORALL vєV DO
      d(v) := ∞; W := Ø;
  2 d(s) := 0;
  3 initialisiere Struktur für V\W // ist zu Begin = V
     als Priority Queue, geordnet nach Distanzen
  4 WHILE V\W ≠ Ø DO
  5   v:=Min(V\W); ExtractMin(V\W);
  6   W:=W U {v};
  7   FORALL w є Succ(v)\W DO
  8     IF d(v)+Kantenlänge(v,w) < d(w) THEN
  9       DecreaseKey(w,d(v)+Kantenlänge(v,w))
  ► Für alle v є V: Succ(v) = { w | (v,w) є E}
  Menge aller Knoten die von v direkt erreichbar sind
  s: Startpunkt
  Sei W die Menge der bekannten Punkte mit ihren kürzesten Wegen
  Sei d(v) = Länge des kürzesten Weges von Start zu v
  SP((V,E),l,s) = shortest path
  Laufzeit?
  abhängig von Datenstruktur
  es werden die Operationen benötigt:
  Insert
  ExtractMin
  müssen jeweils "schnell" unterstützt werden
  DecreaseKey
  Greedy-Algorithmus
  ist ein ADT
- Stabilität
  stabil
  Counting-Sort
  Merge-Sort
  Insertion-Sort
  instabil
  Heap-Sort
  Quick-Sort
Abstrakter Datentyp
eine Menge von Operationen
müssen effizient unterstützt werden
effizient = log n
Signatur
Operationen sind nur durch Axiome beschrieben
ADT
Beispiele
Priority Queue
MAKE HEAP
Erschaffen der leeren Datenstruktur
O(1)
INSERT
Insert(A,key):
HeapSize(A):=HeapSize(A)+1;
i:=HeapSize(A);
WHILE (i > 1) und (A[Parent(i)] < key) DO
  Tausche(A[i], A[Parent(i)]);
  i:=Parent(i);
A(i):=key;
O(log n)
MAX (/ MIN)
ändert Struktur nicht
Max(A):
Return(A[1]);
O(1)
EXTRAXTMAX (/EXTRACTMIN)
ändert Struktur
ExtractMax(A):
IF HeapSize(A)<1 THEN
  Error(Underflow);
Max:=A[1];
A[1]:=A[HeapSize(A)];
HeapSize(A):=HeapSize(A)-1;
Heapyfy(A,1);
Return Max;
O(log n)
Prority Queue - Varianten
erweitert
MAKE HEAP
MAX
EXTRACT MAX
INCREASE KEY
IncreaseKey(A,x,key):
IF A[x] > key THEN
  Fehler(alter Schlüssel größer als neuer);
A[x]=key;
WHILE (x > 1) und (A[x] > A[Parent(x)] DO
  Tausche (A[Parent(x)],A[x]);
  x=Parent(x);
O(log n)
DELETE
Mergeable Heaps
MAKE HEAP
INSERT
MAX
EXTRACT MAX
UNION
Wörterbuch (Dictionary)
Insert
Delete
Search
z.B. als Blattsuchbaum implementiert
einfache Datenstrukturen
Stack
Anschaulich: Array fester Länge n
Ist LIFO-Struktur
Last In - First Out
Operationen
StackEmpty
StackEmpty(S):
1 IF Top(S)=0 THEN   //Stack ist Leer
2   RETURN true;
3 ELSE
    RETURN false;
O(1)
Push
Push(S,x):
1 Top(S):=Top(S)+1;
2 S[Top(S)]:=x;
O(1)
Pop
Pop(S):
1 IF StackEmpty(S) THEN
2   Error(Stack ist leer!)
3 ELSE
    Top(S):=Top(S)-1;
4   RETURN (S[Top(S)+1]);
O(1)
Anwendung
Auswertung arithmetischer Ausdrücke
Compilerbau
Auflösung von Rekurrenzen
traversieren von Bäumen
hier: Struktur zur Verwaltung von Kandidaten
Algorithmus von Andrew
1979
≠ Algorithmus von Graham, siehe Cormen
Gegeben: endliche Punktmenge S Teilmenge R²
im rechteckigen kartesischen Koordinatensystem
Annahme: allgemeine Lage
Sonderfälle ausgenommen
→ hier: keine Punkte mit gleichen Koordinaten
→ es gibt einen linkesten und einen rechtesten Punkt
zu bestimmen: Konvexe Hülle
CH(S), convex hull
Ansatz: Teilen der Punktmenge nach äußeren Punkten
noch zu bestimmen: upper convex hull
UCH(S)
o.B.d.A. seien alle Punkte aus S oberhalb der Geraden AB (mit Ausnahme von A,B)
Sortieren der Punkte aus S nach x-Werten
Algorithmus von Andrew
Push(q_n);
Push(q₁);
Push(q₂);
s:=2; // t=2, x₀=q_n, x₁=q₁, x_t=q_s
WHILE s≠n DO
  α = Stack[Top];
  β = Stack[Top-1];
  WHILE (q_s+1,α,β) keine Linksdrehung DO
    Pop;
    α := β;
    β := neues zweites Element;
  Push(q_s+1);
  s:=s+1;
Output;
Invariante:
Die Punkte x₁, x₂, ... ,x_top bilden eine Teilfolge
von q_n, q₁, q₂, ... mit den Eigenschaften
t ≥ 2, s ≥ 2
Schritte s
x₀ = q_n
x₁ = q₁
x_t = q_s
x₁, ... , x_t ist obere konvexe Hülle
Die Punkte sind sortiert
Amortisierte Kostenanalyse
Jedes Push wird mit 2 Euro bezahlt
Jedes Pop kostet 1 Euro
→ wann kommt Pop?
nur wenn vorher Push erfolgte
kein Punkt wird wieder eingefügt, wenn er einmal mit POP entfernt wurde
→ Time ≤ 2 * Anzahl der PUSHs
→ Algorithmus funktioniert in O(n)
für Sortierte Inputfolge
amortisiert
nicht jeder Einzelschritt wird betrachtet
Folge der Schritte wird bedacht
Satz: Invariante wird bis Schritt 2 hergestellt und bleibt dann erhalten
→ Algorithmus ist korrekt
Notwendig für die Berechnung: Erkennung des Drehsinns 3er Punkte
Rechtsdrehung
Linksdrehung
binäre Suchbäume
T heisst binärer Suchbaum, wenn
T = Ø (T ist leer) oder
T besteht aus den drei disjunkten Mengen
{ROOT}
LTB
ein binärer Suchbaum
linker Teilbaum
RTB
ein binärer Suchbaum
rechter Teilbaum
T erfüllt die binäre Suchbaumeigenschaft
Sei X ein Zeiger auf einen Knoten des binären Suchbaums
ist Y Knoten des linken LTB(X), so gilt key[X] ≥ key[Y]
ist Y Knoten des linken RTB(X), so gilt key[X] ≤ key[Y]
Implementierungen
als zusammengesetzte Stuktur
Objekte
Attribute
beschrieben durch Klammern [ ]
z.B. Länge [ A ]
Beispiel
nur zwei Söhne
Vater / Sohn nicht vorhanden: Zeiger auf NIL
mehr als zwei Söhne
linker Sohn
rechter Bruder
TreeMin
TreeMin(x)
1 WHILE LS(x) ≠ NIL DO
2   x=LS(x);
3 RETURN (x);
T(n) = O(h)
h = Höhe des Baumes
TreeSucc
TreeSucc(x):
1 IF RS[x] ≠ NIL THEN
2   RETURN (TreeMin(RS[x]));
3 y:=P[x];
4 WHILE (y≠NIL) und (x=RS[y]) DO
5   x:=y;
6   y:=p[y];
7 RETURN (y);
T(n) = O(h)
TreeSearch
TreeSearch(x,k):
1 IF (x=NIL) oder (k=key[x]) THEN
2   RETURN (x);
3 IF k < key[x] THEN
4   RETURN(TreeSearch(LS[x],k));
5 ELSE
    RETURN(TreeSearch(RS[x],k));
T(n) = O(h)
TreeInorder
TreeInorder(x):
1 IF x≠NIL THEN
2   TreeInorder(LS[X]);
3   Output(Key[x]);
4   TreeInorder(RS[x]);
liefert eine Sortierung
T(n) є O(n)
T(n) = T(k) + T(n-k-1) + d
k = Anzahl Knoten des LTB
n-k-1 = Anzahl Knoten des RTB
d = const.
T(n) ≤ (c+d)k +c + (c+d)(n-k-1) + c + d = (c+d)n +c
→ T(n) = Θ(n)
TreePreorder
TreePreorder(x):
1 IF x≠NIL THEN
2   Output(key[x]);
3   TreePreorder(LS[x]);
4   TreePreorder(RS[x]);
TreePostorder
TreePostorder(x):
1 IF x≠NIL THEN
2   TreePostorder(LS[x]);
3   TreePostorder(RS[x]);
4   Output(key[x]);
Insert
TreeInsert(t,z):
1 y=NIL;
2 x=Root[t];
3 WHILE x≠NIL DO
4   y=x;
5   IF key[z] < key[x] THEN
6     x=LS[x];
    ELSE
7     x=RS[x];
8 P[z]=y;
9 IF y=NIL THEN
10 Root[t]=z;
ELSE
11 IF key[z] ≤ key[y] THEN
12    LS[y]=z;
    ELSE
13    RS[y]=z;
Delete
TreeDelete(t,z):
1 IF (LS[z] = NIL) oder (RS[z] = NIL) THEN
2    y=z;
    ELSE
3    y=TreeSucc(z);
4 IF LS[y]=NIL THEN
5    x=LS[y];
    ELSE
6    x=RS[y];
7 IF x≠NIL THEN
8    P[x]=P[y];
9 IF P[y]=NIL THEN
10   Root[t]=x;
    ELSE
11   IF y = LS[P[y]] THEN
12     LS[P[y]]=x;
     ELSE
13     RS[P[y]]=x;
14 IF y≠z THEN
15   key[z]=key[y];
16 RETURN (y);
Rotationen
können auf alle binären Suchbäume angewendet werden
verletzen Suchbaumeigenschaft nicht.
►Der Aufwand eine beliebige Inputfolge von Zahlen
in einen binären Suchbaum zu bringen ist Θ(n log n).
Wäre der Zeitaufwand geringer, würde dies bedeuten, dass Sortieren schneller als n log n geht!
Algorithmus von Graham
höhenbalancierte Suchbäume
Höhe h soll gleich log n sein!
Problem: Implementierung sehr schwierig
Top-Down-2-3-4-Bäume
erlaubte Teilstrukturen
Beispiel
Einfügefolge: 1, 15, 5, 2, 16, 4, 9, 13, 8, 6, 17
Schon bei der Suche nach dem Einfügepunkt wird jeder 4er-Knoten sofort aufgespalten!
stets vollständig balanciert!
Höhe h ≤ log n
O(log n)
Rot-Schwarz-Bäume
Axiome
Jeder Knoten ist rot oder schwarz
Die Wurzel ist schwarz
Blätter (NIL) sind schwarz
Ein roter Knoten darf keinen roten Vater haben
Die Schwarzhöhe ist für alle Blätter gleich
bh(x)
Scharzhöhe: Anzahl schwarzer Blätter auf Pfad von Wurzel zu Blatt
→ Transformation:
ist binärer Suchbaum
vollständig höhenbalanciert
n innere Knoten → maximale Höhe ist 2 log (n+1)
Beweis
Hilfssatz
In einem Rot-Schwarz-Baum hat jeder innere Knoten x
einen an ihm hängenden Teilbaum mit > 2^bh(x)-1 inneren Knoten.
Beweis:
Induktionsanfang: R-S-Baum bestehe nur aus der Wurzel → h = 2⁰ - 1 = 0 (trivial)
Induktionssatz: bh(a) = bh(x) falls a rot ist, bh(x)-1 falls a schwarz ist
Farbe von x spielt keine Rolle, der Knoten selbst wird nicht mitgezählt
Induktionsvoraussetzung:

      1   +   (2^bh(x)-1-1) + (2^bh(x)-1-1) = 2^bh(x)-1
innerer        LTB            RTB
Knoten
ist die Höhe h, so ist die Zahl der schwarzen Knoten in einem Pfad von Root zu einem Blatt mindestens h/2
→bh(Root) ≥ h/2
n ≥ 2^h/2 - 1 → n+1 ≥ 2^h/2 → log (n+1) ≥ h/2 → h ≤ 2 log (n+1)
Folge: Laufzeit O(log n)
TreeSearch
TreeMin
TreeMax
TreeSucc
TreePred
Operationen (von binären Suchbäumen angepasst)
NIL[T] ist ein Knoten, der jeden NIL-Zeiger ersetzt
RS-Insert
RS-Insert(T,z):
1 y=NIL[T];
2 x=Root[T];
3 WHILE x≠NIL[T] DO
4    y=x;
5    IF key[z] < key[x] THEN
6      x=LS[x];
     ELSE
7      x=RS[x];
8 P[z]=y;
9 IF y=NIL[T] THEN
10   Root[T]=z;
   ELSE
11   IF key[z] < key[y] THEN
12     LS[y]=z;
     ELSE
13     RS[y]=z;
14 LS[z]=NIL[T];
15 RS[z]=NIL[T];
16 Color[z]=rot;
17 Korrigiere(T,z);
Laufzeit: O(log n)
Korrigiere
Korrigiere (T,z):
1 WHILE color[P[z]]=rot DO
2    IF P[z] = LS[P[P[z]] THEN
3      y=RS[P[P[z]]     //Onkel
4      IF color[y]=rot THEN   //roter Onkel - Fall 1
5        color[p[z]]=schwarz;
6        color[y]=schwarz;
7        color[P[P[z]]]=rot;
8        z=P[P[z]];
       ELSE
9        IF z=RS[P[z]] THEN   // schwarzer Onkel, z ist rechter Sohn - Fall 2
10         z=P[z];
11         Linksrotation(T,z);
12       color[P[z]]=schwarz; // schwarzer Onkel, z ist linker Sohn - Fall 3
13       color[P[P[z]]]=rot;
14       Rechtsrotation(T,P[P[z]]);
15   ELSE
16   ... // Das Ganze nochmal, jedoch Links und Rechts bei
            Söhnen und Rotationen vertauscht.
RS-Insert kostet O(log n)
(wegen Fall 1)
Fall 1: Roter Onkel. Kann wieder zu Fall 1 führen → kann durch gesamten Baum wandern
→ O(log n)

Fall 2: Schwarzer Onkel. z ist rechter Sohn.
Geht durch Rotation über in Fall 3.

Fall 3: Schwarzer Onkel, z ist linker Sohn.
Wird aufgelößt durch Rechtsrotation.

O(log n)
Linksrotation
Linksrotation(T,x);
1 y=RS[x];        //Setze y
2 RS[x]=LS[y];    // Wandle y's linken in x's rechten TB
3 P[RS[x]]=x;
4 P[y]=P[x];      // Verbinde x's Vater mit y
5 IF P[x]=NIL[T] THEN
6    Root[T]=y;
   ELSE
7    IF x=LS[P[x]] THEN
8      LS[P[x]]=y;
     ELSE
9      RS[P[x]]=y;
10 LS[y]=x;         // verschiebe x auf die Linke Seite von y
11 P[x]=y;
O(1)
Anwendungsbeispiel: Segmentschnittproblem
INPUT = Menge von Rechtecken
gewünschter OUTPUT: {(R1,R3),(R2,R3),(R3,R4)}
Menge aller sich schneidenden Paare von Rechtecken
Problem
(R3,R4)
Strecken schneiden sich nicht
Segmentschnittalgorithmus plane-sweep findet dieses Paar nicht
Lösung
Bestimmen der Diagonalen der Rechtecke
→ Punkte zuweisen
→ Algorithmus in 2 Schritten:
1. Segmentschnitt-Algorithmus
2. weiterer Plane-Sweep (Punkteinschlußtest)
event-point-Struktur
Statusstruktur
benötigt:
X-Koordinaten der linken und rechten Rechteckkanten
X-Koordinaten der Einschlußpunkte
Vorgehen
Falls linke Rechteckkante getroffen wird
→ füge Rechteck der verwalteten Menge hinzu
Falls rechte Rechteckkante getroffen wird
→ entferne Rechteck aus der verwalteten Menge
Falls Einschlußpunkt → Finde in der verwalteten Menge
alle Y-Intervalle, die y-Koordinaten des Punktes enthalten
Punkt-Einschluß-Test ist Output-sensitiv
Bentley: Struktur zur Verwaltung von Y
( li, x, (y₁, y₂), R)
li = Markierung linke Kante
x = x-Wert
y₁ = unterer Endpunkt
y₂ = oberer Endpunkt
R = Bezeichner des Rechtecks
( re, x, (y₁, y₂), R)
re = Markierung rechte Kante
x = x-Wert
y₁ = unterer Endpunkt
y₂ = oberer Endpunkt
R = Bezeichner des Rechtecks
( Punkt, x, y, R)
Einschlußpunkt
x, y = Koordinaten
R = Bezeichner des zugehörigen Rechtecks
Segment-Tree
INPUT: Menge von Rechtecken
y₀, y₁, ..., y_N → atomare Intervalle [y₀,y₁],[y₁,y₂]...[y_N-1,y_N]
Aufbau einer Rahmenstruktur auf dieser Basis
Darstellung im Baum
Intervallsuchbaum
Dann suche nach y* (Mittelpunkt von R4):
Notiere alle Werte in den Listen der dabei besuchten Knoten
→ Output = (R₄,R₂), (R₄,R₃), (R₄,R₁)
Laufzeit
Man kann zeigen
Insert → O(log n)
Delete → O(log n)
Search → O(log n)
Sortieren vorher → O(n log n)
→ Gesamtkosten O(n log n)
Output k
Anzahl der Überschneidungen
∑ = O(n log n + k)
O( n log n + k)

Varianten
Blattsuchbäume
innere Knoten enthalten größten Wert des linken Teilbaums
Blätter können als lineare Liste verkettet sein
Pointer zwischen den Blättern
AVL
Eigenschaften des Baums
spezieller, balancierter Binärbaum
Höhendifferenz von linkem und rechtem Teilbaum eines Knotens ist kleinergleich 1
hat ein Knoten die Höhe h+1, dann
hat er einen Teilbaum der Höhe h
und einenTB der Höhe h oder h-1
Die Anzahl der Blätter im Teilbaum der Höhe h+1 ist also mindestens so groß wie die Anzahl der Blätter in einem Teilbaum der Höhe h + die Anzahl der Blätter in einem Teilbaum der Höhe h-1
n_h+1 = n_h + n_h-1
Fibonacci-Reihe
Ein AVL-Baum gegebener Höhe h mindestens Fib(h+2) Blätter
Operationen
Suchen in O(log n)
Löschen
Fall1: Knoten x hat keine Kinder
Parent(x) hatte nur ein Kind
einzelnes Kind = x
Entfernen von x → Parent(x) balanciert
aber: Höhe verringert sich um 1!
→ Aufrufen von Del-Repair(Parent(x))
Parent(x) hatte zwei Kinder ohne weiter Kinder
→ Entfernen ohne Probleme
balance(Parent(x)) auf +1 oder -1 setzen
fertig
Parent(x) hatte zweites Kind mit weiterem Kind
Entfernen von x führt zu Störung von Parent(x)
→ Aufrufen von Del-Repair(Parent(x))
Fall2: Knoten x hat einen Sohn
x wird entfernt
Sohn wird an alter Position von x angehängt
Höhe schrumpft!
→ Aufrufen von Del-Repair(Parent(x))
Fall3: Knoten x hat zwei Kinder
ersetze x durch y=Succ(x)
lösche alten y
y kann keinen linken Sohn haben
→ Löschen kann nur in Fall 1 oder 2 übergehen
DelRepair
bei Aufruf gilt (Invarianten)
balance(Parent(x)) = 0
Höhe des Teilbaums(Parent(x)) ist um eins gefallen
solange beides gilt, erfolgt rekursiver Aufruf
betrachtet: Parent(x) ist LS(Parent(Parent(x)))
Fall1: balance(Parent(Parent(x))) = -1
linker Teilbaum war höher
wird jetzt in der Höhe verringert
→ balance(Parent(Parent(x))) := 0
Höhe verringert sich
→ DelRepair(Parent(Parent(x)))
Fall2: balance(Parent(Parent(x))) = 0
linker Teilbaum wird eins kleiner
rechter bleibt in Höhe erhalten
balance(Parent(Parent(x))) = 1
fertig!
Fall3: balance(Parent(Parent(x))) = 1
linker Teilbaum des Großvaters war schon um eins kleiner als rechter
wird jetzt noch kleiner
→ Verletzung der AVL-Eigenschaft
Sei q=Bruder(Parent(x)) 3 Fälle:
balance(q)=0
→ Linksrotation um Parent(Parent(x))
Gesamthöhe des Teilbaumes bleibt erhalten
→ fertig
balance(q)=1
→ Linksrotation um Parent(Parent(x))
Gesamthöhe des Teilbaums ist um eins kleiner geworden
balance(Parent(Parent(x))) = 0
→ DelRepair(Parent(Parent(x)))
balance(q)=-1
Löschen:
→ Rechtsrotation um q
→ Linksrotation um Parent(Parent(x))
Gesamthöhe des Teilbaums hat sich um eins verringert
balance(Parent(Parent(x))) = 0
→ DelRepair(Parent(Parent(x)))

Einfügen
problematisch
Operationen können Höhenbedingugn verletzen
deshalb Idee: normal Einfügen
dann überprüfen, ob Höhenbedingung verletzt
ggf. korrigieren
Teilbaum-höhen nicht nötig
nur Balance-Faktor merken
Baum leer
schaffe neuen Knoten mit zwei Blättern
lege Wert in diesem Knoten ab
Baum nicht leer
normal einfügen
Suchen der erwarteten Position von x
Suche endet in einem Blatt
Ersetzen des Blattes durch Wert x
3 Fälle
A
balance(parent(x))=1
LS(Parent(x)) = Blatt → RS(Parent(x)) ist kein Blatt
x soll links angehängt werden
(wenn x rechts angehängt werden sollte, wären wir bei der Suche im rechten TB weiter abgestiegen)
→ balance(Parent(x)):=0
Teilbäume haben nun gleiche Höhe
Höhe von P hat sich nicht geändert
B
balance(parent(x))= -1
RS(Parent(x)) = Blatt → LS(Parent(x)) ist kein Blatt
x soll rechts angehängt werden
(wenn x links angehängt werden sollte, wären wir bei der Suche im linken TB weiter abgestiegen)
→ balance(Parent(x)):=0
Teilbäume haben nun gleiche Höhe
Höhe von P hat sich nicht geändert
C
Beide Söhne des Vaters sind Blätter
balance(Parent(x)) = 0
Problem: Höhe eines Teilbaums von Parent(x) ändert sich
Balance weiter oben kann gestört werden
deshalb nötig: Balance prüfen, ggf. (Doppel-)Rotation
dazu: rufe Reperatur(Parent(x)) auf
beim Aufruf hat Parent(x) die Balance +1 oder -1
wieder 3 Fälle
hier betrachtet: Parent(x) ist ein linker Sohn
für Parent(x) = RS(Parent(Parent(X))) analog!
Balance(Parent(Parent(x))) = 1
rechter TB von Parent(Parent(x)) ist um eins länger gewesen
linker TB von Parent(Parent(x)) nun um 1 gewachsen
Parent(Parent(x)) nun ausbalanciert
Balance(Parent(Parent(x))) := 0
fertig!
Balance(Parent(Parent(x))) = 0
beide Teilbäume von Parent(Parent(x)) hatten gleiche Höhe
linker TB von Parent(Parent(x)) nun um 1 gewachsen
Balance(Parent(Parent(x))) := -1
höhe des TB hat sich verändert → Reperatur(Parent(Parent(x))) aufrufen!
→ weiterer Aufstieg im Baum
Balance(Parent(Parent(x))) = -1
linker TB von Parent(Parent(x)) ist um eins länger gewesen
linker TB von Parent(Parent(x)) nun um 1 gewachsen
sehr Problematisch: AVL-Eigenschaft im Teilbaum Parent(Parent(x)) verletzt!
wieder Fallunterscheidung
balance(P) = -1 (nach dem Einfügen)
einfache Rotation
Höhe des Teilbaums bleibt durch Rotation erhalten
kein Prüfen von höherliegenden Knoten
balance(P) = 1 (nach dem Einfügen)
Doppelrotation
erst Linksrotation(Parent(x))
dann Rechtsrotation(Parent(x))
Höhe ist nach den Rotationen wieder wie vor dem Einfügen
kein Prüfen von höherliegenden Knoten
Applet
dynamisches Programmieren
Voraussetzungen
optimale Teilstruktur
Gesamtlösung ist optimal, wenn jede Teillösung optimal ist
überlappende Teilprobleme
Entropie
∑ p_i = 1
H ( P₁,...,P_n ) = -∑ p_i log p_i = ∑ p_i log 1/p_i
p₁ = p₂ = ... = p_n = ¹/_n
Shannonsche Information
gleichverteilt
→ H (p₁,...,p_n) = H(¹/_n,...,¹/_n) = ∑ ¹/_n log n = log n
wenn alle möglichen Ergebnisse eines Zufallsexperiments die gleichen Werte haben, wissen wir am wenigsten über den Ausgang
Zuwachs an Information bei erhalten des Ergebnisses ist maximal
es gilt
H(p₁,...,p_n) ≤ log n
H(p₁, ..., p_n, 0) = H(p₁, ..., p_n)
H(p_π(1), ..., p_π(n)) = H(p₁, ..., p_n)
π( i ) sei eine Permutation
H(p₁, ..., p_n) ≤ -∑ p_i log q_i
Gibb'sches Lemma
für alle g gelte
q_i ≥ 0
∑q_i = 1
Beispiel Münzwurf
2 Mögliche Ausgänge
A1, A2
p₁ = P(A1)
p₂ = P(A2)
p₁ + p₂ = 1
→ p₂ = 1 - p₁
h(p₁) = H(p₁, 1-p₁) ≤ log 2 = 1
h(p) ist ein Maß für den Informationsgehalt des Zufallsexperimentes. h ist maximal, wenn beide Ausgänge gleich wahrscheinlich sind. Dann hat h den Informationsgehalt 1bit
Anwendung: mittlere Blattiefe eines Binärbaums
Sei T ein Binärbaum
es gilt die Ungleichung von Kraft
∑_i=1^m 2^-t_i ≤ 1
t_i := Tiefe des i-ten Blattes
1 ≤ i ≤ m

Gibb + Kraft:
H(p₁, ..., p_n) ≤ -∑ p_i log q_i
H(p₁,...,p_n) ≤ - ∑ p_i log q_i = - ∑ p_i log 2^-t_i = ∑ p_it_i
Satz: Die Entropie H ist eine untere Schranke
für die mittlere Blattiefe ∑ p_it_i
und damit auch eine untere Schranke für die mittlere Suchzeit in Blattsuchbäumen
Ziel: optimaler Wert für ∑p_it_i
Problem: t_Root = 0
→ man verwendet ∑ p_i(t_i+1)
= min
es gilt: T ist dann optimal, wenn auch sein linker und rechter Teilbaum optimal sind!
seien a₁, a₂, ..., a_n Knoten mit key[a_i] ≤ key[a_i+1]
Teilproblem a_i ... a_j mit 1 ≤ i ≤ j ≤ n
Prinzip: Jede optimale Lösung des Gesamtproblems liefert auch optimale Lösungen der Teilprobleme
Bellmannsches Optimalitätsprinzip
ist Voraussetzung für die anwendbarkeit von dynamischer Programmierung
→ gesucht ist optimaler Suchbaum
Lösung
p_i = P(a_i) = Wahrscheinlichkeit, dass nach a_i gesucht wird
p(i, j) := ∑_m^j_{= i} p_{mWahrscheinlichkeit, dass im Teilbaum a_i...a_j gesucht wird
= Summe der Wahrscheinlichkeiten der enthaltenen Knoten}
p(i, j) = p(i, k-1) + p_k + p(k+1, j)
e(i,j) := ∑_m^j_{= i} p_m (t_m+1)
Erwartete Suchkosten im Teilbaum a_i...a_j
Produkt der Pfadlängen zu Knoten mit deren Wahrscheinlichkeiten
e(i, j) = 0 falls j > i
e(i, j) = p(i, j) + min_i≤k≤j( e(i, k-1) + e(k+1,j) )
falls a_i ... a_j nichtleerer Teilbaum, so ist die optimale erwartete Suchzeit die,
die sich ergibt wenn die Wuzel a_k so gewählt wird, dass die Suchzeiten in
beiden Teilbäumen minimal sind.
e_k(i,j) = 1*p_k + e_LTB + e_{RTBp_k = Suchwahrscheinlichkeit der gewählten Wurzel a_k
e_LTB = p(i, k-1) + e(i, k-1)
e_RTB = p(k+1, j) + e(k+1, j)}
→ T(i,j) ist optimaler Baum für Teilproblem für (i,j)
bei der rekursiven Berechnung wird tabelliert:
e(i,j)
k(i,j)
Index der optimalen Wurzel für Teilbaum a_i...a_j
dient später der Rekonstruktion des Gesamtbaums
Beispiel
p₁ = 0.25
p₂ = 0.28
p₃ = 0.1
p₄ = 0.2
p₅ = 0.13
p₆ = 0.04
Applet für Anfang der Tabellen
ergibt
k(i,j)
i\j 1 2 3 4 5 6
1| 1 2 2 2 2 2
2| 2 2 2 2 2 2
3|    3 3 4 4 4
4|      4 4 4 4
5|        5 5 5
6|          6 6
aus erhaltenen Tabellen: Konstruktion des optimalen Suchbaums
entspricht "Teilbaum" a₁...a_n = a₁...a₆
also ist die Wurzel der Wert k(1,6) → a₂
Teilbäume
a₁...a₁ mit Wurzelindex k(1,1) = 1
Wurzel a₁
a₃...a₆ mit Wurzelindex k(3,6) = 4
Wurzel a₄
weitere Teilbäume an a_{4a₃
a₅...a₆ mit Wurzelindex k(5,6) = 5}
Ergebnis
es gilt mittlere Suchbaumtiefe ~ mittlere Suchzeit
Voraussetzung: Blattsuchbäume
Trick für Bäume T, deren innere Knoten Schlüssel speichern
Wurzel enthält nur noch Pfad-Info, nichts weiter
Wert α ist in Blatt gespeichert
aus der Entropie H(p₁, ... , p_n) = - ∑ p_i log p_i
für Bäume mit 2-blättrigen Knoten wird

H₃(p₁ ,..., p_n) = - ∑ p_i log₃ p_i
Satz: ► Die Entropie H₃ ist eine untere
Schranke für die mittlere Suchbaumtiefe
der Ternären Blattsuchbäume
mittlere Blattiefe des ternären Suchbaumes
                 ≤
1+ mittlere Knotentiefe des binären Suchbaums
es gilt log₃ p_i = (log p_i) / (log 3) ≈ 0.63 log p_i
→ 0.63 log p_i -1 ist untere Schranke für mittlere Suchzeit!
H = log p_i ist obere Schranke für mittlere Suchzeit im optimalen Suchbaum
→ mittlere Suchzeit liegt in [0.63 H - 1, H]
optimale Suchbäume
Gegeben:
Sequenz K = (k₁, k₂, ..., k_n)
Schlüssel
k₁ < k₂ < ... < k_n
p_i = P(k_i) = Wahrscheinlichkeit, dass nack k_i gesucht wird
sind innere Knoten des Baums
n+1 Dummy-Schlüssel d₀, d₁, d₂,...,d_n
repräsentieren Werte die nicht in K enthalten sind
q_i = P(d_i) = Wahrscheinlichkeit, dass nach d_i gesucht wird
sind Blätter des Baums
gesucht
Binärer Suchbaum T aus diesen Schlüsseln
erwartete Suchkosten minimal
→ sog. optimaler binärer Suchbaum
hat nicht notwendig minimale Gesamthöhe
Schlüssel mit höchster Wahrscheinlichkeit nicht zwingend in der Wurzel
es gilt
∑_iⁿ_{= 1} p_i + ∑_iⁿ_{= 0} q_i = 1
jede Suche (100% = 1) ist entweder erfolgreich (endet in innerem Knoten) oder nicht erfolgreich (endet in Blatt)
E(Suchkosten in T) = ∑_iⁿ_{= 1} (tiefe_T(k_i)+1)p_i + ∑_iⁿ_{= 0} (tiefe_T(d_i)+1)q_i

= 1 + ∑_iⁿ_{= 1} tiefe_T(k_i)*p_i + ∑_iⁿ_{= 0} tiefe_T(d_i)*q_i
tiefe_T(x) = Tiefe eines Knotens x im Baum T
Feststellungen
jeder Teilbaum des gesuchten Baumes muss
Schlüssel in einem zusammenhängenden
Bereich k_i,..., k_j (1 ≤ i ≤ j ≤ n) enthalten.
i ≥ 1
j ≤ n
j ≥ i-1
dieser Teilbaum muss auch die
Blätter d_i-1 , ... , d_j enthalten
im Optimalen Suchbaum muss dieser Teilbaum optimal sein!
→ optimale Lösung für Baum T lässt
sich aus optimalen Teilstrukturen erzeugen
rekursive Lösung
Seien e(i,j) die erwarteten Kosten für Suche nach
optimalen binären Suchbaum, der Schlüssel k_i .. k_j enthält
Gesamt-Ziel: Berechnung von e(1,n)
einfachster Fall: e(i,j) = e(i,i-1)
Teilbaum enthält nur Blatt d_i-1
erwartete Suchkosten = e(i, i-1) = q_i-1
Fall j ≥ i
sei k_r die Wurzel des Teilbaums k_i...k_j
e(i, j) = p_r + e_LTB + e_RTB
e_LTB = e(i, r-1) + w(i, r-1)
e_RTB = e(r+1, j) + w(r+1, j)
w(i, j) = ∑_m^j_{= i} p_m + ∑_m^j_=i-1q_m

= Summe aller Wahrscheinlichkeiten im Teilbaum
w(i, j) = w(i, j-1) + p_j + q_j
w(i, j) = w(i, r-1) + p_r + w(r+1, j)
→ e(i, j) = e(i, r-1) + e(r+1, j) + w(i, j)
man wählt dazu in jedem Teilbaum den Knoten k_r als Wurzel, der
zu den niedrigsten erwarteten Kosten führt.
e(i, j) = q_i-q falls j=i-1

e(i, j) = min_i≤r≤j [ e(i,r-1)+e(r+1, j) + w(i, j) ] , falls i ≤ j
dynamische Berechnung
tabellieren der Werte e(i, j)
tabellieren der Werte wurzel(i,j)
speichert den Index der Wurzel des Teilbaums k_i....k_j
tabellieren der Werte w(i,j)
mergable Heaps
Ausgangspunkt ist ADT Priority Queue
Min
ExtractMin
Make-Heap
Aufbau der leeren Datenstruktur
O(1)
Insert
Union
Merge, Vereinigung
DecreaseKey
Delete

in diesem Abschnitt verwendet: MinHeaps
Laufzeiten
Operationen
Make-Heap
Insert
Min
ExtractMin
Union
DecreaseKey
Delete

BinaryHeap (worst case)
Θ(1)
O(1)
Θ(log n)
Θ(n)
BinomialHeap (worst case)
Θ(1)
O(log n)
Θ(log n)
FibonacciHeap (average case)
Θ(1)
Θ(log n)
Binomialheaps
Binomialbaum
Regeln
1. B₀ ist ein Binomialbaum
2. Übergang B_k → B_k+1 :
neu angesetzter Knoten wird linker Sohn
im Sinne des geordneten Baums
geordneter Baum:
Beispiele
es gilt
im B_n sind 2ⁿ Knoten
B_n hat die Höhe n
Es gibt genau (²_i) Knoten im B_n der Tiefe i
Beweis
sei d(n,i) die Anzahl der Knoten der Tiefe i im B_n
es ist d(n, i) = d(n-1, i) + d(n-1, i-1) = (ⁿ_i^-1) + (ⁿ_i^-_-¹₁) = (ⁿ_i)
Induktion
die Wurzel des B_n hat n Söhne
Wald von Binomialbäumen
heapgeordnet
min-Heaps
Wurzeln in Liste verknüpft
Wurzeln in Liste nach Wurzel-Degree geordnet
hier: Ausgangsgrad (weil Wurzelbaum)
Grade der Wuzeln im Binomialheap mit n Knoten ist Teilmenge von {0, 1, ..., log n}
Für alle k є N gilt: #B_k ≤ 1
also im Heap maximal ein Binomialbaum jeder Größe
jede natürliche Zahl lässt sich darstellen als n = ∑a_ig^{ieindeutige g-adige Darstellung
g є N
g ≥ 2
Darstellungsmöglichkeit
Wurzel-Degree nach rechts wachsend
Beispiel:12 = 1100_{bin
0 x B₀, 0 x B₁, 1 x B₂, 1 x B₃
hat 12 Knoten}
13 = 1101_{bin
1 x B₀, 0 x B₁, 1 x B₂, 1 x B₃
hat 13 Knoten}
14 = 1110_{bin
0 x B₁, 0 x B₁, 1 x B₂, 1 x B₃
hat 14 Knoten}
→ für jede Knotenzahl gibt es einen entsprechenden Heap}
es werden Mengen von Objekten dargestellt
Objekt hat Attribute = "Felder"
P[x]
zeigt auf den Vater eines Knotens
ist für Wurzeln = NIL
key[x]
degree[x]
Knotengrad
= Anzahl der Kinder
Linker-Sohn-Rechter-Bruder-Darstellung
LS[x]
Zeigt auf den linkesten Sohn
hat x keine Kinder, so ist LS[x] = NIL
reB[x]
Zeigt auf den rechten Bruder von x
wenn x eine Wurzel ist, so zeigt es auf die Wurzel des benachbarten Baumes
ist NIL, falls x rechtester Knoten im Baum auf seiner Ebene
ist NIL, falls x größte Wurzel ist (MinHeap)
Zugriff auf Heap H über head[H]
Zeiger auf erste Wurzel in Wurzelliste
ist NIL, falls H leer ist
Operationen
Min(h)
Min(H):
1 y=NIL
2 x=head[H]
3 min:=∞
4 WHILE x≠NIL do
5    IF key[x] < min THEN
6       min = key[x]
7       y=x
8    x=reB[x]
9 RETURN y
Heap ist min-heap-geordnet
→ minimaler Schlüssel muss in einer Wurzel stehen
Min durchforscht alle Wurzeln
speichert Zeiger auf kleinstes Element in y
log n + 1 Wurzeln
O(log n)
while-Schleife wird O(log n) mal durchlaufen
Link(y,z)
y und z sind beide Bäume B_{k-1 gleiche Knotenzahl}
z ist nach Aufruf dann ein Baum B_k
Link(y,z):
1 p[y]=z;
2 reB[y]=LS[z]
3 LS[z]=y
4 degree[z]=degree[z]+1;

Θ(1)
Union ( H₁ , H₂ )
Union(H1,H2):
1 H=MakeHeap()
2 head[H] = Merge(H1,H2) // Wie bei Merge-Sort, Vergleich nach Degrees (Sortieren der Wurzelknoten)
3 "zerstöre" die Objekte H1, H2, aber nciht die entsprechenden Listen
4 IF head[H]=NIL THEN
5     RETURN H
6 prevX=NIL //Variable
7 x=head[H]
8 nextX=reB[x] // Variable
9 WHILE nextX≠NIL DO
10   IF (degree[x]≠degree[nextX]) oder (( reB[nextX]≠NIL ) und (degree[reB[nextX]]=degree[x])) THEN
11       prevX=x
12       x=nextX
13   ELSE
         IF key[x]<key[nextX] THEN
14         reB[x]=reB[nextX]
15         Link(nextX,x)
16      ELSE
          IF prevX=NIL THEN
17           head[x]=nextX
18        ELSE
            reB[prevX]=nextX
19      Link(x,nextX)
20      x=nextX
21   nextX=reB[x]
22 RETURN H
Anlegen einer neuen Leeren Sturktur
Zusammenmischen der beiden Heaps
nach Grad steigend sortiert
löschen der alten Objekte
"Durchklappern" der Wurzelliste auf Suche nach Bäumen gleichen Grades
verwendete Zeiger (ab Zeile 6)
x - aktuelle Wurzel
prevX - Wurzel links von x
nextX - Wurzel rechts von x
werden zwei Wurzeln gleichen Grades gefunden
zusammenfassen zu Baum
ist ein Grad höher
eins weiter Rücken
log n
in der Schleife O(1)
maximal 2 log n + 2 Schleifendurchläufe
Insert(H,x)
Insert(H,x):
1 H'=MakeHeap()
2 p[x]=NIL
3 reB[x]=NIL
4 degree[x]=0
5 LS[x]=NIL
6 head[H']=x
7 H=Union(H,H')
Fügt Knoten ein, indem es Binomialheap erzeugt der nur diesem Knoten enthält
Zeile 1 leeren Heap erzeugen
Zeile 2-5 Knoten initialisieren
es wird angenommen, dass key schon gesetzt wurde
Zeile 6 einfügen von Knoten in leeren Heap durch Setzen von Zeiger
Zeile 7 Heaps vereinigen
vereinigt den neuen Heap mit dem bestehenden
O(log n)
Zeilen 1-6: O(1)
Zeile 7: O(log n)
ExtractMin(H)
ExtractMin(H):
1 finde Wurzel x mit kleinstem key in Wurzelliste
2 entferne x aus der Wurzelliste von H
3 kehre die Reihenfolge der verketteten Liste der Kinder von x um, setze bei ihenen jeweils p auf NIL
4 H'=MakeHeap()
5 setze head[H'] auf den Kopf der resultierenden Liste
6 H = Union[H,H']
7 return x
O(log n)
DecreaseKey(H,x,k)
Schlüssel x
neuer Wert k
DecreasKey(H,x,k):
01 IF k>key[x]
02    ERROR('neuer Schlüssel größer als alter')
03 key[x]=k
04 z=p[x]
05 WHILE z≠NIL DO
06    tausche(key[z]↔key[x]) // und ggf. weitere Daten
07    x=z
08    z=p[x]
geht davon aus, dass Zeiger auf x gegeben
Verändert Wert von x
schiebt x wie bei Heaps üblich so lange nach oben, bis Heap-Ordnung stimmt
O(log n)
Delete(H,x)
Delete(H,x):
1 DecreaseKey(H,x,-∞)
2 ExtractMin(H)
O(log n)
amortisierte Kostenanalyse
Werkzeug
Messung der mittleren Kosten einer Folge von Operationen
kann verwendet werden um zu zeigen, dass Kosten einer einzelnen Operation klein sind in der Sequenz von Operationen, auch wenn einzelne, absolut betrachtete Op kostspielig ist
ist eine Form der Worst-Case-Analyse
worst-case →

∑ Kosten der Einzelschritte
          # Einzelschritte
garantiert die mittlere Performance jeder Operation im schlechtesten Fall
3 Methoden
Aggregatmethode
Bestimmung einer oberen Schranke für T(n)= Gesamtkosten einer Sequenz von Operationen
Kosten pro Operation dann T(n)/n
mittlere Kosten als amortisierte Kosten jeder
Operation → jede Operation ist gleich teuer
Beispiele
Stapel mit Multipop
Operationen
StackEmpty(S)
O(1)
Push(S,x)
O(1)
Pop(S)
O(1)
Multipop(S,k)
Multipop(S,k):
1 WHILE (not StackEmpty(S)) AND (k≠0)
2   POP(S)
3   k=k-1
Stapel mit n Objekten → Laufzeit = min(n,k)
→ T(n) = O(n)
einfache Analyse
ist echte obere Schranke
Schranke ist aber nicht scharf!
Sequenz von n Operationen → O(n²)
aber: mit Multipop kann nur entfernt werden, was vorher mit Push eingefügt wurde!
Anzahl der Pop-Aufrufe auf nichtleeren Stapel inklusive Multipop ist höchstens gleich Anzahl der Push-Aufrufe
maximal n Push-Operationen
beliebige Sequenz von n Push, Pop, Multipop umfasst maximal 2n Operationen
n Operationen mit insgesamt O(n) → einzelne Operation benötigt amortisiert O(1)

Binärzähler
A=[A₀ A₁... A_k] ist ein Array
A_i є {0 , 1}
Länge[A]=k
Increment(A)
1 i=0
2 WHILE (i<Länge[A]) AND (A[i]=1) DO
3   A[i]=0
4   i=i+1
5 IF i<Länge[A]
6   A[i]=1
erste Analyse
einfache Ausführung benötigt im worst case Θ(k)
n Increment-Operationen → O(nk)
korrekt
nicht scharf!
amortisiert
Bit 0 klappt bei n Aufrufen n mal um
Bit 1 klappt bei n Aufrufen n/2 mal um
Bit 2 klappt bei n Aufrufen n/4 mal um
Bit i klappt bei n Aufrufen 1/2ⁱ mal um
einzelnes Bit Umklappen → Θ(1)
→ T(n) = ∑_i^k-1₌₀ ⁿ/2ⁱ < n∑_i^∞₌₀ ¹/2ⁱ = 2n = O(n)
→ Einzeloperation braucht die Zeit O(n)/n = O(1)
Guthabenmethode
differenziert zwischen verschiedenen Operationen
es werden "Guthaben" an bestimmte Objekte geheftet
spendiert durch bestimmte Operationen
verbraucht durch andere
eine/mehrere Methode(n) bezahlen für andere
Beispiele
Stapel mit Multipop
Operationen
StackEmpty(S)
O(1)
Push(S,x)
O(1)
Pop(S)
O(1)
Multipop(S,k)
Multipop(S,k):
1 WHILE (not StackEmpty(S)) AND (k≠0)
2   POP(S)
3   k=k-1
min(k,s)
erste Analyse
Stapel mit n Objekten → Laufzeit = min(n,k)
→ T(n)(eine Operation) = O(n)
einfache Analyse
ist echte obere Schranke
Schranke ist aber nicht scharf!
Sequenz von n Operationen → O(n²)
amortisiert
Kosten
Push:
tatsächlich: 1
hier: 2
beides in O(1)
Pop:
tatsächlich: 1
hier: 0
beides in O(n)
Multipop:
tatsächlich: n
hier: 0
amortisiert zu O(1)
Idee
Push bezahlt 2€
1€ für Push selbst
1€ wird an das Objekt geheftet,was durch Push auf den Stapel gelangt
Pop bezahlt nichts
müsste aber eigentlich 1€ bezahlen
Lösung: nehme den € von dem zu entfernenden Objekt!
Multipop bezahlt nichts
müsste eigentlich für jedes entfernte Objekt 1€ zahlen
Lösung: nehme den € vom jeweils zu entfernenden Objekt

Binärzähler
A=[A₀ A₁... A_k] ist ein Array
A_i є {0 , 1}
Länge[A]=k
Increment(A)
1 i=0
2 WHILE (i<Länge[A]) AND (A[i]=1) DO
3   A[i]=0
4   i=i+1
5 IF i<Länge[A]
6   A[i]=1
erste Analyse
einfache Ausführung benötigt im worst case Θ(k)
n Increment-Operationen → O(nk)
korrekt
nicht scharf!
amortisiert
jedes Umklappen eines Bits koste 1€
beim Klappen von 0 auf 1 werden 2€ statt einem berechnet
Zeile 6
kommt pro aufruf nur 1 mal vor
O(1)
1 euro für das Umklappen an sich
der andere € wird an die 1 geheftet
Klappen von 1 auf 0 kostet eigentlich 1€
wird aber nicht "von außen" bezahlt, sondern durch den € der an der jeweiligen 1 hängt
also: Aufruf der Prozedur
While-Schleife
wird von 1en bezahlt
kostet nichts
if-clause
bezahlt 2€
1x pro Prozeduraufruf
→ ein Prozeduraufruf kostet 2? → O(1)
obere Schranke für amortisierte Kosten ≥ ∑_iⁿ₌₁ AK_i ≥ ∑_iⁿ₌₁ K_{iAK_i = amortisierte Kosten für Operation i
K_i = theoretisch berechnete Kosten
→ die amortisierten Kosten stellen eine obere Schranke für die realen Kosten dar!}
Potentialmethode
ähnlich Guthabenmethode
Guthaben aber nicht an Objekte geheftet
Guthaben wird als gemeinsames Potential der Datenstruktur verwaltet
Definitionen
→ D₀ = Datenstruktur vor erster Operation (zu Begin)
D_i = Datenstruktur nach Ausführung der i-ten Operation
Φ_i = Φ(D_i) = Potential der Datenstruktur D_i
oft: Φ₀ = Φ(D₀) = 0
AK_i = amortisierte Kosten der Operation i = tatsächliche Kosten + Potentialdifferenz
Potentialdifferenz: Φ_i - Φ_i-1
tatsächliche Kosten = K_i
→ AK_i = K_i + Φ_i - Φ_i-1
Ziel: ∑AK_i ≥ ∑K_i → damit würden die amortisierten Kosten
eine obere Schranke für die tatsächlichen Kosten darstellen
Es gilt
Folge von Operationen 1...n →

∑_iⁿ₌₁ AK_i = ∑_iⁿ₌₁ (K_i + Φ_i - Φ_i-1) =

(∑_iⁿ₌₁ K_i) + Φ_n - Φ₀
→ Ziel ist erreicht, wenn Φ_n - Φ₁ ≥ 0
Beispiel
Stapel mit Multipop
Operationen
StackEmpty(S)
O(1)
Push(S,x)
O(1)
Pop(S)
O(1)
Multipop(S,k)
Multipop(S,k):
1 WHILE (not StackEmpty(S)) AND (k≠0)
2   POP(S)
3   k=k-1
min(k,s)
erste Analyse
Stapel mit n Objekten → Laufzeit = min(n,k)
→ T(n)(eine Operation) = O(n)
einfache Analyse
ist echte obere Schranke
Schranke ist aber nicht scharf!
Sequenz von n Operationen → O(n²)
amortisiert
Potential Φ := Anzahl der Elemente im Stack
AK_PUSH = K_PUSH + Potentialdifferenz_PUSH
= 1 + 1 = 2
AK_POP = K_POP + Potentialdifferenz_POP =
1 + (-1) = 0
AK_MultiPOP = K_MultiPOP + Potentialdifferenz_MultiPOP
= k' + (-k') = 0
k' = min(n,k)

Fibonacci-Heaps
verwalten dynamische Mengen
Wälder von Bäumen
sind in beliebiger Reihenfolge in Wurzelliste zusammengefasst
min[H] ist Zeiger auf kleinsten Knoten in Wurzelliste
Elemente werden als Objekte mit Attributen [ ] dargestellt
sohn[x] beliebig oder NIL
degree[x] = Anzahl der Söhne = Rang
maximaler Grad für Knoten in Heap mit n Knoten = D(n) = O(log n)
mark[x] speichert, ob x ein Kind verloren hat, seitdem x zum letzten mal zum Kind eines anderen Knotens gemacht wurde
→ Menge von Objekten
Beweis zu degree[x] ≤ log n
sei x beliebiger Knoten in H mit n Knoten
sei degree[x] = k
x habe die Kinder y₁, y₂, ... y_{kder Index bezeichne die Reihenfolge mit der sie eingefügt wurden
es gilt degree[y₁] ≥ 0 und degree[y_i] ≥ i-2degree[y₀] ≥ 0 ist offensichtlich
für i ≥ 2 giltx hatte Kinder y₁...y_i-1 als y_i verkettet wurde
→ degree[x] war zu diesem Zeitpunkt ≥ i-1
y_i wird nur mit x verkettet, wenn degree[y_i] = degree[x] ist
→degree[y_i] ≥ i-1 zum Zeitpunkt der Verkettung
Seit Verkettung mit x kann es höchstens ein Kind verloren habensonst wäre es durch cut abgetrennt worden
→ degree[y_i] ist immer ≥ i-2für alle Kinder y_i von x, mit iє{1,...,k}}
Fibonacci-Reihe
F_k = k-te Fibonacci-Zahl
F_k =
0, falls k=1
1, falls k=1
F_k-1 + F_k-2 sonst
F_k+2 = 1 + ∑_i^k₌₁ F_i > Φ^{kΦ = (1 + √5) / 2 ≈ 1.61803 ist der Goldene Schnitt}
es gilt: Größe(x) ≥ F_k+2 ≥ Φ^k
sei s_k die minimal mögliche Größe eines
Knotens in einem F-Heap, der den Grad k hat
trivial:
s₀=1
s₁ = 2
s_k ≤ Größe(x)
s_k steigt monoton mit k und ist untere Schranke für größe[x]
bestimmen von s_k:
eins für x zählen
eins für erstes Kind y₁ zählen
Größe der Kinder y₂..y_k = ∑_i^k₌₂ s_degree[yi]
→ s_k = 2 + ∑_i^k₌₂ s_degree[yi] ≥ 2 + ∑_i^k₌₂ s_{i-2wegen degree y_i ≥ i-2}
s_k ≥ 2 + ∑_i^k₌₂ s_i-2 ≥ 2 + ∑_i^k₌₂ F_i = 1 + ∑_i^k₌₀ F_i = F_k+2
also größe(x) ≥ s_k ≥ F_k+2 ≥ Φ^k

wegen n ≥ größe(x) ≥ Φ^k → n ≥ Φ^k → log n ≥ k log Φ → log_Φn ≥ k = degree[x]
→ jeder Knoten p eines F-Heaps mit degree[p]=k ist Wurzel eines Teilbaums mit ≥ F_k+2 Knoten
→ Maximum D(n), dass der Grad eines Knotens annehmen kann ist als O(log n)
Rang eines Knotens in einem F-Heap ist beschränkt, was consolidate ermöglicht
Verweise eigen jeweils nur auf einen Sohn, die anderen können über doppelt verkettete Ringliste erreicht werden

H = Heap mit zwei Attributen
min[H] = Zeiger auf das Minimum
n[H] = Anzahl der Elemente in H
Beispiel
Darstellung als F-Heap
Operationen
Kostenanalyse amortisiert
t[H] = Anzahl der Bäume in der Wurzelliste
m[H] = Anzahl der markierten Knoten im F-Heap
Potentialfunktion:
Φ(H) = t[H] + 2m[H]
MakeHeap
MakeHeap():
n[H]=0; // Anzahl der Elemente
min[H]=NIL
amortisierte Kosten
Potential Φ(H) = 0
Tatsächliche Kosten K=O(1)
amortisierte Kosten AK=K+Potentialdifferenz = O(1)
Insert
Insert(H,x):
1 degree[x]=0
2 p[x]=NIL
3 kind[x]=NIL
4 links[x]=NIL
5 rechts[x]=NIL
6 marke[x]=false
7 verkette die Wurzelliste, die x enthält mit der Wurzelliste von H
8 IF (min[H] = NIL) oder key[x] < key[min[H]]
9    min[H] = x
10 n[H] = n[H]+1
Zeile 1..6: Attribute initialisieren
Zeile 7 Knoten einfügen
Zeile 8..9: wenn x den kleinsten Schlüssel hat, so setze Min-Zeiger auf x
10: Knotenzähler erhöhen
Kosten
H=alter Heap
H' = geänderter Heap
t(H') = t(H) + 1
m(H') = m(H)
Potentialdifferenz: Φ(H') - Φ(H) = [ t(H)+1 + 2m(H) ] - [ t(H) + 2m(H) ] = 1
tatsächliche Kosten = O(1)
→ amortisierte Kosten = O(1) + 1 = O(1)
Min
bestimmen des Minimums
durch Zeiger auf Min[H]
tatsächliche Kosten: O(1)
keine Änderung des Heaps → Potentialdifferenz = 0
→ amortisierte Kosten = O(1)
Union
UNION(H1,H2):
1 H=MakeHeap()
2 min[H] = min[H1]
3 verknüpfe die Wurzellisten von H₁, H₂ // O(1) aktuelle Kosten
4 IF (min[H1]=NIL) ODER ((min[H2]≠NIL) AND (min[H2]<min[H1]))
5    min[H] = min[H2]
6 n[H] = n[H1] + n[H2]
7 Vernichte Objekte H₁ und H₂
8 RETURN H
leeren F-Heap H erzeugen
Wurzellisten "aufschneiden"
Wurzellisten vereinigen
Min[H] = min(Min[H₁], Min[H₂])
Kostenanalyse
Potentialdifferenz(Union) = Potential(neuer Heap) - Potential(H₁) - Potential(H₂)
= Φ(H) - Φ(H₁) - Φ(H₂) = 0
keine neuen Elemente
lediglich Knoten aus alten Bäumen zusammengeknüpft
K_Union = O(1)
AK_Union = O(1)
ExtractMin
komplizierteste der Operationen
hier werden Bäume aus Wurzelliste vereinigt
ExtractMin(H):
1 z=min[H]
2 IF z≠NIL
3    FOR alle Kinder x von z DO
4       füge x zur Wurzelliste von H hinzu
5       p[x]=NIL
6     entferne z aus der Wurzelliste von H
7    IF z=rechts[z]
8       min[H]=NIL
9    ELSE
10      min[H]=rechts[z]
11      Consolidate(H)
12   n[H]=n[H]-1
13 RETURN z
Zeile 1: Speichern des Zeigers auf minimalen Knoten
Zeile 2: z=NIL bedeutet, der Heap ist leer, wir sind fertig
Zeile 3-5: Verschieben der Kinder von Z in die Wurzelliste
Zeile 7: Wenn z=rechts[z], dann war z einziger Knoten, wir sind fertig
Zeile 10,11: Min[H] auf einen (nicht zwingend minimalen) Knoten setzen, Konsolidieren
Konsolidieren muss erfolgen, da Min[H] nach Zeilen 1-6 nicht unbedungt auf Minimum zeigt
AK = O(log n)
minimaler Knoten hat maximal D(n) Kinder
K = O(D(n))
D(n) = log n
AK = K + log n für Potential
Consolidate
Ziel: alle Knoten der Wurzelliste haben paarweise verschiedene Knotengrade D
es entsteht eine Struktur, die an Binomialheaps erinnert
ohne Delete, DecreaseKey → fast gleiche Struktur
→ dann und nur dann kann analoge Hähenbeschränkung (h=log n) erfolgen!
bei Verwendung von Delete und DecreaseKey ist diese Aussage falsch
Link
Link(H,y,x):
1 entferne y aus der Wurzelliste von H
2 mach y zu einem Kind von x, inkrementiere grad[x]
3 mark[x]=false
DecreaseKey
DecreaseKey(H,x,k):
1 IF k>key[x]
2   Fehler('neuer Key ist größer als alter!')
3 key[x] = k
4 y=P[x]
5 IF (y≠NIL) UND (key[x] < key[y])
6   Cut(H,x,y)
7   CascadingCut(H,y)
8 IF key[x] < key[min[H]]
9   min[H]=x
Zeile 1-3: sichern, dass neuer Schlüssel kleiner als alter, machen Zuweisung
Zeile 4-5: Prüfen ob x eine Wurzel ist, oder der Vater von x kleiner als x ist
ist dies der Fall, muss Struktur nicht geändert werden
sonst: Min-Heap-Ordnung verletzt
Zeile 6, Cut: x von Baum abschneiden und samt anhängendem Teilbaum in die Wurzelliste einfügen
Zeile 7: wenn y noch keine Marke hat, dann Marke setzen; Wenn Marke schon da, dann auch y in die Wurzelliste nehmen und selbe Prüfung auf Vater von y anwenden. Ggf. bis Wurzel erreicht
Markierungen werden dabei zurückgesetzt
Kosten
Zeit für ändern der Knotenwerte = O(1)
zuzüglich Zeit für Kaskadentrennungen
Annahme: c mal rekursiver Aufruf von CascadingCut
O(1) + c*O(1) = O(c) = tatsächliche Kosten
Potentialänderung ≤ 4-c
H = Heap vor DecreaseKey
jeder Aufruf von CascadingCut - ausser letztem - trennt markierten Knoten und setz dessen Marke auf false
zu t(H) kommt also der verringerte Knoten und c-1 abgeschnittene Knoten, also t(H') = t(H)+c
m(H') ist nach DecreaseKey höchstens m(H)-(c-1)+1 = m(H)-c+2
c-1 mal Markierung gelöscht
evtl. 1 neue Markierung gesetzt
→ Potentialänderung ≤ [(t(H)+c) +2(m(H) - c +2)] - [t(H)+2m(H)] = 4-c
anschaulich: pro CascadinCut werden 2 Einheiten bezahlt
eine für Ausschneiden und löschen der Marke
eine für Erhöhung des Potentials und einfügen in Wurzelliste
→ amortisierte Kosten ≤ O(c) + 4 - c = O(1)
dazu: Potential skalieren
in O(c) verborgene Konstanten müssen dominiert werden
→ AK_DecKey = O(1)
Cut
CUT(H,x,y):
1 entferne x aus der Sohnliste von y, degree[y] = degree[y] - 1
2 füge x in die Wurzelliste von H ein (neben min[H])
3 p[x]=NIL
4 marke[x]=false
CascadingCut
CascadingCut(H,y):
1 z=p[y]
2 IF z≠NIL
3   IF mark[y] = false
4     mark[y]=true
5   ELSE
      Cut(H,y,z)
6    CascadingCut(H,z)
Wenn der Vater von y noch keinen Sohn verloren hat, wird seine Markierung auf true gesetzt
Wenn der Vater von y schon einen Sohn verloren hat, dann schneide von ihm auch y ab und setze es in die Wurzelliste
Kosten O(1)
Delete
Delete(H,x):
1 DecreaseKey(H,x,-∞)
2 ExtractMin(H)
AK_Delete=AK_DecreaseKey+AK_ExtractMin
wegen D(n) = O(log n) → AK_Delete=O(log n)
interessant: man kann F-Heaps auch bei geringer Verwendung von DecreaseKey und Delete verwenden!
F-Heaps sind Strukturen der theoretischen Informatik
geben Aufschluss über optimale mögliche Komplexität
die konkrete Implementation ist dafür schwierig

Verwaltung disjunkter Mengen
Situationsbeispiele
Graphen G=(V,E)
V = Knotenmenge
E = Kanten
Knoten p und q durch Weg verbunden ↔ Es gibt Kanten, die die Knoten verbinden
p ~ q ↔ Es gibt in G einen Weg, der p mit q verbindet
es gilt
p ~ p
q ~ q
p ~ q ↔ q ~ p
→ Äquivalenzrelation
→ Äquivalenzklassen
bilden eine Zerlegung von V

nichtleer, disjunkt, vollständig
Zerlegungen - Äquivalenzrelation
gesucht: Zerlegung, die zusammenhängenden Komponenten entspricht
Definition: Zerlegungsklassen - Zusammenhangskomponenten
da die Zusammenhangskomponenten eine Äquivalenzrelation auf der Knotenmenge darstellen gilt: jedes Element ist ein kanonisches Element seiner Zerlegungsklasse im Bezug auf die Relation ~.
kanonisch = repräsentativ für seine Klasse
eine Output-Menge wird durch ihr kanonisches Element beschrieben
gelb: mögliche kanonische Elemente
hier: 3 Zusammenhangskomponenten
mögliche Aufgaben in der Informatik
Input: p є V
Output: Zusammenhangskomponente, in der p ist
Input p,q є V mit p≠q
Output: Sind p und q in der gleichen Zusammenhangskomponente?
führt zu Programmen
SameComponent
ConnectedComponents
→ wir brauchen Datenstrukturen zur Verwaltung disjunkter Mengen
Union-Find
ADT = Menge der Operationen
MakeSet(x)
x: Element
erstelt Einermenge
keine leere Struktur!
Union(x,y)
Input x und y
Output = kanonisches Element der Vereinigung von x und y
Find(x)
findet zu einem gegebenen Input x das kanonische Element der Menge, die x enthält
ConnectedComponents
ConnectedComponents(G=(V,E))
1 FOR ALL vєV DO
     MakeSet(v)
2 FOR ALL (u,v) є E DO // für alle Kanten
3   IF Find(u)≠Find(v)
4      Union(Find(u),Find(v))
SameComponent
SameComponent(u,v):
RETURN Find(u)=Find(v)
Rechenzeit? hängt von Speicherung im Computer ab
→ Datenstruktur
1. Ansatz
Array für
gelb: kanonisches Element
zeigt auf sich selbst
x    a b c d e f g h
p(x) a a a a f f f h
Repräsentation als Array
MakeSet wäre O(1)
aber Union wäre O(n)
umsetzen aller Zeiger
2. Ansatz
Listen
Find - O(1)
Union - Verknüpfen der Listen in O(n)
gewichtetes Union
Länge der Listen werden verwaltet
bei Union wird die kürzere Liste an die Längere angehängt
→ möglichst wenig Zeiger umsetzen
Satz: eine beliebige Folge von m MakeSet, Find und Unions mit n MakeSet-Aufrufen kostet O(m+n log n)
für gewichtetes Union (sonst Θ(n²))
m Operationen gesamt
n MakeSets ( = Anzahl der Elemente)
n ≤ m
besser: Disjoint-Set-Forests
Wälder für disjunnkte Mengen
jedes Element zeigt nur auf seinen Vater
Objekte in linearem Array
zu verwalten:
kanonisches Element c: P(c)=c
MakeSet(x)
1 p[x]=x
2 size[x]=1
O(1)
size = Anzahl der Knoten
Union(Find(x),Find(y)):
bild
worst case
1. intelligente Vereinigung (nach Größe)
Union(e,f):
1 IF size[e]<size[f]
2    vertausche(e ↔ f)
3 p[f]=e
4 size[e]=size[e]+size[f]
O(1)
Größenlemma
gilt für Vereinigung nach Größe
Ein Baum der Höhe h hat ≥ 2^h Knoten
Beweis
Induktionsanfang: T ist nur Root → Höhe = 0, 2⁰ = 1 Knoten
Induktionsschritt: T = T₁ U T₂
Induktionsvoraussetzung: size(T₁) ≥ 2^h1, size(T₂) ≥ 2^h2, oBdA. sei size(T₁) ≥ size(T₂)
→ Höhe(T) =
max(h₁, h₂) falls h₁≠h_{2size[T] = size[T₁] + size[T₂] ≥ 2^h1 + 2^h2 ≥ 2^h
→Behauptung folgt}
max(h₁, h₂)+1 falls h₁ = h_{2 h= h₂ + 1
size[T] = size[T₁] + size[T₂] ≥ 2^h1 + 2^h2 ≥ 2size[T₂] ≥ 2*2^h2 = 2^h2+1 = 2^h}
→ Folgerung: Find kostet "nur" O(log n)
→ Heuristiken:
2. intelligente Vereinigung (nach Rang)
UNION(x,y):
1 Link(Find(x),Find(y))
Link(x,y):
1 IF rank[x]>rank[y]
2   p[y]=x
3 ELSE
4   p[x]=y
5   IF rank[x]=rank[y]
6      rank[y]=rank[y]+1
Lemma: Der Rang von x ist für alle Knoten eine obere Schranke für die Höhe von x
Rank wird bei MakeSet auf 0 gesetzt
bei einzelnem Knoten gilt also rank[x] = höhe[x]
rank wird bei Union nur erhöht, wenn beide Bäume gleichen Rang haben
3. intelligentes Find
O(log n)
erster Ansatz
FIND(x):
1 WHILE p[x]≠x
2    x=p[x]
3 RETURN x
schlechter Ansatz
Θ(m log n)
n Anzahl der Elemente
m Gesamtzahl der Operationen
wenn Union nach rank (m>n)
besser
Find(x):
1 y=x
2 WHILE p[y]≠y
3    y=p[y]   // y ist jetzt wurzel von x
4 z=x
5 WHILE p[z]≠y
6    t=z
7    z=p[z]
8    p[t]=y
9 RETURN y
2. Whileschleife übernimmt Pfadkompression
rekursiv
Find(x):
1 IF x≠p[x]
2 p[x]=Find(p[x])
3 RETURN p[x]
2-Schritt-Verfahren
läuft einmal bis zur Wurzel und zurück zu x
beim Rücksprung werden die Zeiger aktualisiert
neue Attribute
höhe = maximale Länge des Weges von einem Blatt zur Wurzel
rank = Rang eines Knotens
MakeSet(x)
1 p[x]=x
2 size[x]=1 O(1)
Analyse
sei
k ≥ 0 sei die Ebene
j ≥ 1
A_k( j ) =
j+1, falls k=0
A_k-1^(j+1)( j ) falls k ≥ 1
also iterierte Anwendung
f(x) = x+1 → f⁽²⁾(x) = f(f(x)) → f⁽³⁾(x) = f(f⁽²⁾(x)) → f⁽ⁱ⁾(x) = f(f^(i-1)(x))
sowohl in k als auch in j streng monoton steigend
speziell
A_k-1⁽⁰⁾( j) = j
A_k-1⁽ⁱ⁾( j) = A_k-1(A_k-1^(i-1)(j) ) für i ≥ 1
für j ≥ 1 gilt
A₁( j) = 2j + 1
A₂( j) = 2ⁱ⁺¹(j + 1) - 1
es folgt:
A₀(1) = 2
A₁(1) = 3
A₂(1) = 7
A₃(1) = 2047
A₄(1) >> A₂(2047) > 2²⁰⁴⁸ >> 10^{80entspricht deer geschätzen Anzahl der Atome im beobachtbaren Universum}
A_k(x) ist die Ackermann-Funktion
α(n) = min { k | A_k(1) ≥ n}
a(n) =
0, falls 0 ≤ n ≤ 2
1, falls n=3
2, falls 4 ≤ n ≤ 7
3, falls 8 ≤ n ≤ 2047
4, falls 2048 ≤ n ≤ A₄(1)
Inverse der Ackermannfunktion
man kann für praktische Zwecke α(n) ≤ 4 annehmen
es gilt:
n = Anzahl der Elemente in der Struktur = Anzahl der zu Grunde liegenden MakeSets
jeder Knoten hat einen Rang ≤ n-1
wenn man einen Pfad vom Knoten zum Root verfolgt,<br>ist der Rang streng monoton steigend.
rank[x] ≤ rank[p[x]]
Lemma 0
Am Ergebnis der Untersuchung ändert sich nichts, wenn wir statt der UNIONs die LINKs zählen
Potentialfunktion Φ_q = ∑_{Knoten x} Ψ_q(x)
Φ_q = Potential des Waldes nach der q-ten Operation
Φ₀ = 0 (Wald ist leer)
Φ_q ≥ 0
Potentialfunktion Ψ_q(x) := Potential nach Ausführung der q-ten Operation
ordnet jedem Knoten x aus dem Wald der disjunkten Mengen ein Potential Ψ_q(x) zu
Ψ_q(x) =
α(n) * rank[x], falls x nach der q-ten Operation eine Wurzel ist oder den Rang 0 hat
(α(n) - ebene(x)) * rang[x] - iter(x), sonst
sei ebene[x] = max{k : rang[p[x]] ≥ A_k(rang[x])}
Das heiißt, ebene(x) ist die höchste Ebene k, für die A_k,
angewendet auf den Rang von x nicht größer als der Rang des Vaters von x ist.
es gilt: 0 ≤ ebene(x) ≤ α(n)
sei iter(x) = max{i : rang[p[x]] ≥ A⁽ⁱ⁾_ebene(x)(rang[x])}
iter(x) gibt an, wie oft wir A_ebene[x] maximal auf den Ausgangsknoten
iterativ anwenden können, bevor wir einen größeren Wert als den
Rang des Vaters von x erhalten
Lemma 1
die amortisierten Kosten von MakeSet sind O(1)
→ Rang ändert sich nicht
→ iter ändert sich nicht
→ ebene ändert sich nicht
Lemma 2
die amortisierten Kosten von Link(x,y) sind O(α(n))
Bemerkung: aktuelle Kosten hier O(1)
→ wie ändert sich das Potential? q-te Operation, welche Knoten erfahren eine Potential-Änderung?
→ x, y, Söhne(y)
x: Ψ_q(x) → Ψ_q-1(x) = α(n) * Rang[x] für Rang[x]≠0 → Ψ_q(x) = (α(n)-ebene(x)) * rang[x] - iter[x]
y: Ψ_q(y) → Ψ_q-1(y) + α(n) = (Ψ_q-1(y)+1) * α(n)
→ Gesamtänderung ist gleich α(n)
Lemma 3
die amortisierten Kosten von Find(x) sind O(α(n))
→ alle Operationen werden unterstützt
Satz von Tarjan: Θ(m * α(n)) ist die Zeit
von m Operationen mit n MakeSets
Beweisidee: amortisierte Analyse über die Potentialfunktion
amortisierte Kosten = aktuelle Kosten + Potentialdifferenz
wenn überhaupt, dann kann eine Potentialdifferenz nur bei Link auftauchen
es bleibt Untersuchung der Potentialdifferenz für x,y
x war Wurzel
Rang[x] = 0
bleibt y
1. Fall: Rang(y) bleibt
2. Fall: Rang(y) := Rang(y) +1
Ψ_q-1(y) = α(n) * Rang(y)
Ψ_q(y) = (Rang(y) + 1) * α(n) ist die Rang-Erhöhung

= Rang[y] * α(n) + α(n)
Algorithmus von Kruskal
Anwendung der Union-Find-Struktur
Input:
ungerichteter Graph
enthält Kreise
E Kanten
V Knoten
gesuchter Output:
Teilgraph
soll alle Knoten enthalten
kreislos
Summe der Zahlen an den Kanten soll minimal werden
sogenannter minimal spanning tree - mst
Algorithmus
Kruskal(G=(V,E),W):
1 E^* = Ø
2 K = Ø // Kollektion: eine Menge von Mengen
3 Bilde Prioritätswarteschlange Q der Kanten von E bezüglich des Gewichtes. W
4 für jedes vєV
     MakeSet(v)
5 K= {{v}|vєV}
6 WHILE K enthält mehr als eine Menge DO
7    (v,w)=MIN(Q)
8    ExtractMin(Q)
9    IF FIND(v) ≠ FIND(w)
10     E^* = E^* U {(v,w)}
11     UNION(v,w)
12 RETURN E^*
Laufzeit: O(|E| log |V|)
ausgehend von Vereinigung nach Rang und Pfadverkürzung bei Find
Zeile 1,2: O(1)
Zeile 3: O(E log E)
Zeile 4,6-11: O(E) x Find, O(E) x Union, |V| x MakeSet → O(V + E) α(V)

wegen |E| ≥ |V| -1 (Graph war zusammenhängend) → Operationen für die
disjunkten Mengen kosten O(E α(V)). mit α(|V|) = O(log |V|) = O(log |E|) ergibt
sich: O(E log V)
verwendet oft Min, ExtrectMin
es bietet sich an einen Prority Queue zu verwenden
ausserdem Union, Find, MakeSet
Union-Find
angewendet auf Beispiel
Schritt 1

K
{a},{b},{c},{d},{e},{f}

nächste Kante
(b,d)

Hinzunahme
Ja

Schritt 2

K
{a},{b,d},{c},{e},{f}

nächste Kante
(a,c)

Hinzunahme
Ja

Schritt 3

K
{a,c},{b,d},{e},{f}

nächste Kante
(e,d)

Hinzunahme
Ja

Schritt 4

K
{a,c},{b,d,e},{f}

nächste Kante
(c,e)

Hinzunahme
Ja

Schritt 5

K
{b,d,e,a,c},{f}

nächste Kante
(a,d)

Hinzunahme
Nein

Schritt 6

K
{b,d,e,a,c},{f}

nächste Kante
(a,d)
(c,d)
(a,b)
(b,f)

Hinzunahme
Nein
Nein
Nein
Ja

Ergebnis

Hashing
Streuspeicherverfahren
zugehöriger ADT = Dictionary = {Insert, Delete, Search}
mit Delete: Open Hashing
zu Grunde liegendes Problem
Voraussetzung
sei U ein Universum
sei K eine Menge von Schlüsseln aus dem Universum
|K| << |U|
dann lohnt sich Hashing
Beispiel: Telefonbuch
Universum = Wörter über dem lateinischen Alphabet
Schlüssel: "relativ kleine" Menge von Wörtern aus dem Universum
es kommen nicht alle möglichen Wörter vor
andere kommen doppelt vor
Positionen von Einträgen werden durch Hashfunktion h(k) berechnet
Berechnung der Hasfunktion in O(1)
worst case: Alle Keys "wollen" auf gleichen Platz
m-1 leere Listen
1 Liste der Länge n
nicht gut
Lösung: Verwendung von Hash-Funktionen, die Annahme des einfachen uniformen Hashings erfüllen
heißt: Wahrscheinlichkeit dafür das ein Element einen bestimmten Platz bekommt ist für alle Plätze gleich
Alle Hashplätze sind gleich wahrscheinlich

Wahl von Hasfunktionen
Größe m der Tabelle wichtig
muss in O(1) ausführbar sein
Divisionsmethode
h(k) = k mod m
m≠2^{iBeispiel: m=2² = 4
k₁ = 15 = 01111_b
k₂ = 31 = 11111_b
k₃ = 06 = 00110_b
h(k₁) = 3 = 11_b
h(k₂) = 3 = 11_b
h(k₃) = 2 = 10_b
→ berechnete Position nur von letzten drei Bits abhängig!}
→ m sollte eine Primzahl sein
nicht zu dicht an einer 2er Potenz
z.B. 701
Multiplikationsmethode
Wähle 0 < A < 1
Beispiel
√5 - 1
2
= 0.6180339
h(k) = _└m (k A mod 1)_┘ = _└m (k A - _└k A_┘)_┘
→ hier ist m = 2^p sinvoll!
Belegungsfaktor α = n/m
n = Anzahl der Schlüsselwerte in der Tabelle
Chaining
wichtig: Annahme des einfachen uniformen Hashings
für mehrfach verwendete Listenplätze wird Überlaufliste gebildet
Einfügen neuer Elemente i.d.R. am Ende der Überlaufliste
Grund: vorher Durchsuchen der Liste
Prüfen ob einzufügendes Element schon vorhanden
beim Entfernen werden Elemente wirklich gelöscht, nicht nur Zeiger auf diese
Elemente hinter gelöschtem müssen erhalten bleiben!
für erfolgreiche und erfolglose Suche
erfolglos: Liste durchlaufen, Element nicht gefunden
erfolgreich: Element gefunden → Stop!

erwartete Länge der Listen = α
Satz: Zeit für Search ist Θ(1+ α)
unter Annahme des einfachen uniformen Hashings

Realisierungen
direkte Verkettung
separate Verkettung
Überlauflisten nicht mit in Hashtabelle
open hashing
Suche nach (freien) Plätzen in der Liste
Sondierungsfolge (probing sequence)
h: U x {0, ... , m-1} → {0, ... , m-1} ist eine Abbildung
h(k,i) є {0,...,m-1}
i = 0,1,2,3,...
es gibt m! Sondierungsfolgen
Annahme des uniformen Hashings: alle Sondierungsfolgen haben die gleiche Wahrscheinlichkeit
Theorem: unter dieser Voraussetzung gilt für die
erfolglose Suche, dass die erwartete Zeit ≤ 1/(1-α) ist
Beweis
sei X die Anzahl der Sondierungen
A_i = es gibt eine i-te Probe und der sondierte Platz ist besetzt.
P(X ≥ i) = P(A₁ ∩ A₂ ∩ ... ∩ A_i-1) = P(A₁)*P(A₂|A₁) * P(A₃|A₂ ∩ A₁) ... W(A_i-1|A₁ ∩ ... ∩ A_i-2)
P(A₁) = n/m → P(A_j|A₁ ∩ ... ∩ A_j-1)

n-j+1
m-j+1
=

n-(j-1)
m-(j-1)
P(A₁ ∩ ... ∩ A_i) = n/m * (n-1)/(m-1) * (n-2)/(m-2) * .... * (n-i+1)/(m-i+2) ≤ (n/m)^i-1= α^i-1
E(X) = ∑_i^∞₌₁ P(X ≥ i)
E(X) ≤ ∑_i^∞₌₁ α^i-1 = ∑_i^∞₌₀ αⁱ = 1/(1-α)
lineares Sondieren
immer x Plätze weiter schauen
h_i(k) = h(k) + i*x
jede Folge hängt nur von Anfangswert ab
m mögliche Anfangswerte → nur m Sondierungsfolgen
m << m! → schlecht!
primary clustering
quadratisches Sondieren
h_i(k) = (h(k) + c₁i + c₂i² + c₃) mod m
secondary clustering
wieder nur m (statt m!) Folgen
doppeltes Hashing
m² Folgen
zwei Hasfunktionen h₁, h₂
h_i(k) = (h1(k) + i*h2(k)) mod m
Beispiel
m=13
h1(k) = k mod 13
h2 (k) = 1+k mod 11
Folge: 79,69,96,72,50,14
generierte Schlüsselwerte:

Folge der Schlüssel k 79 69 96 72 50 14

h₀(k) 1 4 5 7 11 1

h₁(k) - - - - - 5

h₂(k) - - - - - 9

universal hashing
hash Verfahren mit "Robin Hood"-Effekt
es gibt keine "bösen" Inputfolgen
jede beliebige Inputfolge hat die gleiche Chance
Hashfunktion nicht festgelegt, wird aus Pool H von Hashfunktionen zufällig gewählt
für einzelne Funktion kann es zu Kollision kommen
nicht für alle!
endliche Menge von Hasfunktionen universell → für x und y є U:
Anteil der zu Kollision führenden Funktionen h є H mit h(x) = h(y) ≤ 1/m
x,y sind zwei beliebige Elemente aus dem Universum U
H: Menge der Hasfunktionen
m: Größe der Hastabelle
P_H(h(x) == h(y)) ≤ 1/m
Aufwand zum Einfügen eines Schlüssels
δ(x,y,h) =
1 falls h(x) == h(y) für x≠y
0 sonst
Erweiterung auf Mengen
von Schlüsseln: δ(x,S,h) = ∑_sєS δ(x,s,h)
von Hashfunktionen δ(x,y,H) = ∑_hєH δ(x,y,h)
Folgerung: H ist universell wenn gilt: δ(x,y,H) ≤ |H|/m
x,y є U
E(Aufwand zum Einfügen eines Schlüssels x) = E(δ(x,S,h)) =

∑_hєH δ(x,S,h)
|H|

=

1/|H| ∑_hєH∑_yєSδ(x,y,h) = 1/|H| ∑_yєS∑_hєHδ(x,y,h)

=

1/|H| ∑_yєS δ(x,y,H) ≤ 1/|H| ∑_yєS |H|/m = 1/m ∑_yєS1 = |S|/m
für zufällig gewähltes h aus einer universellen Menge von Hashfunktionen
Kosten des Einfügens ~ Anzahl der Kollisionen beim Einfügen von x
Annahme: in Hashtabelle alle Schlüssel der Menge S gespeichert
→Aufwand zum Einfügen eines weiteren Schlüssels x =
Anzahl der Elemente aus S, mit denen x kollidiert

parallele Algorithmen
bisher betrachtet
seriella Algorithmen
anerkanntes Modell
RAM - random access machine - von Neumann-Architektur
Beurteilung der Algorithmen a: Rechenzeit T_a(n)
mehrere Prozessoren
grobkörnig: wenige leistungsfähige
feinkörnig: viele, weniger leistungsstarke
kein allgemein anerkanntes einziges Modell
2 Hauptmodelle
Netzwerkmodell / Feldrechner
Kommunikation zwischen und nur über einen weiteren Prozessor möglich!

Dimensionen 0, 1, 2, 3
jede höhere Dimension setzt siich aus mehreren niedrigeren zusammen
Hypercube
Kommunikation zwischen und nur über zwei weitere Prozessoren möglich!
dicht kommunizierende Prozessoren: nur eine Position muss geändert werden z.B. 001 und 011, 110 und 111
shared memory modell
statt T_a(n): C_a(n) = T_a(n) * P_a(n)
P = Anzahl der Prozessoren
C = Kosten
Satz: Die Kosten können das serielle Minimum nicht überbieten
Beweis: Simuliere den parallelen Algorithmus seriell
Idee: Probleme durch parallele Algorithmen schneller lösen
z.B. Sortieren in O(log n)
dazu: mehr Prozessoren nötig
Beispiel: Sortieren im Netzwerkmodell nach Batcher
einzelner Prozessor mit 2 Eingaben

Sort über Merge
2 x 2 merging-Netzwerk

allgemein
Time: O(log² n)
Batcher-Theorem: die n x n-merging networks sortieren mit der Binärbaummethode (merge-Sort) korrekt ("Sie mischen korrekt")
1. Beweisschritt
Betrachte Teilfolge (d₁, d₂,...,d_i+1) für ein i
es sollen k Elemente dieser Teilfolge zu (a₁, a₃, a₅, a₇, ...) gehören
→ (i+1-k) gehören zu (b₁, b₃, b₅, b₇, ...)
→ a₁ a₂ a₃ a₄ a₅ → (2k -1) der (a₁, a₂, a₃,...) sind ≤ d_i+1
analog (2i+1-2k) der (b₁, b₂, b₃, ...) sind ≤ d_i+1
wegen (2k-1)+(2i+1-2k) = 2i gilt: d_i+1 ≥ c_2i
analog folgt: e_i ≥ c_2i
2. Beweisschritt
seien k Elemente von c₁, c₂, c₃,...., c_2i+1 auch Elemente von (a₁, a₂, a₃, ....)
analog (2i+1-k) Elemente von (b₁, b₂, b₃, ....)
es folgt: c_2i+1 ist ≥ k Elementen von (a₁ a₂ a₃....)
d.h. ^k/₂ Elemente von (a₁ a₃ a₅ a₇...) (bzw. (k+1)/₂ falls k ungerade)
es folgt: c_2i+1 ist ≥ 2i+1-k Elementen von (b₁ b₂ b₃....)
es folgt: c_2i+1 ist ≥ 2i+1-k Elementen von (b₁ b₂ b₃....)
d.h. i+1-^k/₂ Elemente von (b₁ b₃ b₅ b₇...) (bzw. (2i+1-k)/₂ falls k ungerade)
→ ^k/₂+i+1-^k/₂ = i+1,

^(k+1)/₂+^(2i+1-k)/₂ = ^{(2i + 2)}/₂ = i+1
c_2i+1 ≥ e_i ≥ c_2i
analog: c_2i+1 ≥ e_i ≥ c_2i
→c₁ ≤ c₂ ≤ c₃ ≤ .... ≤ c_2i ≤ c_2i+1, wobei es keine Werte zwischen c_2i und c_2i+1 gibt,
→ c_2i+1 = max(e_i, d_i+1), c_2i = min(e_i, d_i+1)

Programme für Darstellung
Latex
Flash
Script
CodeGen

Folge der Schlüssel k	79	69	96	72	50	14
h₀(k)	1	4	5	7	11	1
h₁(k)	-	-	-	-	-	5
h₂(k)	-	-	-	-	-	9