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