Einleitung

Beispiel: Sortieren (Spezifikation 1)

Beispiel:

Beispiel: Sortieren (Implementierung 1)

Beispiel: Sortieren (Implementierung 2)

Beispiel Sortieren: Einordnung

Grundbegriffe: Spezifikation, Algorithmus

Eine Spezifikation ist eine Relation \(S\subseteq E\times A\).

Ein Algorithmus ist

Der Algorithmus heißt

Der abstrakte Datentyp Menge (Signatur)

Der abstrakte Datentyp Menge (Axiome)

für alle \(\verb|e,f|\in E,\verb|m|\in M\):

  1. null(empty) = True;

  2. null(insert(e,m)) = False;

  3. contains(e,empty) = False;

  4. contains(e,insert(e,m)) = True;

  5. e\(\neq\)f \(\Rightarrow\) contains(e,insert(f,m)) = contains(e,m);

Implementierungen von Mengen

Grundbegriff: Datenstruktur

Inhalt und Ziel der Vorlesung

Aufgabe: Sortieren (Spezifikation 2)

Implementierungen von Sortierverfahren

Aufgabe: kürzeste Wege

Aufgabe: Rundreise

Einordnung dieser VL in das Studium

Auswahl von LV zu Programmierung und Algorithmen:

Organisatorisches

Zeitplan für Übungsserien

Grundsätzlich:

zur Initialisierung: in KW 14 (\(=\) aktuelle Woche \(=\) Woche 0)

Bewertung von Übungsserien

Literatur

Alternative Quellen

Übung KW14

Ablauf der Übung

Übungsserie 0 (Diskussion in KW14)

Aufgabe 0.0 (Leseübung)

Aufgabe 0.1 (Mengen)

Aufgabe 0.2 (Sortieren)

Für \(a=[3,1,4,1,5,9]\):

Aufgabe 0.3 (kürzestes Wege)

Wir betrachten den Graphen \(G_n\) auf der Knotenmenge \(V_n=\{0,1,\ldots,n\}^2\) mit den Kanten

(jeweils für alle \(x,y\), für die das angegebene Paar tatsächlich in \(V_n^2\) liegt)

Aufgabe 0.4 (Sortieren mit compare-exchange)

Aufgabe 0.5(A) (autotool)

Übungsserie 1 (Diskussion in KW15)

Aufgabe 1.0 (Leseübung)

Aufgabe 1.1 (Mengen)

Aufgabe 1.2 (Sortieren mit compare-exchange)

Aufgabe 1.3 (kürzeste Wege)

Wir betrachten den Graphen \(G_n\) auf der Knotenmenge \(V_n=\{1,\ldots,n\}^2\) und der Kantenmenge \(E_n=\{((x_1,x_2),(y_1,y_2)) \mid (x_1-y_1)^2+(x_2-y_2)^2=5\}\), die alle Gewicht \(1\) haben.

Komplexität von Algorithmen und Problemem

Plan

Literatur: vgl. WW 2.3/2.4, OW S. 4/5

Was bedeutet Zeit?

Coverage mit gcov

https://gcc.gnu.org/onlinedocs/gcc/Gcov.html

        5:    8:  for (int i = 0; i<n; i++) {
        4:    9:    int k = i;
       10:   10:    for (int j = i+1; j<n; j++) 
        6:   11:      if (b[j]<b[k]) k = j;    
        4:   12:    swap(b[i],b[k]);

Vollständiger Quelltext: https://gitlab.imn.htwk-leipzig.de/waldmann/ad-ss17

Zeitkomplexität von Algorithmen

Zeitkomplexität von Problemen

Komplexität von Programmen

Komplexität v. Progr. (Verzweigung)

Komplexität v. Progr. (Schleifen)

Asymptotischer Vergleich von Funktionen

Wiederholung

unterschiedliche Komplexitätsfunktionen

und ihre Auswirkungen bei Änderung der Eingabegröße:

das ist nützlich, aber nicht alle Funktionen sind so einfach

Motivation: Abstraktion von…

Definition, Beispiele

Eigenschaften

die Relation \(\{(f,g)\mid f\in O(g)\}\):

Aber wenn es nur um Polynome geht…

…wozu dann der Aufwand? Polynome erkennt man leicht!

Nein. Welche der folgenden Funktionen sind (beschränkt durch) Polynome? Von welchem Grad?

Solche Funktionen kommen als Kostenfunktionen von Algorithmen vor und müssen richtig eingeordnet werden.

Abgekürzte Notation für Funktionen

Abgekürzte Notation f. Mengen v. Funktionen

Eine Vergleichsmethode

Weitere Notationen

(wie immer: alle Funktionen aus \({\mathbb{N}}\to{\mathbb{N}}\))

Asympt. Vergleich von Standardfunktionen

alle Beweise mittels Limes-Kriterium

Spezielle Funktionen

Anwendung

Eine klassische Übungsaufgabe aus [CLR]:

Übungsserie 2 (für KW 16)

Aufgabe 2.1

for x = 1 to n
  for y = 1 to n
    if not (x = y)
      for z = 1 to n
        if not (x = z) && not (y = z) 
          e

Aufgabe 2.2

Die Binärdarstellungen aller Zahlen von \(0\) bis \(n\) werden nebeneinandergeschrieben.

Als Darstellung der 0 benutzen wir dabei die leere Ziffernfolge.

Die Gesamt-Anzahl der Vorkommen der 1 nennen wir \(B(n)\).

Beispiel: von \(0\) bis \(3\): \([[],[1],[1,0],[1,1]]\), \(B(3)=4\).

Die Binärdarstellungen von \(0\) bis \(n-1\) werden durch führende Nullen ergänzt, so daß jede so lang wie die Darstellung von \(n\) wird.

Die Gesamt-Anzahl der dabei hinzugefügten 0 nennen wir \(F(n)\).

Beispiel: \([[\underline{0},\underline{0}],[\underline{0},1],[1,0],[1,1]]\), \(F(3)=3\).

Aufgabe 2.2 (Musterlösung einer Teilaufgabe)

Aufgabe 2.3

(4 P)

Welche \(O, \Theta\)-Relationen gelten zwischen

\(f_1(n)=n-\sqrt n, ~ f_2(n)= \sqrt{n}^{\sqrt{n}},~ f_3(n)=n\)

Aufgabe 2.4

Einfache Algorithmen auf Zahlen und Feldern

Übersicht

Der größte gemeinsame Teiler (gcd)

Algorithmus von Euklid (Variante 1)

Eingabe: nat x, nat y;  Ausgabe: gcd(x,y)
// x = X, y = Y (Bezeichung für Eingabe)
while true  // I: gcd(x,y) = gcd(X,Y)
  if x = 0 then return y
  if y = 0 then return x
  if x = y then return x
  if x < y then y := y - x else x := x - y

Entwurf und Analyse von Schleifen

(David Gries: The Science of Programming, Springer, 1981; Kapitel 11)

Multiplizieren durch Verdoppeln

Algorithmus von Euklid (Variante 2)

Laufzeit von Euklid (Variante 2)

Die Fibonacci-Zahlenfolge

Binäre Suche in geordnetem Feld

Spezifikation:

Eingabe: a[1..n] schwach monoton steigend, x
Ausgabe: falls exists i: a[i] = x,
  dann ein i mit a[i] = x, sonst NEIN

Implementierung (divide and conquer)

nat l := ... ; nat r := ...
while ... // Schranke: log (r - l)
  // I: a[1 .. l-1] < x , x < a[r+1 .. n]
  nat m = div (l+r,2)
  if a[m] = x then return m
  else if a[m] < x then ...
  else ...

Laufzeit: \(\Theta (\log n)\).

Binäre Suche in geordnetem Feld (Var. 2)

Spezifikation (beachte: Grenzen sind \(l\) und \(r\))

Implementierung (mit Rekursion statt Schleife):

search (a [l .. r], x) = 
  if  l > r  then return NEIN
  else nat m = div (l+r,2);
       if  a[m] = x  then return m
       else if  a[m] < x  then search(a[m+1 .. r],x)
       else search(a[l .. m-1],x)

Korrektheit: \(x\in a[l\dots r] \iff\) \(a\) nicht leer und

\( (x<a[m]\wedge x\in a[l\dots m-1])\)

\( \vee x=a[m] \vee (x>a[m]\wedge x\in a[m+1\dots r])\)

Binäre Suche (Var. 2) in Java

boolean search (List<Integer> a, int x) {
 if (a.isEmpty()) return false; else {
  int m = (a.size() - 1) / 2;
  if (a.get(m) == x) return true; 
  else if (a.get(m) < x) 
   return search(a.subList( 0,        m), x);
  else 
   return search(a.subList(m+1,a.size()), x); }

Bemerkung zum Programmierstil

Die Flagge färben (Vorbereitung: 2 Farben)

E.W. Dijkstra: A Discipline of Programming (Kap. 14), Prentice-Hall, 1976

Ansatz (\(b\) wird in \(a\) konstruiert)

while ( ... ) // Schranke: r - l
  // I: a[1..l-1] = B, a[r+1..n] = R
       if a[l] = B then ...
  else if a[r] = R then ...
  else { a[l] <-> a[r]; ... }

Die Flagge färben (wirklich: 3 Farben)

Ansatz:

l = ... ; m = ... ; r = ...
// I: a[1..l-1]=B, a[l..m-1]=W, a[r+1..n]=R
// Schranke?
while ... 
  if      a[m]=B { a[m] <-> a[...]; ... }
  else if a[m]=R { a[m] <-> a[...]; ... }
  else           {                  ... }

Hinweis zu Übungsaufgabe 3.3

Übungsserie 3 (für KW 17)

Aufgabe 3.1 (Euklid, Variante 1)

Aufgabe 3.2 (Euklid, Variante 3)

Die GNU Multiprecision-Bibliothek (T. Granlund et al., FSF, 1991–2016) https://gmplib.org/manual/Binary-GCD.html enthält diesen gcd-Algorithmus, der (wie Variante 1, im Gegensatz zu Variante 2) keine Divisionen benutzt (Division durch 2 ist binär leicht realisierbar).

while ...
  (a,b) := (abs(a-b), min(a,b)) // 1
  if even(a) then a := div(a,2) // 2
  if even(b) then b := div(b,2) // 3

Die Invariante soll auch hier sein: \(I: \gcd(a,b)=\gcd(A,B)\) (der gcd der aktuellen \(a,b\) ist der gcd der Eingabe).

Aufgabe 3.3 (Suche in mehreren Feldern)

Spezifikation:

Eingabe: Felder \(a[1..s], b[1..t]\), jedes ist schwach monoton steigend.

Ausgabe: ein Paar \((i,j)\) mit \(a[i]=b[j]\), falls das existiert, sonst NEIN.

Aufgabe 3.4 (Suche im Rechteck)

Spezifikation:

Eingabe: ein Feld \(a[1..n,1..n]\), eine Zahl \(x\),

wobei jede Zeile und jede Spalte von \(a\) schwach monoton steigen

Ausgabe: ein Paar \((i,j)\) mit \(a[i,j]=x\), falls das existiert, sonst NEIN.

Sortieren in Feldern und Listen

Übersicht

Entscheidungsbäume

Höhe und Breite von Binärbäumen

Untere Schranke für Sortierverfahren

Nebenrechnung: Wachstum von \(\log n!\)

Zählen von Inversionen

Zählen von Inversionen (Beweis)

Bijektion zwischen \({\operatorname{\textsf{Inv}}}(a)\setminus\{(k,k+1)\}\) und \({\operatorname{\textsf{Inv}}}(b)\):

durch vollst. Fallunterscheidung für \((i,j)\in{\operatorname{\textsf{Inv}}}(a)\):

Inversionen und einfache Sortierverfahren

Inversionen und Laufzeit

Sortieren durch Einfügen

Shell-Sort: Vorbereitung

Shell-Sort: Vorbereitung—Beweis

Shell-Sort: Idee

Shell-Sort: Hilfssatz 1

Shell-Sort: Hilfssatz 2

Shell-Sort: eine geeignete Differenzenfolge

Rechnen mit Folgen (Listen)

Das Zusammenfügen von monotonen Folgen

Merge: Korrektheit (1)

zu zeigen: \({\operatorname{\textsf{MM}}}(a)\cup{\operatorname{\textsf{MM}}}(b)={\operatorname{\textsf{MM}}}({\operatorname{\textsf{merge}}}(a,b))\)

Beweis durch Induktion nach \(|a|+|b|\)

Merge: Korrektheit (2)

Def: \(a\) ist monoton \(\iff\) \({\operatorname{\textsf{null}}}(a)\) oder \(a={\operatorname{\textsf{cons}}}(x,a')\) und \(\forall z\in{\operatorname{\textsf{MM}}}(a'): x\le z\) und \(a'\) ist monoton.

Zu zeigen: wenn \(a\) monoton und \(b\) monoton, dann \({\operatorname{\textsf{merge}}}(a,b)\) monoton.

Beweis durch Induktion nach \(|a|+|b|\)

Sortieren durch Zusammenfügen (Merge-S.)

Merge-Sort: Korrektheit (1)

zu zeigen: \({\operatorname{\textsf{MM}}}(a)={\operatorname{\textsf{MM}}}({\operatorname{\textsf{sort}}}(a))\).

Beweis durch Induktion nach \(|a|\):

Merge-Sort: Korrektheit (2)

zu zeigen: \({\operatorname{\textsf{sort}}}(a)\) ist monoton.

Beweis durch Induktion nach \(|a|\):

Komplexität von Merge-Sort

Asymptotische Komplexität von Merge-Sort

Übungsserie 4 (für KW 18)

Aufgaben 4.A (autotool)

Aufgabe 4.1 (Permutationen)

Bestimmen Sie die Anzahl \(A(n)\) der Permutationen von \([1\dots n]\), die sowohl 2-geordnet als auch 3-geordnet sind.

Aufgabe 4.2 (Shell-Sort)

Für Eingabe \([10,9,\dots,2,1]\) (o.ä. — wird dann vom Übungsleiter vorgegeben):

Bestimmen Sie experimentell Zahlen \(c,d\), so daß Shell-Sort mit Differenzenfolge \([c,d,1]\) möglichs wenig Element-Vergleiche ausführt.

Hinweis: Bei der Bearbeitung der Aufgaben könnte diese Implementierung von Shell-Sort nützlich sein: https://gitlab.imn.htwk-leipzig.de/waldmann/ad-ss17/blob/master/kw17/shell.cc. Bei der Präsentation im Seminar rechnen Sie an der Tafel ohne maschinelle Hilfe.

Zusatz-Aufgabe 4.3 (Der Osterhase)

(Wird diskutiert, sobald eine Gruppe eine Lösung anmeldet und sofern in der Übung Zeit ist. Das und evtl. Vergabe von Zusatzpunkten liegt im Ermessen der Übungsleiter.)

Der listige Osterhase hat ein buntes Osterei versteckt, hinter einem der Grasbüschel \(1, 2,\ldots, n\).

Der fleißige Student sucht das Ei.

Er erhebt sich vom Schreibtisch, geht zu Grasbüschel \(i\) und sieht nach. Ist das Ei dort, hat er gewonnen.

Ist das Ei nicht dort, geht er zum Schreibtisch zurück, um weitere Übungsaufgaben zu bearbeiten.

Hinter seinem Rücken nimmt der Osterhase das Ei von der Stelle \(j\) (diese war ungleich \(i\)) und versteckt es in einer der maximal zwei direkt benachbarten Positionen (\(j-1\) oder \(j+1\), falls diese in \([1\dots n]\) liegen).

Nachdem der Student eine Weile überlegt hat, erhebt er sich vom Schreibtisch, …(siehe oben).

Untersuchen Sie für jedes \(n\ge 1\):

Beispiel: \(n=3\). Schritt 1: teste Position 2. Falls das Ei nicht dort ist, dann ist es in 1 oder 3. Im nächsten Schritt muß es der Hase nach 2 legen, weil das die einzige Nachbarposition von 1 und von 3 ist. Deswegen ist Schritt 2: teste Position 2 sicher erfolgreich.

Übungsserie 5 (für KW 19)

Aufgabe 5.A (autotool)

Merge von \(a\) und \(b\) mit \(|a|=2\) und \(|b|=4\) (oder ähnlich) mit wenig Vergleichen.

Aufgabe 5.1 (Merge-Sort)

Für Eingabe \([10,9,\dots,2,1]\) (o.ä. — wird dann vom Übungsleiter vorgegeben):

Such-Aufgabe: zur Implementierung von sort in der Haskell-Standardbibliothek Data.List

Aufgabe 5.2 (Entscheidungsbäume, Merge)

Benutzen Sie Entscheidungsbäume, um eine untere Schranke für die Anzahl der notwendigen Vergleiche bei \({\operatorname{\textsf{merge}}}(a,b)\) als Funktion von \(|a|\) und \(|b|\) zu erhalten.

Die Blätter des Entscheidungsbaumes sind Permutationen von \(a\cdot b\), welche die relative Reihenfolge der Element aus \(a\) sowie der Elemente aus \(b\) beibehalten.

Beispiel: eine solche Permutation von \([a_1,a_2]\cdot[b_1,b_2,b_3]\) ist \([b_1,a_1, b_2,b_3,a_2]\).

Analyse rekursiver Algorithmen

Übersicht

[WW] Kapitel 7

Definition, Motivation

Termination und Komplexität rekursiver Algorithmen

Multiplizieren durch Verdoppeln

(vgl. früher angegebener iterativer Algorithmus)

mult(nat a, nat b) = if a = 0 then 0 
  else mod(a,2) * b + 2 * mult(div(a,2),b)

Multiplikation von Binärzahlen

mit bisher bekanntem Verfahren:

geht das schneller? Überraschenderweise: ja!

Multiplikation von Binärzahlen

Multiplikation von Binärzahlen

Hauptsatz über Rekursionsgleichungen

Begründung des Hauptsatzes (1)

für \(n=b^e\), also \(e=\log_b n\). Dann \(a^e=n^x\) mit \(x={\log_b a}\). \[\begin{aligned} f(b^e) = {} & a\cdot f(b^{e-1}) + g(b^e) \\ = {} & a (a\cdot f(b^{e-2}) + g(b^{e-1})) + g(b^ e) \\ = {} & a^e\cdot f(b^0) + \sum_{k=0}^e a^{e-k} \cdot g(b^k) \\ f(n) = {} & \Theta(n^{\log_b a}) + a^e\cdot \sum_{k=0}^e a^{-k} \cdot g(b^k) \\ = {} & \Theta(n^x) + n^x\cdot \sum_{k=0}^e g(b^k)/a^k\end{aligned}\] drei Fälle: A) \(n^x\) am größten, B) Summanden für alle \(k\) ähnlich groß. C) Summand für \(k=0\) am größten.

Begründung des Hauptsatzes (2)

Begründung des Hauptsatzes (3)

Begründung des Hauptsatzes (4)

Anwendungen des Hauptsatzes

Quicksort (Algorithmus)

Spezifikation: Ordnet \(a[1\dots n]\) schwach monoton steigend

\(Q(a[1\dots n])\): wenn = \(n\le 1\), dann fertig, sonst
= \(p=a[n]\) (das Pivot-Element)
tausche Elemente in \(a[1\dots n-1]\), bestimme \(k\in[1\dots n]\),
so daß = \(\forall 1\le i < k: a[i]<p\) und \(\forall k\le i< n: p\le a[i]\)
vgl. dutch national flag (mit 2 Farben)
\(a[k] \leftrightarrow a[n]\) ; \(Q(a[1\dots k-1])\) ; \(Q(a[k+1\dots n])\)

Quicksort (Laufzeit)

Quicksort (mittle Laufzeit — Herleitung)

Quicksort (mittle Laufzeit – Rechnung)

Quicksort (Verbesserungen)

Median-Bestimmung

Median ohne Sortieren (ein Spezialfall)

Median und Selektion (Plan)

Selektion in Linearzeit (Realisierung)

Übungsserie 6 (für KW 20)

Aufgabe 6.A (autotool)

zur Bestimmung des Medians von 5 Elementen mit 6 Vergleichen.

Aufgabe 6.2 (Rekursionsgleichungen)

Entscheiden Sie, ob der Hauptsatz anwendbar ist.

Falls ja, lösen Sie dann die Gleichung. (Jeweils 2 P)

Falls nein, lösen Sie dann die Gleichung. (Zusatz: 2 P)

Aufgabe 6.2 (ein seltsames Sortierverfahren)

Zum Sortieren einer Folge \(a[1\dots n]\) wird dieses rekursive Verfahren \(V\) vorgeschlagen:

wenn \(n\le 2\), dann sortiere \(a\) mit 0 oder 1 Vergleich.
sonst: = \(p=\lfloor n/3\rfloor+1, q=\lceil 2n/3\rceil\)
\(V(a[1\dots q])\); \(V(a[p \dots n])\); \(V(a[1\dots q])\)

Aufgabe 6.3 (Quicksort)

Dynamische Programmierung

Übersicht

[WW] Kapitel 8

Beispiel, Definition

Beispiel: Geldwechseln (Plan)

Beispiel: Geldwechseln (Realisierung)

Verstreute Teilfolgen

Gemeinsame Teilfolgen

Bestimmung von LCS (Plan)

Bestimmung von LCS (Realisierung)

LCS (Anwendung bei Quelltextverwaltung)

RNA-Sekundärstruktur (Definitionen)

RNA-Sekundärstruktur (Implementierung)

RNA-Sekundärstruktur (Impl. — Detail)

Weiteres zu RNA-Strukturen

Greedy (gierige) Algorithmen

Übersicht

Beispiel, Definition

Bin Packing (Koffer packen): Spezifikation

Bin Packing: Algorithmen

Online- und Offline-Algorithmen

Online-Algorithms: First Fit (FF)

Untere Schranke für Online-Algorithmen

Schärfere untere Schranke für FF

Übungsserie 7 (für KW 21)

Organisatorisches

Aufgabe 7.1 (RNA-Struktur)

Aufgabe 7.2 (Greed)

Wir nennen ein Münzsystem einfach, wenn das gierige Verfahren für jeden Betrag eine Darstellung mit minimaler Münzenzahl liefert.

Aufgabe 7.3 (Bin Packing)

First Fit Decreasing (FFD) \(=\) First Fit für die absteigend sortierte Eingabefolge.

Bäume als Impl. von Mengen, Abbildungen, Folgen

Übersicht

vgl. [WW] 4.4, 6.2

Bäume in der Graphentheorie

Bäume in der Informatik

Binärbäume

Binärbäume (Beispiele Größe, Höhe)

  size (Branch(Branch(Leaf,2,Leaf),3,Branch(Leaf,5,Leaf)))
= 1 + size(Branch(Leaf,2,Leaf)) + size (Branch(Leaf,5,Leaf))
= 1 + 1 + size (Leaf) + size(Leaf) + 1 + size(Leaf) + size(Leaf)
= 1 + 1 +   1         +   1        + 1 +    1       +    1
= 7

  height (Branch(Branch(Leaf,2,Leaf),3,Branch(Leaf,5,Leaf)))
= 1 + max (height (Branch(Leaf,2,Leaf)), height(Branch(Leaf,5,Leaf)))
= 1 + max (1 + max(height(Leaf),height(Leaf)), 1 + max(height(Leaf),height(Leaf)))
= 1 + max (1 + max(0,0)                    , 1 + max(0,0))
= 1 + max (1 + 0, 1 + 0) 
= 2

Binärbäume (Beweis Größe/Höhe)

Satz: \(\forall t: {\operatorname{\textsf{size}}}(t)\le 2^{{\operatorname{\textsf{height}}}(t)+1}-1\)

Beweis: Induktion nach \({\operatorname{\textsf{height}}}(t)\):

Binärbäume (Realisierungen)

Baum-Durchquerungen

Baum-Durchquerungen (Beispiele)

t = Branch(Branch(Leaf,2,Leaf),1,Branch(Branch(Leaf,4,Branch),3,Leaf))

ino(t)
= ino(Branch(Branch(Leaf,2,Leaf),1,Branch(Branch(Leaf,4,Branch),3,Leaf)))
= ino(Branch(Leaf,2,Leaf)) ++ [1] ++ ino(Branch(Branch(Leaf,4,Branch),3,Leaf))
= ino(Leaf) ++ [2] ++ ino(Leaf) ++ [1] ++ ino(Branch(Leaf,4,Branch)) ++ [3] ++ ino(Leaf)
= [] ++ [2] ++ [] ++ [1] ++ ino(Leaf) ++ [4] ++ ino(Branch) ++ [3] ++ []
= [2,1,4,3]

pre(t) = [1,2,3,4]
post(t) = [2,4,3,1]

keys(t) = {1,2,3,4}

Suchbäume — Definition, Suchen

Suchbäume — Suchen (Beispiel)

  contains (4, Branch(Branch(Leaf,2,Leaf),3,Branch(Leaf,5,Leaf)))
= contains (4, Branch(Leaf,5,Leaf))
= contains (4, Leaf)
= false

Suchbäume — Einfügen

Suchbäume — Einfügen (Beispiel)

  insert (4,Branch(Branch(Leaf,3,Leaf),5,Branch(Branch(Leaf,7,Branch),9,Leaf)))
= Branch(insert(4,Branch(Leaf,3,Leaf)),5,Branch(Branch(Leaf,7,Branch),9,Leaf))
= Branch(Branch(Leaf,3,insert(4,Leaf)),5,Branch(Branch(Leaf,7,Branch),9,Leaf))
= Branch(Branch(Leaf,3,Branch(Leaf,4,Leaf)),5,Branch(Branch(Leaf,7,Branch),9,Leaf))

Suchbäume — Einfügen (Beweis)

1. Lemma \(t\in{\operatorname{\textsf{Such}}}(K) \iff t={\operatorname{\textsf{Leaf}}}\vee t={\operatorname{\textsf{Branch}}}(l,k,r) \wedge l\in{\operatorname{\textsf{Such}}}(K)\wedge r\in{\operatorname{\textsf{Such}}}(K) \wedge \forall x\in{\operatorname{\textsf{keys}}}(l): x<k \wedge \forall x\in{\operatorname{\textsf{keys}}}(r): k < x\).

Beweis:

2. Korrektheit des Einfügens: zu zeigen sind

Persistente und ephemere Datenstrukturen

Bestimmen und Löschen des Minimums

Suchbäume — Löschen

Übungsserie 8 für KW 22

Aufgabe 8.A (autotool)

Grundsätzliches

Auch wenn es nicht explizit dasteht: alle Aussagen sind zu begründen.

Es mag ja sein, daß in der Schule trainiert wird, bestimmen Sie von geben Sie anzu unterscheiden.

Sie sind jetzt aber an einer Hochschule, und dort gibt es nicht für jeden Arbeitsschritt eine separate Einladung und Anleitung,

denn das Studienziel ist, daß Sie wissenschaftliche Methoden des Fachgebietes selbständig anwenden.

Das wissenschaftliche Vorgehen zeichnet sich gerade dadurch aus, daß jeder Schritt begründet und jedes Resultat überprüfbar ist.

Aufgabe 8.1 (Bäume)

Für die durch

\(B(n) := {\operatorname{\textbf{if}}~}n>0{~\operatorname{\textbf{then}}~}{\operatorname{\textsf{Branch}}}(B(n-1),n,B(n-1)) {~\operatorname{\textbf{else}}~}{\operatorname{\textsf{Leaf}}}\)

definierten Binärbäume:

Aufgabe 8.2 (Suchbäume)

Aufgabe 8.3 (Suchbäume)

Implementieren Sie diese Spezifikation

in Zeit \(O({\operatorname{\textsf{height}}}(t))\).

(3 P) Ergänzen Sie den Ansatz

(1 P) Bestimmen Sie \({\operatorname{\textsf{up}}}(5,t)\) für \(t=\) der Baum, der durch Einfügen von \([1,8,2,7,3,6,4,5]\) in dieser Reihenfolge in \({\operatorname{\textsf{Leaf}}}\) entsteht.

Balancierte Suchbäume

Motivation

Zu strenge Balance

Höhen-Balance (Definition)

Höhen-Balance erzwingt logarithmische Höhe

Operationen für balancierte Suchbäume

Balancieren durch Rotieren (1)

Balancieren durch Rotieren (2)

Korrektheit und Anzahl der Rotationen: Insert

Korrektheit und Anzahl der Rotationen: Delete

Ergänzungen

Anwendungen Suchbäume

Weitere Operationen für Suchbäume

Übungsserie 9 für KW 23

Aufgabe 9.A

Aufgabe 9.1 (Rotieren)

Aufgabe 13.2–4 aus [Cormen, Leiserson, Rivest, Stein] (deutsche Ausgabe als E-Buch in der Bibliothek)

Die Aussage ist zu ergänzen: …in jeden anderen binären Suchbaum mit der gleichen Schlüsselmenge …, sonst ist sie trivial falsch.

(2 P) Lösen Sie die Aufgabe für den Spezialfall, daß \(t_1\) ein vollständiger binärer Suchbaum mit 7 Schlüsseln und \(t_2\) eine rechtsläufige Kette ist.

(2 P) Lösen Sie die Aufgabe allgemein.

Aufgabe 9.2 (AVL-Struktur)

Aufgabe 9.3 (AVL-Operationen)

Heap-geordnete Bäume

Übersicht

Motivation und Plan

Binäre Heaps (Plan)

Binäre Heaps (Implementierung)

Binäre Heaps: Einfügen, Verringern

Binäre Heaps: Minimum bestimmen und entfernen

Binäre Heaps: Heap erzeugen

Bemerkung zur Implementierung (I)

Bemerkung zur Implementierung (I)

Anwendung binärer Heaps: Heapsort

Ausblick: schnellere Heaps

Übungsserie 10 für KW 24

Aufgabe 10.A (autotool)

Aufgabe 10.1 (Binäre Heaps)

Aufgabe 10.2 (Kombination Suchbaum und Heap)

Wir betrachten binäre Bäume, deren Schlüssel Zahlenpaare sind, so daß für die ersten Komponenten die Heap-Eigenschaft und für die zweiten Komponenten die Suchbaum-Eigenschaft gilt. (Es wird keine Balance-Eigenschaft gefordert.)

Aufgabe 10.3 (Young-Tableaux)

(4 P) [CLRS] Aufgabe 6-3 a,c,d,e.

Direkter Zugriff (Hashing und Anwend.)

Übersicht

[WW] 9, [CLRS] 11

Motivation

Sortieren durch Zählen

Hashing zur Implementierung des ADT Menge

Hashfunktionen (1)

Hashfunktionen (2)

Hashing mit Verkettung (Chaining)

Hashing mit offener Adressierung

Offene Adressierung und Delete

Lineares Sondieren und Haufen (Clustering)

Offene Adr. mit doppeltem Hashing

Erwartete Laufzeit f. doppeltes Hashing

Eine Variante des doppelten Hashing

Amortisierte Komplexität

Übersicht

[CLRS] Kapitel 17.4

Motivation

Def. und Bsp.: Amortisierte Komplexität

Die Potential-Methode

Amortisierte Analyse von Quake Heaps

Strukturelle Invarianten von Quake Heaps

extractMin für Quake Heaps

Logarithmische Höhe und Erdbeben

Potential für Quake Heaps

Übungsserie 11 für KW 25

Aufgabe 11.A (autotool: Hashing)

Aufgabe 11.1 (Hashing)

Für

den Algorithmus an einem Beispiel an der Tafel vorführen.

Aufgabe 11.2 (Kuckucks-Hashing)

engl. cuckoo hashing

Aufgabe 11.3 (Amortisierte Analyse)

Wiederholung (1. Semester):

Die Schlange \(S\) soll durch zwei Keller \(L,R\) implementiert werden.

Aufgaben:

Aufgabe 11.4 (Zusatz) (Quake Heaps)

Graphen: Eigenschaften, einfache Algorithmen

Überblick

Andreas Brandstädt: Graphen und Algorithmen, Teubner 1994, https://link.springer.com/book/10.1007/978-3-322-94689-8

Hansjoachim Walther, Günther Nägler: Graphen — Algorithmen — Programme, Fachbuchverlag Leipzig 1987

Motivation, Definition, Beispiele

Spezielle Graphen, Graph-Operationen

Eigenschaften von Graphen

Verbindungen, Abstände

Die Größe spezieller Teilgraphen

Repräsentationen von Graphen

Das Durchlaufen von Graphen (Schema)

Breitensuche (breadth first search, BFS)

Tiefensuche (depth first search, DFS)

Bezeichnungen für DFS-Bäume und -Ordnung

DFS-Klassifikation der Kanten

DFS für ungerichtete Graphen

Gerichtete kreisfreie Graphen (DAG)

Topologisches Ordnen

Minimal-Gerüste

Überblick

Definition Minimalgerüst

Algorithmus (Schema)

Algorithmus (Eigenschaften, Realisierungen)

Algorithmus von Kruskal (1956)

Union-Find-Strukturen

Mengensysteme (DSF, disjoint set forest)

Effiziente Implementierung von \({\operatorname{\textsf{Union}}}\) in DSF

Effiziente Implementierung von \({\operatorname{\textsf{find}}}\) in DSF

Zusammenf./Ausblick: MST-Algorithmen

Übungsserie 12 für KW 26

Aufgabe 12.A (autotool)

Aufgabe 12.1 (vorrechnen)

Algorithmen an der Tafel ausführen, ggf. auch als Teil der Diskussion einer der folgenden Aufgaben.

Aufgabe 12.2 (Graph-Eigenschaften)

Aufgabe 12.3 (Tiefensuche)

Aufgabe 12.4 (Minimalgerüste)

Kürzeste Wege

Überblick

WW 10

Definitionen

Algorithmus von Dijkstra

Algorithmus von Dijkstra: Korrektheit

Algorithmus von Dijkstra: Laufzeit

Algorithmus von Dijkstra: über den Autor

Kürzeste Wege für alle Knotenpaare

Der tropische Halbring

Matrizen über Halbringen

Matrizen von Weg-Kosten

Berechnung von Matrix-Potenzen

Algorithmus von Floyd und Warshall

Übungsserie 13 für KW 27

Allgemeines

Aufgaben 13.A (autotool)

zu Algorithmen von

Das sind dann nicht unbedingt Pflicht-Aufgaben. Nutzen Sie trotzdem diese Gelegenheit, sich diese Algorithmen vom autotool vorführen zu lassen.

Aufgabe 13.1 (Algorithmus von Prim)

Der Algorithmus von Prim zur Bestimmung eines Minimalgerüstes entsteht aus dem Algorithmus von Dijkstra zur Bestimmung kürzester Pfade, indem die Anweisung \(d[y]:=\min\{d[y],d[x]+w(x,y)\}\) durch die Anweisung \(d[y]:=\min\{d[y],w(x,y)\}\) ersetzt wird.

Jedesmal, wenn dort \(w(x,y)<d[y]\), notieren wir \(x\) als Vorgänger von \(y\) (in einem Array \(p\) durch die Zuweisung \(p[y]:=x\)). Diese Vorgänger-Zuordnung kann wechseln, solange \(y\) grau ist.

Die Vorgängerkanten bilden am Ende des Algorithmus einen Baum, der ein Minimalgerüst für \((G,w)\) ist.

Aufgabe 13.2 (Algorithmus von Dijkstra)

Aufgabe 13.3 (all pairs shortest paths)

Weitere Beispiele zu Graphen und -Algorithmen

Färbungen (Definition, Beispiele)

Färbungen (Geschichte)

Chromatische Zahl und Maximalgrad

Der Satz von Brooks

Hohe chromatische Zahl ohne Dreiecke

Effizientes Färben

Komplexitätstheorie

Reduktionen

Zusammenfassung

Übersicht

was haben wir hier eigentlich gelernt?

und warum?

Algorithmen

Datenstrukturen

Komplexität, Effizienz

Sortieren (Technik)

Sortieren (Einschätzung)

dieses Semester:

ab 3. Semester:

Suchbäume und Heaps

Wie weiter?

Wie weiter? (Werbung für meine Vorlesungen)

Bachelor

Master

Eine Aufgabe für die Semesterpause

Vorsicht! nicht zuviel Zeit investieren!

Plan der Vorlesungen/Übungen

Übersicht nach Kalenderwochen

Wörter, die es nicht gibt

Häufige Übersetzungsfehler in der Informatik