Algorithmik mündlich
algo
algo
-
- 1 / 10
-
Lernkarten
Was berechnet der Dijkstra-Algorithmus im i-ten Schritt?
1.) \(B_0 = \{u\}\)
2.) Nach Schritt \(i\) ist \(B_i\) berechnet,so dass für jedes \(w \in B_i, d(u,w)\) und ein zugehöriger kürzester Pfad von \(u\) und \(w\) bekannt sind. Weiterhin gilt für alle \(w'\in B_i\) und alle \(z \in V\backslash B_i:d(u,w')\le d(u,z)\).
Was sucht Dijkstra im i-ten Schritt bei der Kante (x,y) für Eigenschaften?
- \((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)\)
Warum terminiert der Algorithmus von Dijkstra?
- 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
Laufzeit Dijkstra mit Prioritätswarteschlange und Fibonnaci-Heap.
\(\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}})\)
Wann heißt ein Graph G=(V,E) zusammenhängend?
Wenn je zwei Knoten durch einen Pfad verbunden sind.
Was ist ein Baum?
Ein Baum ist ein zusammenhängender, kreisfreier, ungerichteter Graph.
Wie viele Kanten besitzt ein Baum mit n Knoten? Warum?
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.
Was ist ein minimal aufspannender Baum?
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)\)
Warum benötigt jeder Sortieralgorithmus, welcher ausschließlich auf Schlüsselvergleiche basiert, im Mittel und im schlechtesten Fall \(\Omega(n \log(n))\) Vergleiche?
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.
Wie findet man den Median der Mediane in Linearzeit?
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)\)
