Algorithmik mündlich

• \((x\in B_{i_1}, y\notin B_{i-1})\)
• \(\forall (x',y')\in E: x' \in B_{i-1} \wedge y' \notin B_{i-1}: d(u.x) + \gamma(x,y) \le d(u,x') + \gamma(x',y')\)
• Nach diesem Schritt: \(B_i := B_{i-1}\cup \{ y \}\) und \(d(u,y)=d(u,x)+\gamma(x,y)\)

• Nach dem i-ten Durchlauf ist \(B=B_i\).
• Jeder Schritt vergrößert \(B_i\) und ernthält nu rdie vom Startknoten aus erreichbaren Knoten

\(\mathcal{O}(|V|^2+|E|)=\mathcal{O}(|V|^2)\)

und

\(\mathcal{O}(\underbrace{|E|}_{\text{Anzahl decrease-key}}+\underbrace{|V|}_{\text{Anzahl insert}}\underbrace{\log(|V|}_{\text{Anzahl delete_min}})\)

Wenn je zwei Knoten durch einen Pfad verbunden sind.

Ein Baum ist ein zusammenhängender, kreisfreier, ungerichteter Graph.

n - 1 Kanten

Beweis über Induktion:

IA: Ein Baum mit n=1 Knoten: 1-1=0

IS: n+1 Knoten:

Ein Baum mit n+1 Knoten ist ein Baum mit n Knoten und 1er Kanten angehängt. Nach Induktionsvorraussetzung hat der Baum n-1 Kanten + 1 angehängte Kante = n-1+1 = n

ISS: Behauptung ist wahr.

Ein Baum \(B=(V,F,\gamma|_F)\) mit \(F \subseteq E\) mit minimalen Gewicht, also \(\gamma(B):=\sum_{e \in F} \gamma(e)\) zu einem gewichteten Graphen \(G=(V,E,\gamma)\)

Fasst man den Sortieralgorithmus als Binärbaum auf, in der jeder Knoten einen Vergleich x[i]<x[j] darstellt, dann hat dieser Baum bei n Elementen (Schlüsseln) mindestens n! viele Blätter, da jede Permutation vorkommen kann. Die Laufzeit des Sortieralgorithmus ist die Mindesthöhe dieses Binärbaums, also log(n!), was asymptotisch widerrum \(\Omega(n \log(n))\) entspricht.

1. Teile in 5er Blöcke auf und bestimme aus diesen Medianen das Pivotelement mit Kosten \(T(n/5)\) (Median aus 5 ist mit 6 Vergleichen möglich.

2. Zerlege das Feld nach Pivot, dann ist die Hälfte der Median-Blöcke kleiner und die andere Hälfte größer als das Pivotelement. Aus diesen 5er Blöcken sind (inkl. Medianelement) 3 Elemente kleiner als das Pivotelement: Kosten von \(1/2 \cdot n/5 \cdot 3 = 3/10 \cdot n\). Folglich ist der größere Teil \(7/10 \ n\) groß, also  WC Kosten 7/10 n + Quicksortschritt O(n)

Nach Mastertheorem:

\(T(n)=T(n/5)+T(7/10\cdot n)+\Theta(n)\in \Theta(n)\)