Grundlagen

• Korrektheit

• Laufzeit

• Speicherplatz

• Kommunikationszeit

• Güte

Es wird durch folgendes unmöglich Algorithmen zu vergleichen

• Unterschiedliche Compiler

• Betreibsstem

• schneller Hardware

• Laufzeitumgebungen

• Eingaben

• verwendete Datenstruckturen

1. Idealisierter Rechner mit Festen befehlen abzählbar unendliche ram,

   1. Laufzeit Rambefehle

   2. speicherbedarf benötigte speicherzellen

2. Ermittlung charakteristischer Parameter

   (sortieren -> Vertauschungen & Vergleiche)

   Laufzeit & Speicher ist in der Regel abhängig von der Größe der Eingabe

Laufzeit und Speicherbedarf ist abhängig von der Eingabe

Bei einer Laufzeit von 2^n brint ein Doppelt so schneller rechner dargestellt als gleichung 2*2^n was umgerechnet 2^n+1 ist! Mit anderen Worten in dem Fall sorgt ein Doppelt so schneller Rechner nur für eine größere eingabe von 1

Dabei betrachten wir nur Funktionen mit natürlichen Funktionswerten, also f, g : N → N, weil wir die Anzahl von Schritten oder benutzten Speicherzellen angeben. Konstante Faktoren c werden bei Aufwandsabschätzungen vernachlässigt; es wird nur das asymptotische Wachstum der Funktionen betrachtet, also das Verhalten bei großen Werten von n.

Hinweis: In der Klausur kann nat¨urlich auch nach der Definition von Groß-Omega oder Groß-Theta gefragt werden

Nein. Es können auch obere Schranken fürr Average- oder Best-Case-Abschätzungen angegeben werden. Groß-O heißt nicht automatisch Worst-Case, es beschreibt lediglich obere Schranken.

Die Menge der zulässigen Eingaben der Länge n bezeichnen wir mit Wn, die Anzahl der Schritte von Algorithmus A für Eingabe w mit A(w).

Dann ist die Worst-Case-Komplexität definiert als

TA(n) = sup{A(w) | w ∈ Wn}

und ist eine obere Schranke fürr die maximale Anzahl der Schritte, die Algorithmus A benötigt, um Eingaben

der Größe n zu bearbeiten.

TA(n)$ ist der Maximalwert, den die Funktion A(w) annehmen kann, wenn alle möglichen Wörter w der exakten Länge n ausgewertet werden.

Eingabelänge = n

Lulässige eingabelänge = Wn

Alogirthmus = a

Alogirithmus für eingabe w = A(w)

• Divide-and-conquer,

• dynamische Programmierung

• Greedy

• Backtracking

• Branch-and-Bound und

• lokale Suche.

• Divide the problem into subproblems.

• Conquer the subproblems by solving them recursively.

• Combine subproblem solutions. (Dieser Schritt kann ggf. entfallen)

Potenzieren einer Zahl:

function Power(x, n)

if n = 1 then return x ▷ Rekursionsende

if n is even then

m := n/2 ▷ divide

t := Power(x, m) ▷ conquer

return t · t ▷ combine

else

m := n−1/2 ▷ divide

t := Power(x, m) ▷ conquer

return t · t · x ▷

Bei Divide-And-Conquer entstehen in den rekursiven Aufrufen Teillösungen, die wir im Combine-Schritt zusammen fügen müssen. Damit wir nicht dieselben Teilprobleme immer wieder rekursiv lösen, werden bereits berechnete Teillösungen in Tabellen gespeichert. Diesen Ansatz nennt man memorieren.

Anstatt die Teillösungen rekursiv zu berechnen, kann man aber auch einen Bottom-Up-Ansatz wählen: Aus Rekursion wird Iteration, indem wir aus kleinen Teillösungen größere Lösungen zusammensetzen. Da wir nicht von vorneherein wissen, welche Teillösungen wir benötigen, berechnen wir einfach alle. Dieses Verfahren wird oft bei Optimierungsproblemen eingesetzt und heißt dynamische Programmierung.

Unter anderem beim 0/1-Rucksack-Problem, beim Wechselgeld-Problem, bei der Levenshtein-Distanz und bei einigen Graphalgorithmen wie z.B. die transitive Hülle oder all-pairs-shortest-path

Das Optimalitätsprinzip von Bellman:

Eine optimale Lösung kann aus optimalen Teillösungen zusammengesetzt werden;

Dies gilt z.B. bei küzesten Wegen:

Jeder Teilweg (vi, . . . , vj ) eines kürzesten Weges (v1, . . . , vi, . . . , vj , . . . , vk) ist ebenfalls ein kürzester Weg.

Sei knap(h, i) der maximale Wert, der mit den Objekten i, . . . , n und Rucksackgröße h erreicht werden kann. Dann gilt für i < n und h ≥ gi

Antwort: Betrachte die Lösung eines Problems als eine Sequenz von Entscheidungen. Das Verfahren ist also iterativ. Im Schritt i wird aus allen möglichen ”Fortsetzungen Ai einer Teillösung“

diejenige ausgewählt, die momentan den besten Erfolg bringt. Dazu wird ein Kostenmaß genutzt. Es werden also nicht verschiedene Kombinationen von Teillösungen getestet, sondern nur eine einzige ausgewählt. Diese Lösung ist ggf. nicht optimal.

Probleme:

Rucksack-Problem, Handlungsreisenden-Problem (nur approximativ), Wechselgeld-Problem (ist nicht für alle Münzsysteme exakt), Präfix-Code nach Huffman und bei einigen

Graphalgorithmen wie z.B. minimaler Spannbaum nach Kruskal.

Hinweis: Es reicht nicht aus, in der Klausur zu schreiben, dass Greedy-Algorithmen ”lokale Entscheidungen“ treffen. Was soll lokal denn bedeuten? Was ist der Unterschied zu ”lokaler Suche“?

Sortiere die Objekte nach Nutzen pro Gewicht, sodass

w1/g1 ≥ w2/g2 ≥ . . . ≥ wn/gn gilt.

Nimm in Schritt i das Objekt i in die Lösung auf.

Problem hierbei: Das letzte Objekt kann evtl. nur teilweise in den Rucksack aufgenommen werden. Dies ist also keine Lösung für das 0/1-Rucksack-Problem, aber wird das letzte Element nicht in den Rucksack aufgenommen, so ergibt sich eine approximative Lösung für das 0/1-Rucksack-Problem.

Antwort: Die Münzen seien abfallend sortiert nach ihrer Größe, also d1 ≥ d2 ≥ . . . ≥ dk = 1.

In der Regel wird dk = 1 vorausgesetzt, damit jeder Betrag ausgezahlt werden kann.

Rekursiv: Der auszuzahlende Betrag sei p. Dann lautet der initiale Aufruf Geld(1, p). Imnfolgenden Algorithmus bezeichnet div die ganzzahlige Division.

function Geld(i, p : int) : int

if p = 0 then

return 0

return p div di + Geld(i + 1, p mod di)

Hinweis: Es reicht nicht aus, in der Klausur so etwas wie ”Nimm immer die größte Münze und nimm davon so viele, dass der Betrag nicht überschritten wird.“ zu schreiben.

Warum denn immer nur die größte Münze? Werden die anderen gar nicht benötigt? Wie berechnet man denn, wie viele Münzen pro Schritt möglich sind? Wie wird der verbleibende Betrag berechnet?

Wir haben in der Vorlesung zu der Frage ”Was ist ein Algorithmus?“ gelernt: Ein schrittweises und endlich beschreibbares Verfahren zum Lösen eines Problems, das ”mechanisch“ ausgeführt werden kann.

Die einzelnen Schritte sind verständlich und nachvollziehbar ! Ein Algorithmus muss nicht (falls nicht anders gefordert) als Pseudo-Code angegeben werden.

Aber Algorithmen müssen exakt beschrieben werden, und dazu eignet sich Pseudo-Code sehr gut

Antwort: Bezeichne d1, . . . , dk die Werte der M¨unzen und coins(p) die minimale Anzahl Münzen, um den Betrag p auszuzahlen. Dann ergibt sich folgende Optimierungsfunktion:

Bei dynamischer Programmierung erfolgt die Berechnung aber nicht rekursiv sondern iterativ, wobei Zwischenergebnisse in einem Array C gespeichert werden.

C[0] := 0

for i := 1, . . . , p do

C[i] := min {1 + C[i − dj ]}

j:dj ≤i

Das Master-Theorem gibt die Lösung einer allgemeinen Rekursionsgleichung der folgenden Form an: T (n) = a · T (n/b) + Θ(nk)

Es lässt sich oft auf Rekursionsgleichungen anwenden, die bei Divide-And-Conquer-Algorithmen entstehen, z.B. Laufzeit der binären Suche, Best-Case-Laufzeit von Quicksort oder der Laufzeit von Mergesort. Es ist immer dann anwendbar, wenn a viele Teilprobleme jeweils der Größe n/b zu lösen sind und der Divide- und der Combine-Schritt zusammen einen Aufwand von Θ(nk) haben

Antwort:

• Binäre Suche: T (n) = 1 · T (n/2) + Θ(1), also ein rekursiver Aufruf (a = 1); die zu durchsuchende Folge wird in jeder Runde halbiert (b = 2); das Aufteilen in Teilprobleme

bzw. das Zusammenfassen von Teill¨osungen dauert nur konstante Zeit (k = 0).

a = bk → T ∈ Θ(nk · log(n)) = Θ(log(n))

• Mergesort: T (n) = 2 · T (n/2) + Θ(n), also zwei rekursive Aufrufe (a = 2); die zu sortie-

renden Teilfolgen werden in jeder Runde halbiert (b = 2); das Aufteilen in Teilfolgen ist

in konstanter Zeit m¨oglich, aber das Mischen der sortierten Teilfolgen zu einer einzigen

sortierten Folge kostet lineare Zeit (k = 1).

a = bk → T ∈ Θ(nk · log(n)) = Θ(n · log(n))

Antwort: naiver Algorithmus

for i := 1 to n do

for j := 1 to n do

c[i][j] := 0

for k := 1 to n do

c[i][j] := c[i][j] + a[i][k] * b[k][j]

Die Laufzeit liegt in Θ(n3), denn es müssen n2 viele Elemente cij berechnet werden; die Berechnung jedes einzelnen Elements cij dauert Zeit Θ(n

Antwort: Es ist ein Divide-And-Conquer Algorithmus: Teile die gegebene Folge mittels eines Pivot-Elements p auf in zwei Teilfolgen:

Folge K enthält nur Elemente kleiner gleich p und

Folge G enthät nur Elemente größer gleich p.

Sortiere anschließend die Teilfolgen rekursiv, sodass sich insgesamt eine sortierte Folge ergibt: sorted(K), p, sorted(G)

1. Divide: Wähle aus allen Werten einen beliebigen Wert p, das Pivotelement aus und teile die Folge in zwei Teilfolgen K und G auf:

• K enthält Werte die kleiner oder gleich p sind,

• G enthält Werte die größer oder gleich p sind.

Antwort:

1. Wähle ein Pivot-Element p.

2. Suche das erste Element (von links), das größer als p ist, und suche das erste Element (von rechts), das kleiner als p ist, und vertausche die beiden Elemente.

3. Wiederhole das Suchen und Vertauschen jeweils ab der Stelle, wo der letzte Tausch stattgefunden hat.

4. Tausche zum Schluss das Pivot-Element an die richtige Stelle.

function Partition(a : sequence; ℓ, r: Integer)

p := a[ℓ], i := ℓ + 1, j := r

repeat

while i < r and a[i] ≤ p do

i := i + 1

while j > ℓ and a[j] ≥ p do

j := j − 1

if i < j then

SwapAt(a, i, j)

until j ≤ i

SwapAt(a, ℓ, j)

return j

Als Laufzeit erhalten wir O(n · log(n)). Eine der resultierenden Folgen hat die Länge

1/10n, die andere hat eine Länge von 9/10n. Damit ergibt sich als Laufzeit

Da der obige Baum logarithmische Tiefe hat, ergibt sich als Laufzeit O(n · log(n)).

Die Wahrscheinlichkeit, dass die Folge an Position p aufgeteilt wird, ist 1/n. Das Aufteilen in zwei Teilfolgen erfolgt in Zeit O(n).

• Worst-Case-Laufzeit ist O(n2)

• stark vorsortierte Folgen oder solche Folgen, die viele gleiche Elemente enthalten

Mittels einer Zufallsstrategie kann Quicksort verbessert werden: Wähle als Pivot-Element ein zufälliges Element aus A[l...r] und vertausche es mit A[l].

⇒ Laufzeit ist unabhängig von der zu sortierenden Folge

⇒ mittlere/erwartete Laufzeit: Θ(n · log(n))

3-Wege-Split Quicksort

Teile die Folge a[l], . . . , a[r] in drei Folgen Fl, Fm, Fr auf.

• Fl enthält die Elemente mit Schlüssel < k.

• Fm enthält die Elemente mit Schlüssel = k.

• Fr enthält die Elemente mit Schlüssel > k

Sortiere Fl und Fr auf dieselbe Weise.

Idee: Die Pivotelemente werden zuerst am Rand gesammelt (zwischen l und l2 sowie zwischen r2 und r) und vor dem rekursiven Aufruf in die Mitte transportiert.

Im ungünstigen Fall ist die Rekursionstiefe O(n).

Wir können die Rekursionstiefe aber wie folgt auf O(log(n)) beschränken:

• löse das kleinere Teilproblem rekursiv und

• löse das größere Teilproblem iterativ direkt

• quicksort(int l, int r)

  while l < r

  m := partition(l, r)

  if (m-l) < (r-m) then

  quicksort(l, m-1)

  l := m + 1

  else

  quicksort(m+1, r)

  r := m - 1

Mergesort und Heapsort

Bezeichne d1, . . . , dk die Werte der Münzen und coins(p) die minimale Anzahl Münzen, um den Betrag p auszuzahlen. Dann ergibt sich folgende Optimierungsfunktion:

Bei dynamischer Programmierung erfolgt die Berechnung aber nicht rekursiv sondern iterativ, wobei Zwischenergebnisse in einem Array C gespeichert werden.

C[0] := 0

for i := 1, . . . , p do

C[i] := min j:dj ≤i{1 + C[i − dj ]

• Teile die Folge in zwei etwa gleich große Teilfolgen.

• Sortiere die Teilfolgen rekursiv.

• Mische die sortierten Teilfolgen zu einer Folge zusammen.

  • Zunächst werden die Werte in ein Hilfsarray kopiert.

  • Durchlaufe die Hilfsarrays jeweils elementweise von vorne nach hinten.

  • Das jeweils kleinere der beiden Elemente wird in das originale Array an die nächste Stelle zurück kopiert.

→ T (n) = 2 · T (n/2) + c · n ∈ O(n · log n)

• Erstelle einen initialen Max-Heap. Anschließend wird in Runde k das oberste Element mit dem Element an Position n − k getauscht und das nun oberste Element versickert.

• Es werden n Runden benötigt, jeweils mit der Laufzeit O(log n), da der Heap nur logarithmische Tiefe hat. Aufbauen des initialen Heaps erfolgt in Zeit O(n).

• Das Erstellen des initialen Heaps erfolgt, indem wir die Elemente kn/2−1, . . . , k0 nacheinander versickern lassen. Dabei müssen n/4 Elemente nur um eine Ebene im Baum verschoben werden, n/8 viele Elemente nur um 2 Ebenen usw

Allgemeine Sortierverfahren verwenden ausschließlich Vergleichsoperationen zwischen Schlüsseln, um die Positionen der Werte in der sortierten Folge zu bestimmen, aber keine arithmetischen Operationen oder ähnliches.

Jedes allgemeine Sortierverfahren benötigt zum Sortieren von n verschiedenen Schlüsseln im schlechtesten Fall und im Mittel wenigstens Ω(n · log(n)) Schlüsselvergleiche.

Man zeigt das über die Höhe von Entscheidungsbäumen.

Worst-Case-Analyse:

• es gibt n! verschiedene Permutationen üuber n Zahlen

• ein Entscheidungsbaum hat mindestens n! Blätter

• ein Binärbaum der Höhe h hat maximal 2h − 1 Blätter

• es muss also gelten: 2h ≥ n!

Ja, mittels Counting-Sort bzw. Radix-Sort. Die funktionieren aber nur gut für Integer-Werte. Zusammengesetzte Datentypen wie double (setzt sich aus Mantisse und Exponent zusammen) bereiten bei Radix-Sort Probleme, Counting-Sort ist nicht brauchbar bei großen Wertebereichen.

Gleiche Elemente stehen nach dem Sortieren in der gleichen relativen Reihenfolge

zueinander wie vor dem Sortieren.

O(n + k) bei n Elementen und k Schl¨usselwerten.

• Initialisieren des Count-Arrays: O(k)

• Durchlaufen der Werte zum Erstellen der Counts: O(n)

• Count aufsummieren: O(k)

• Einsortieren der Werte: O(n)

Sortiere die Zahlen anhand der einzelnen Ziffern, beginnend mit der niederwertigsten Stelle. Verwende ein stabiles Sortierverfahren wie Countingsort. Falls nötig, müssen führende Nullen eingefügt werden. Dieser Ansatz ist für ganze Zahlen geeignet, aber nicht für reelle

Zahlen, da es überabzählbar viele reelle Zahlen gibt

Fasse jeweils r Bit einer Zahl zu einer Ziffer zusammen. Bei einer Wortlänge von b Bit müssen b/r Phasen durchlaufen werden.

Countingsort hat Laufzeit Θ(n + k), wobei n die Anzahl der Zahlen und {0, . . . , k − 1} der Wertebereich der Zahlen ist.

Bei b/r Phasen erhalten wir als Laufzeit von Radix-Sort

Θ(b/r · (n + 2r)).

In der Praxis fasst man bspw. 32-Bit-Wörter in Gruppen zu 8 Bit zusammen und erhält damit vier Phasen und insgesamt als

Laufzeit Θ(4 · (n + 28)) = Θ(n).

Sortiert Zahlen aus dem Bereich [0, 1], also reelle Zahlen, wobei das Verfahren nur dann eine lineare Laufzeit hat, wenn die Zahlen ungefähr gleichverteilt sind.

Die n Werte des Arrays werden in verschiedene Fächer einsortiert. Der Wert A[i] wird in das

Fach B[⌊n · A[i]⌋] eingefügt. Sind alle Werte in die jeweiligen Fächer eingefügt, entnimmt man die Werte nacheinander aus den Fächern B[0], . . . , B[n − 1] und fügt sie in dieser Reihenfolge in das Array A ein

Im Worst-Case werden alle Werte in dasselbe Fach einsortiert und es ergibt sich als Laufzeit O(n2).

Werden die Listen nicht sortiert gehalten sondern anschließend sortiert, erhalten wir im Worst-Case die Laufzeit O(n · log(n)).

Im Best-Case verteilen sich die Werte auf alle Fächer, sodass genau ein Wert pro Fach abgelegt wird.

Dann erhalten wir eine lineare Laufzeit O(n).

Auch im Average-Case erhalten wir eine lineare Laufzeit.

Sei Xi eine Zufallsvariable, die die Anzahl der Elemente im Fach B[i] beschreibt.

Für jedes Element A[j] gilt dann: Die Wahrscheinlichkeit, dass das Element A[j] im Fach i abgelegt wird, ist

P(A[j] fällt in Fach i) = 1/n.

Aus diesem Bernoulli-Experiment ergibt sich dann die lineare Laufzeit.

• Lineare Suche: O(n), überprüft ein Element nach dem anderen und findet damit im Durchschnitt nach n/2 Versuchen das gesuchte Element.

• Binäre Suche: O(log(n)). Beginne mit linker Grenze ℓ := 1 und rechter Grenze r := n. Vergleiche das Element in der Mitte m := ⌊ℓ+r/2 ⌋ mit dem gesuchten Element. Ist das gesuchte Element kleiner, dann setze r := m − 1, sonst setze ℓ := m + 1. In jeder Runde wird das zu durchsuchende Intervall halbiert.

  Die Anzahl der Schritte ist damit die durchschnittliche Tiefe eines entsprechenden Suchbaums, also O(log(n)), da ungef¨ahr die H¨alfte der Zahlen in der letzten Ebene und die andere Hälfte oberhalb davon liegt. Deshalb braucht man im durchschnittlichen Fall nur einen Schritt weniger als im schlechtesten Fall.

Antwort: Die Zahlen sind so gewählt, dass kein Taschenrechner benötigt wird!

best-case: Θ(1). Das Element wird direkt beim ersten Zugriff gefunden.

Wird nur erreicht, wenn die Werte gleichverteilt sind und keine Häufungen in den Werten enthalten sind.

worst-case: Θ(n). Wenn die Werte am Rand extrem von den anderen Werten abweichen, also

wenn die Werte sehr ungleichmäßig verteilt sind. Dann läuft der Algorithmus alle Positionen im Array durch.

Eine Laufzeitabschätzung ist nur möglich, falls die Werte im Array streng monoton steigen, also keine Werte mehrfach enthalten sind.

Das Eingrenzen des Suchbereichs hat dann

Laufzeit O(log(k)).

Da der Bereich höchstens k Elemente enthält, erfolgt die anschließende binäre Suche ebenfalls in Zeit O(log(k))

Bei einer Ringliste enthält das letzte Element einen Zeiger auf den Anfang der Liste

Eine Queue arbeitet nach dem FIFO-Prinzip (First-In, First-Out), ein Stack nach

dem LIFO-Prinzip (Last-In, First-Out)

Antwort: 44, 39, 20, 3, 25, 42, 67, 60, 59, 65, 75, 72, 89

Hinweis: In der Klausur kann natürlich auch nach der Postorder-, Levelorder- oder Inorder-Nummerierung gefragt werden.

Antwort: Ohne Balancierung würde durch das Einfügen von aufsteigend sortierten Werten ein zu einer Liste degenerierter Baum entstehen. Beim Einfügen eines Wertes müsste ggf. immer

bis ans Ende der Liste gelaufen werden.

Als Laufzeit zum Einfügen von n Elementen in einen

solchen Baum erhalten wir daher:

Das Einfügen eines einzelnen Elements würde so im Worst-Case Zeit O(n) dauern. Das Balancieren der Bäume führt zu einer besseren Worst-Case-Laufzeit von O(log(n)) für das Einfügen

und Löschen von sowie dem Suchen nach Objekten.

Hinweis: Es reicht nicht aus, nur zu schreiben, dass sonst eine lineare Liste entstehen kann.

Was ist denn so schlimm an einer linearen Liste? Solche Listen werden doch bspw. in der C++ Standard-Bibliothek benutzt, std::list und std::forward list. Wenn Listen so schrecklich

wären, bräuchte man die doch gar nicht implementieren.

Beim erfolgreichen Suchen eines Wertes werden gerade so viele Vergleiche benötigt, wie der gesuchte Knoten von der Wurzel entfernt ist. Die interne Pfadlänge (internal path length) eines Baums ist:

Wenn wir die interne Pfadlänge durch die Anzahl der Knoten N im Baum dividieren, so erhalten wir die durchschnittliche Anzahl der benötigten Vergleiche. Sei CN die durchschnittliche interne

Pfadlänge eines binären Suchbaums mit N Knoten. Dann gilt:

Analog zu der Rekursionsformel von Quicksort gilt

CN ∈ Θ(N log N ).

Dividieren wir durch N so erhalten wir die durchschnittliche Anzahl Vergleiche bei einer erfolgreichen Suche: Θ(log N )

In einem AVL-Baum unterscheiden sich die Tiefen des linken und des rechten Teilbaums für jeden Knoten höchstens um 1, sodass die Bäume im wesentlichen balanciert sind.

Unterscheiden sich die Tiefen im AVL-Baum zwischen zwei Teilbäumen nach dem Einfügen oder Löschen eines Elements um 2, wird mit Hilfe von sogenannten Rotationen der Baum wieder ausgeglichen. Eine Rotation hat konstante Laufzeit, das Aktualisieren der Differenzwerte kann sich allerdings bis zur Wurzel fortsetzen.

Suchen nach sowie Einfügen und Löschen von Objekten erfolgt in Zeit O(log(n)), wenn n die Anzahl der Objekte im Baum bezeichnet

Ein minimaler AVL-Baum der Höhe t > 1 setzt sich aus einer Wurzel und einem Teilbaum der Höhe t − 1 sowie einem Teilbaum der Höhe t − 2 zusammen. Für die minimale

Anzahl n(t) von Knoten in einem Baum der Höhe t gilt also:

→ n(t) = 1 + n(t − 1) + n(t − 2) = f ib(t + 3) − 1 ≈ 1.61803t+4

Aus der Mathematik wissen wir, dass die Fibonacci-Zahlen f ib(i) exponentielles Wachstum haben.

→ Die Höhe eines AVL-Baumes mit n Knoten ist in O(log(n)).

Teilbaum A ist vor und nach der Rotation links von K2, ebenso ist Teilbaum C vorher und nachher rechts von K1, sodass hier keine Erklärung nötig ist. Da K2 vorher links von K1 ist, gilt K2.key < K1.key, und damit ist die Anordnung von K1 und K2 nachher auch korrekt.

Bleibt nur noch der Teilbaum B. Die Werte der Knoten von B sind kleiner als K1.key und größer gleich K2.key, also ist auch nach der Rotation die Suchbaumeigenschaft erfüllt.

Es sind keine Binärbäume! Ein B-Baum der Ordnung m hat folgende Eigenschaften:

• Alle Blätter befinden sich in gleicher Tiefe.

• Alle inneren Knoten außer der Wurzel haben mindestens ⌈m/2⌉ Kinder. Besteht der Baum nicht nur aus der Wurzel, dann hat die Wurzel mindestens 2 Kinder.

• Jeder innere Knoten hat höchstens m Kinder. Ein Knoten mit k Kindern speichert k − 1 Schlüsselwerte.

• Alle Schlüsselwerte eines Knotens sind aufsteigend sortiert.

Seien k1, . . . , ks die Schlüssel eines inneren Knotens. Dann gibt es die Zeiger z0, z1, . . . , zs auf die Kinder und es gilt:

• z0 zeigt auf einen Teilbaum mit Werten kleiner als k1.

• zi für i = 1, . . . , s − 1 zeigt auf einen Teilbaum mit Werten größer als ki und kleiner als ki+1.

• zs zeigt auf einen Teilbaum mit Werten größer als ks.

Bestimme zunächst mittels einer Suche das Blatt, in dem der Wert abgelegt werden muss. Wir unterscheiden zwei Fälle:

• Fall 1: Das Blatt hat noch nicht die maximale Anzahl m − 1 von Schlüsseln gespeichert.

  Dann fügen wir den Wert entsprechend der Sortierung ein.

• Fall 2: Das Blatt hat bereits die maximale Anzahl m − 1 von Schlüsseln gespeichert.

  In diesem Fall ordnen wir den Wert wie im Fall 1 entsprechend seiner Größe ein und teilen anschließend den zu groß gewordenen Knoten in der Mitte auf. Das mittlere Element wird in den Vorgänger-Knoten eingefügt.

  Dieses Teilen wird solange längs des Suchpfades bis zur Wurzel fortgesetzt, bis ein Knoten erreicht ist, der noch nicht die maximale Anzahl von Schlüsseln speichert,

  oder bis die Wurzel erreicht wird.

  Muss die Wurzel geteilt werden, so schafft man eine neue Wurzel, die den mittleren Schlüssel als einzigen Schlüssel speichert.

Inorder: 1, 4, 5, 6, 8, 10, 11, 12, 16

Preorder: 8, 4, 1, 6, 5, 10, 12, 11, 16

Postorder: 1, 5, 6, 4, 11, 16, 12, 10, 8

Levelorder: 8, 4, 10, 1, 6, 12, 5, 11, 16

Strukturanpassung an unterschiedliche Zugriffshäufigkeiten:

• Oft angefragte Schlüssel werden in Richtung Wurzel bewegt.

• Selten angefragte Schlüssel wandern zu den Blättern hinab.

• Die Zugriffshäufigkeiten sind vorher nicht bekannt.

Sei T ein Suchbaum und x ein Schlüssel. Dann ist splay(T,x) der Suchbaum, den man wie folgt erhält:

• Schritt 1: Suche nach x in T. Sei p der Knoten, bei dem die erfolgreiche Suche endet, falls x in T vorkommt. Ansonsten sei p der Vorgänger des Blattes, an dem die Suche nach x endet, falls x nicht in T vorkommt.

• Schritt 2: Wiederhole die Operationen zig (einzelne Rotation), zig-zig (zwei Rotationen in die gleiche Richtung) und zig-zag (zwei Rotationen in entgegengesetzte Richtungen) beginnend bei p solange, bis sie nicht mehr ausführbar sind, weil p Wurzel geworden ist.

• Kommt x in T vor, so erzeugt splay(T,x) einen Suchbaum, der den Schlüssel x in der Wurzel speichert.

• Kommt x nicht in T vor, so wird der in der symmetrischen Reihenfolge dem Schlüussel x unmittelbar vorangehende oder unmittelbar folgende Schl¨ussel zum Schlüssel der Wurzel

Um x in T einzufügen, rufe splay(T,x) auf. Ist x nicht in der Wurzel, so füge wie folgt eine neue Wurzel mit x ein. Beachte obige zweite Aussage: Kommt x nicht in T vor, so wird der in der symmetrischen Reihenfolge dem Schlüssel x unmittelbar vorangehende oder

unmittelbar folgende Schlüssel zum Schlüssel der Wurzel.

• Falls der Schlüssel der Wurzel von T kleiner als x ist

Falls der Schlüssel der Wurzel von T größer als x ist:

Ein gerichteter Graph G = (V, E) besteht aus

• einer endlichen Menge von Knoten V = {v1, . . . , vn} und

• einer Menge von gerichteten Kanten E ⊆ V × V .

Bei einem ungerichteten Graphen G = (V, E) sind die Kanten ungeordnete Paare:

E ⊆ {{u, v} | u, v ∈ V, u̸ = v}

Sei G = (V, E) ein gerichteter Graph und seien u, v ∈ V . Dann ist p = (v0, v1, . . . , vk) ein gerichteter Weg in G der Länge k von Knoten u nach Knoten w, falls gilt: v0 = u, vk = w und (vi−1, vi) ∈ E f¨ur 1 ≤ i ≤ k.

Der Weg p ist einfach, wenn kein Knoten mehrfach vorkommt.

Oder: Sei G = (V, E) ein ungerichteter Graph und seien u, v ∈ V . p = (v0, v1, . . . , vk) ist ein ungerichteter Weg in G der Länge k von Knoten u nach Knoten w, falls gilt: v0 = u, vk = w

und {vi−1, vi} ∈ E f¨ur 1 ≤ i ≤ k.

Die Graphen G1 und G2 sind Teilgraphen von G, aber G1 und G2 sind keine induzierten Teilgraphen von G, da in G1 die Kanten (6, 1) und (5, 7) fehlen und in G2 bspw. die Kanten (1, 7) und (7, 2) fehlen

• Ein Graph G′ = (V ′, E′) ist ein Teilgraph von G, geschrieben G′ ⊆ G, falls V ′ ⊆ V und E′ ⊆ E.

• Für einen induzierten Teilgraphen G′ von G fordern wir zusätzlich, dass eine Kante e = (u, v) ∈ E mit u, v ∈ V ′, bei der also Start- und Endknoten in V ′ liegen, auch im Teilgraphen G′ vorhanden ist.

Die einfache Tiefensuche soll alle von einem gegebenen Startknoten s aus erreichbaren Knoten finden.

Zunächst werden die globalen Variablen dfbZähler und dfeZähler mit 0 initialisiert. Außerdem werden alle Knoten als unbesucht markiert. Die rekursive Funktion dfs ist wie folgt definiert.

markiere u als ”besucht“

dfb[u] := dfbZähler

dfbZähler := dfbZähler + 1

betrachte alle Kanten (u, v) ∈ E:

falls Knoten v als ”unbesucht“ markiert ist:

dfs(v)

dfe[u] := dfeZähler

dfeZ¨ahler := dfeZähler + 1

Für einen Graphen G = (V, E) beträgt die Laufzeit O(|V | + |E|).

• Da die Knoten markiert werden und bereits besuchte Knoten nicht zweimal besucht werden, werden maximal alle |V | Knoten besucht.

• Da die zu einem Knoten inzidenten Kanten aufgrund der Markierung der Knoten auch nur einmal (bei gerichteten Graphen) oder zweimal (bei ungerichteten Graphen) betrachtet werden, ergibt sich in Summe die

  Laufzeit O(|V | + |E|).

Hinweis: Für die Klausur ist auch die Breitensuche relevant.

• Baumkante: Kante, der die Tiefensuche folgt.

• Vorwärtskante: Kante (u, v) ∈ E mit dfb[v] > dfb[u], die aber keine Baumkante ist.

• Querkante: Eine Kante (u, v) ∈ E mit dfb[v] < dfb[u] und dfe[v] < dfe[u].

• Rückwärtskante: Kante (u, v) ∈ E mit dfb[v] < dfb[u] und dfe[v] > dfe[u].

Es entfallen die Querkanten und die Vorw¨artskanten.

• Querkanten existieren nicht, da dfs(u) innerhalb von dfs(v) aufgerufen würde, siehe obige grafische Darstellung.

• Vorwärtskanten existieren nicht, weil bei dfs(v) die Kante {v, u} als Rückwärtskante entdeckt würde: df b[v] > df b[u] und df e[v] < df e[u].

Es gibt also nur Baum- und R¨uckw¨artskanten bei einer Tiefensuche auf ungerichteten Graphen

Kreise können mittels einer Tiefensuche (nicht die einfache Tiefensuche) gefunden werden. ( Überlegen Sie sich, warum eine einfache Tiefensuche nicht ausreichend ist.)

markiere alle Knoten als unbesucht

solange ein unbesuchter Knoten v existiert:

dfs(v)

Satz: Ein gerichteter Graph G enthält genau dann einen Kreis, wenn die Tiefensuche auf G eine Rückwärtskante liefert.

• Gegeben: Ein gerichteter Graph G = (V, E).

• Gesucht: Eine Nummerierung π(v1), . . . , π(vn) der Knoten, sodass gilt:(u, v) ∈ E ⇒ π(u) > π(v)

Algorithmus: Tiefensuche

G ist kreisfrei ⇒ dfe-Nummern sind topologische Sortierung!

Hinweis: Es reicht nicht aus, so etwas wie ”Der Knoten mit der größten Nummer hat keine

einlaufende Kante.“ zu schreiben.

Was ist denn mit den anderen Knoten?

Haben die einlaufende Kanten oder nicht?

Und falls ja, von welchen Knoten?

Es reicht auch nicht aus, nur zu schreiben, dass die dfe-Nummern einer Tiefensuche eine topologische Sortierung festlegen. Denn das gilt nur für kreisfreie Graphen.

Ein Baum ist ein zusammenhängender, kreisfreier Graph. Ein Spannbaum T = (V, ET ) eines Graphen G = (V, E) ist ein Baum, der jeden Knoten aus V enthält. Ein solcher Baum besteht aus |V | − 1 Kanten. Die Kosten eines Spannbaums sind definiert als

Ein minimaler Spannbaum ist ein Spannbaum mit minimalen Kosten unter allen möglichen Spannbäumen des Graphen.

Beweis durch Widerspruch:

Wir nehmen an, dass kein minimaler Spannbaum die billigste Kante zwischen V1 und V2 enthält. Dann

entsteht durch Hinzunahme der billigsten Kante ein Kreis.

Durch streichen der teueren Kante zwischen V1 und V2 des Kreises entsteht wieder ein Spannbaum, dessen Gewicht sogar geringer ist als der ursprüngliche Spannbaum

Sei Q eine Datenstruktur (Priority Queue) zum Speichern von Knoten. Die Knoten sind mit den Kantenwerten gewichte

Sei G = (V, E, c) ein ungerichteter Graph mit Kostenfunktion c : E → R+

Nach Ablauf des Algorithmus enthält die Menge A die Kanten eines minimalen Spannbaums.

Variante: Anstelle des Sortierens können die Kanten auch in eine Priority-Queue Q eingefügt

werden, sortiert nach dem Gewicht der Kanten. Die Schleife ändert sich dann zu:

while (Q̸ = ∅)

(u, v) := minimum(Q)

extractMin(Q)

Insbesondere sollen die Funktionen findSet und union unterstützt werden. Daher wird die Datenstruktur Union-Find-Datenstruktur genannt. Sie unterstützt die Speicherung einer disjunkten Zerlegung einer Menge S = X1 ∪ X2 ∪ . . . ∪ Xk mit Xi ∩ Xj = ∅ für i̸ = j.

• Speichere jede Klasse Xi in einem Baum.

• Der Repräsentant einer Klasse Xi ist die Wurzel des Baums.

• Die Funktion findSet(v) liefert den Repräsentanten des Baums, in dem Knoten v gespeichert ist.

• Damit ein Knoten schnell gefunden werden kann, werden Zeiger auf alle Elemente v ∈ S gespeichert.

• Die Funktion union hängt den kleineren (bzw. flacheren) Baum an die Wurzel des größeren (bzw. tieferen) Baums an.

Die Kosten einer findSet-Operation sind abhängig von der Höhe der Bäume.

• Es wäre günstig, alle Knoten direkt an die Wurzel zu hängen. Das aber würde die union-Operation teurer machen als bisher.

• Stattdessen: Verkürze während der findSet-Operation die Pfadlängen. Die Pfadkomprimierung macht die findSet-Methode ungefähr doppelt so teuer wie vorher, die asymptotische Laufzeit bleibt gleich.

• Eine amortisierte Laufzeitanalyse liefert: Kruskals Algorithmus hat für alle praktischen Eingaben eine lineare Laufzeit. Dabei gehen wir davon aus, dass die Kanten bereits sortiert sind oder mittels Radix-Sort in linearer Zeit sortiert werden können.

Es werden alle kürzesten Wege von einem Startknoten aus gesucht (single source shortest paths).

Sei Q eine Datenstruktur (Priority Queue) zum Speichern von Knoten. Die Knoten sind mit Distanzwerten gewichtet. Wichtig: Die Kantengewichte dürfen nicht negativ

sein!

Jeder Teilweg eines kürzesten Weges ist ebenfalls ein kürzester Weg. Betrachten wir einen kürzesten Weg (v0, v1, v2, . . . , vk) von v0 nach vk.

Dann ist jeder Teilweg von vi nach vj für i < j auch ein kürzester Weg von vi nach v

Cut and paste: Gäbe es einen kürzeren Weg von vi nach vj , dann könnte auch der Weg von v0 nach vk verkürzt werden.

single source shortest paths

Antwort:

• Die äußere Schleife wird (V − 1)-mal durchlaufen.

• Die innere Schleife wird E-mal durchlaufen.

• Alle Operationen der inneren Schleife kosten Zeit O(1).

→ Gesamte Laufzeit in Θ(V · E).

Ein kürzester Weg, der keine negativen Kreise enthält, besucht keinen Knoten zweimal. Daher besteht ein solcher Weg aus höchstens V − 1 Kanten.

Der Graph G enthalte keine negativen Kreise.

• Sei v ∈ V ein beliebiger Knoten, und betrachte einen kürzesten Weg p von s nach v mit minimaler Anzahl Kanten.

• Initial gilt: d[v0] = 0 = δ(s, v0)

• Wir betrachten die Durchl¨aufe der ¨außeren Schleife:

  • nach 1. Durchlauf durch E gilt: d[v1] = δ(s, v1).

  • nach 2. Durchlauf durch E gilt: d[v2] = δ(s, v2).

  • ...

  • nach k. Durchlauf durch E gilt: d[vk] = δ(s, vk).

• Ein kürzester Weg besteht aus höchstens V − 1 Kanten

Mittels dynamischer Programmierung all-pairs-shortest-path berechnen.

Sei dk ij die Länge eines kürzesten Weges von i nach j, der nur über Knoten mit Nummern kleiner gleich k läuft.

Dann gilt:

Weil es nicht funktioniert, da die kürzesten Wege nicht erhalten bleiben, wie folgendes Beispiel zeigt

• Der kürzeste Weg zwischen Startknoten s und Zielknoten z ist jeweils grün markiert.

• Links ist der Originalgraph zu sehen, im rechten Graphen wurde auf jedes Kantengewicht

der Wert 4 addiert.