TU Wien:Algorithmen und Datenstrukturen VU (Szeider)/Zusammenfassung Test 1

Es gibt auch eine Zusammenfassung für den Stoff vom 2. Test.

Stable Matching

Gale-Shapley-Algorithmus

Pseudocode

Kennzeichne jede Familie/jedes Kind als frei
while ein Kind ist frei und kann noch eine Familie auswählen
    Wähle solch ein Kind s aus
    f ist erste Familie in der Präferenzliste von s,
    die s noch nicht ausgewählt hat
    if f ist frei
        Kennzeichne s und f als einander zugeordnet
    elseif f bevorzugt s gegenüber ihrem aktuellen Partner s'
        Kennzeichne s und f als einander zugeordnet und s' als frei
    else
        f weist s zurück

Algorithmenanalyse

Von der LVA-Leitung wurde ein Aufgabenblatt zum Üben der Algorithmenanalyse hochgeladen: Aufgabenblatt Algorithmenanalyse.pdf. Lösungen: Aufgabenblatt Algorithmenanalyse mit Lösungen.pdf.

Instanz

Eine Eingabe wird auch als Instanz des Problems, das durch den Algorithmus gelöst wird, bezeichnet.

• worst-case
• average-case
• best-case

Asymptotisches Wachstum

$f(n)=O(g(n))$ "$g(n)$ ist eine obere Schranke von $f(n)$."

$O(g(n))=\{f(n)\mid \exists \ c>0\ \exists \ n_{0}>0\ \forall \ n\geq n_{0}:f(n)\leq c\cdot g(n)\}$

$f(n)=\Omega (g(n))$ "$g(n)$ ist eine untere Schranke von $f(n)$."

$\Omega (g(n))=\{f(n)\mid \exists \ c>0\ \exists \ n_{0}>0\ \forall \ n\geq n_{0}:c\cdot g(n)\leq f(n)\}$

$f(n)=\Theta (g(n))$ "$g(n)$ ist eine scharfe Schranke von $f(n)$."

$\Theta (g(n))=\{f(n)\mid \exists \ c_{1}>0\ \exists \ c_{2}>0\ \exists \ n_{0}>0\ \forall \ n\geq n_{0}:c_{1}\cdot g(n)\leq f(n)\leq c_{2}\cdot g(n)\}$

Additivität

$f=O(h)\land g=O(h)\Rightarrow f+g=O(h)$ (analog für Θ und Ω)

Transitivität

$f=O(g)\land g=O(h)\Rightarrow f=O(h)$ (analog für Θ und Ω)

Laufzeiten einiger gebräuchlicher Funktionen

Laufzeit	Notation	Beispiele
konstant	$O(1)$
logarithmisch	$O(\log n)$	binäre Suche
linear	$O(n)$	Maximumsuche, merge two sorted lists to one sorted
n log n	$O(n\log n)$	Mergesort
quadratisch	$O(n^{2})$
kubisch	$O(n^{3})$
polynomiell	$O(n^{k})$
exponentiell	$O(c^{n})$

Polynomialzeit

Es existiert eine Konstante $d\geq 1$, sodass die Laufzeit in $O(n^{d})$ liegt.

Sortieren als praktisches Beispiel

Selectionsort

Suche kleinstes unsortiertes Element und tausche es mit dem ersten Unsortierten.

Wikipedia, worst, best & average-case: $O(n^{2})$, instabil

Pseudocode

Selectionsort(A):
for i ← 0 bis n − 2
    smallest ← i
    for j ← i + 1 bis n − 1
    if A[j] < A[smallest]
            smallest ← j
    Vertausche A[i] mit A[smallest]

Insertionsort

Füge unsortiertes Element an der richtigen Stelle ein.

Wikipedia, worst-case: $O(n^{2})$, best-case: $O(n)$, average-case: $O(n^{2})$, stabil

Pseudocode

Insertionsort(A):
for i ← 1 bis n − 1
    key ← A[i], j ← i − 1
    while j ≥ 0 und A[j] > key
        A[j + 1] ← A[j]
        j ← j − 1
    A[j + 1] ← key

Graphen

G = (V,E)

n=|V|, m=|E|

	Adjazenzmatrix	Adjazenzliste
Platzbedarf	$\Theta (n^{2})$	$\Theta (m+n)$
Laufzeit adjazent	$\Theta (1)$	$\Theta (\deg(v))$
Aufzählen aller Kanten	$\Theta (n^{2})$	$\Theta (m+n)$

• Pfade und Zusammenhang
• Kürzeste Pfade und Distanz
• Kreis
• Baum
  • Wurzelbaum

Breitensuche (BFS)

Speichere Nachbarknoten in einer Queue, falls sie noch nicht entdeckt wurden. Wiederhole dies für alle Knoten in der Queue bis sie leer ist / der gesuchte Knoten gefunden wurde.

Wikipedia, worst case: $O(|V|+|E|)$

Pseudocode

BFS(Graph, Start):
Discovered[v] ← false für alle Knoten v ∈ V
Discovered[s] ← true
Q ← {Start}
while Q ist nicht leer
    Entferne ersten Knoten u aus Q
    Führe Operation auf u aus
    foreach Kante (u,v) inzident zu u
        if !Discovered[v]
            Discovered[v] ← true
            Füge v zu Q hinzu

Tiefensuche (DFS)

Rekursiver Aufruf für jeden Nachbarknoten, der noch nicht besucht wurde.

Wikipedia, worst case: $O(|V|+|E|)$

Pseudocode

DFS(Graph, Start):
Discovered[v] ← false für alle Knoten v ∈ V
DFS1(Graph, Start)

DFS1(Graph, u):
Discovered[u] ← true
Führe Operation auf u aus
foreach Kante (u,v) inzident zu u
    if !Discovered[v]
        DFS1(G, v)

Zusammenhangskomponente

Ein maximaler zusammenhängender Teilgraph. Ein nicht zusammenhängender Graph zerfällt in seine Zusammenhangskomponenten.

Zusammenhang in gerichteten Graphen

starker Zusammenhang

jedes Paar von Knoten ist gegenseitig erreichbar

schwacher Zusammenhang

jedes Paar von Knoten ist unter Misachtung der Kantenrichtung von einander erreichbar

DAGs und topologische Sortierung

• Gerichteter azyklischer Graph (Directed Acyclic Graph, DAG)
• Topologische Sortierung

Dijkstra-Algorithmus

Pseudocode

Dijkstra(G,s):
Discovered[v] ← false für alle Knoten v ∈ V
d[s] ← 0
d[v] ← ∞ für alle anderen Knoten v ∈ V \ {s}
L ← V
while L ist nicht leer
    wähle u ∈ L mit kleinstem Wert d[u]
    lösche u aus L
    Discovered[u] ← true
    foreach Kante e = (u,v) ∈ E
        if !Discovered[v]

d[v] ← min(d[v],d[u]+l_e)

Heap

Ein Heap (Min-Heap) ist ein binärer Wurzelbaum, dessen Knoten mit ≤ total geordnet sind, sodass gilt:

• Ist u ein Kind von v, dann gilt v ≤ u (Heap-Eigenschaft für Min-Heap).
• Alle Ebenen von Knoten bis auf die letzte sind vollständig aufgefüllt.
• Die letzte Ebene des Baumes ist linksbündig aufgefült.

Ebenenweise Speicherung in Array (index 0 freigelassen):

• Nachfolgerknoten: $2k,2k+1$
• Elternknoten $\lfloor {\tfrac {k}{2}}\rfloor$

Erstellen aus Array $O(n)$

Einfügen $O(\log n)$

Element wird an Position $n+1$ eingefügt.

Heapify-up(H,i)

if i > 1
    j ← ⌊i/2⌋
    if H[i] < H[j]
        Vertausche die Array-Einträge H[i] und H[j]
        Heapify-up(H,j)

Löschen $O(\log n)$

Element an Stelle $n$ wird auf gelöschte Stelle verschoben.

Heapify-down(H,i)

n ← length(H)-1
if 2 · i > n
    return
elseif 2 · i < n
    left ← 2 · i, right ← 2 · i + 1
    j ← Index des kleineren Wertes von H[left] und H[right]
else
    j ← 2 · i
if H[j] < H[i]
    Vertausche die Arrayeinträge H[i] und H[j]
    Heapify-down(H,j)

Greedy-Algorithmen

Erstelle inkrementell eine Lösung, bei der nicht vorausschauend ein lokales Kriterium zur Wahl der jeweils nächsten hinzuzufügenden Lösungskomponente verwendet wird.

Interval Scheduling

Ziel: Finde eine Teilmenge maximalen Gewichts von paarweise kompatiblen Jobs.

Sortierungsmöglichkeiten:

• früheste Startzeit
• früheste Beendigungszeit
• kleinstes Intervall
• wenigste Konflikte

Dabei hat sich erwiesen, dass eine Sortierung nach frühester Beendigungszeit am ehesten zu einem globalen Optimum führt.

Minimaler Spannbaum

(Minimum Spanning Tree, MST)

• Algorithmus von Prim

Pseudocode

Annahme: Alle Kantengewichte sind unterschiedlich.

Prim(G, c):
foreach (v ∈ V )
    A[v] ← ∞
Initialisiere eine leere Priority Queue Q
foreach (v ∈ V )
    Füge v in Q ein
S ← ∅
while Q ist nicht leer
    u ← entnehme minimales Element aus Q
    S ← S ∪ {u}
    foreach Kante e = (u, v) inzident zu u
         if v ∉ S und ce < A[v]
             Verringere die Priorität A[v] auf ce

• Algorithmus von Kruskal
• Union-Find-Struktur

Prim ist besser für dichte Graphen und Kruskal ist besser für dünne Graphen.

Divide-and-Conquer

Teile ein Problem in Teilprobleme auf. Löse jedes Teilproblem unabhängig und kombiniere die Lösung für die Teilprobleme zu einer Lösung für das ursprüngliche Problem.

Mergesort

$O(n\log n)$, stabil

1. Teile Array in zwei Hälften.
2. Sortiere jede Hälfte rekursiv.
3. Verschmelze zwei Hälften zu einem sortierten Ganzen.

Pseudocode

Merge(A,l,m,r):
i ← l, j ← m + 1, k ← l
while i ≤ m und j ≤ r
    if A[i] ≤ A[j]
        B[k] ← A[i], i ← i + 1
    else
        B[k] ← A[j], j ← j + 1
    k ← k + 1
if i > m
    for h ← j bis r
        B[k] ← A[h], k ← k + 1
else
    for h ← i bis m
        B[k] ← A[h], k ← k + 1
for h ← l bis r
    A[h] ← B[h]

Quicksort

best & average: $O(n\log n)$, instabil

Wähle ein Pivotelement $x$, teile die Liste in zwei Teillisten, die linke enthält Elemente $\leq x$, die rechte Elemente $\geq x$. Sortiere die Teillisten rekursiv.

Inversionen zählen

Brute-Force-Ansatz: Überprüfe alle Paare i und j. Falls i > j -> Inversion.

                   Laufzeit O(n^2)

Divide-and-Conquer: 1) Teile Liste in zwei Teile. -> O(1)

                   2) Zähle rekursiv die Anzahl der Inversionen in jeder Hälfte. (links und rechts) -> 2T(n/2)
                   3) Combine: Inversionen von linke Hälfte + Inversionen von rechte Hälfte + Inversionen linke-rechte Hälfte. 

z.B. [3, 1, 4, 10, 5, 2]

    1) Teile: [3, 1, 4]   [10, 5, 2]
    2) Inversionen auf linke Hälfte: {(3-1)} => 1 Inversionen
       Inversionen auf rechte Hälfte: {(10-5, 10-2, 5-2)} => 3 Inversionen
    3) Linke-rechte Hälfte: {(3-2), (4-2)}
       Gesamt: 1 + 3 + 2 = 6   

Laufzeit: O(n * log(n))

Suchbäume

• Einfügen eines neuen Elements
• Suche eines Elements
• Entfernen eines Elements
• Durchlaufen aller Elemente in geordneter Reihenfolge
• Finden des kleinsten / größten Elements
• Finden eines nächstkleineren / nächstgrößeren Elements

Durchmusterungen (Traversals)

• Inorder: linker Unterbaum, Wurzel, rechter Unterbaum
• Preorder: Wurzel, linker Unterbaum, rechter Unterbaum
• Postorder: linker Unterbaum, rechter Unterbaum, Wurzel

Wurzelbäume

Tiefe (Niveau) eines Knotens

Anzahl der Kanten auf dem Pfad von der Wurzel zum Knoten

Blatt

Ein Knoten, wenn er keine Kinder besitzt, ansonsten innerer Knoten.

Binäre Suchbäume

binäre Suchbaumeigenschaft

Für jeden Knoten gilt: alle Knoten im linken Teilbaum haben einen kleineren Schlüssel, alle Knoten im rechten Teilbaum einen größeren Schlüssel.

Balancierte Bäume

• höhenbalanciert (AVL)
• gewichtsbalanciert
• (a,b)-Baum (2 ≤ a ≤ b)

AVL-Bäume

Wikipedia

$\mathrm {bal} (v)=h_{2}-h_{1}$

• $h_{1}$ Höhe linker Unterbaum
• $h_{2}$ Höhe rechter Unterbaum

balanciert

$\mathrm {bal} (v)\in \{-1,0,1\}$

Rebalancierung

$\mathrm {bal} (u)=-2,\mathrm {bal} ({\text{left}})\in \{-1,0\}$	Rotation nach rechts
$\mathrm {bal} (u)=-2,\mathrm {bal} ({\text{left}})=1$	Doppelrotation links-rechts
$\mathrm {bal} (u)=2,\mathrm {bal} ({\text{right}})\in \{1,0\}$	Rotation nach links
$\mathrm {bal} (u)=2,\mathrm {bal} ({\text{right}})=-1$	Doppelrotation rechts-links

B-Bäume und B*-Bäume

Wikipedia

B-Baum der Ordnung $m$

1. Blätter haben gleiche Tiefe und sind leere Knoten.
2. Jeder Knoten hat bis zu $m$ Kinder.
3. Jeder innere Knoten außer der Wurzel hat mindestens $\lceil {\tfrac {m}{2}}\rceil$ Kinder. Die Wurzel hat mindestens 2 Kinder.
4. Jeder Knoten mit $l$ Schlüssel hat $l+1$ Kinder.
5. Für jeden Knoten mit Schlüsseln $s_{1},\dots ,s_{l}$ und Kindern $v_{0},\dots ,v_{l}$ gilt: $\forall i=1,\dots ,l$:
   • Alle Schlüssel in $T_{v_{i-1}}$ sind kleiner gleich $s_{i}$
   • $s_{i}$ ist kleiner gleich allen Schlüsseln in $T_{v_{i}}$

   ($T_{v_{i}}$ bezeichnet den Teilbaum mit Wurzel $v_{i}$)

B-Bäume wachsen immer an der Wurzel.

Hashing

• Hashfunktion
  • Divisions-Rest-Methode $h(k)=k\ {\bmod {\ }}m$ (m idealerweise prim)
  • Multiplikationsmethode $h(k)=\lfloor m(k\cdot A-\lfloor k\cdot A\rfloor )\rfloor$, (A ist irrational)
• Kollisionsbehandlung
  • Verkettung der Überläufer: Jedes Element der Hashtabelle ist eine verkettete Liste
  • offene Hashverfahren (Flag $f_{i}\in \{{\text{frei}},{\text{besetzt}},{\text{wieder frei}}\}$)

    lineares Sondieren

    $h(k,i)=(h'(k)+i)\ {\bmod {\ }}m$

    quadratisches Sondieren

    $h(k,i)=(h'(k)+c_{1}i+c_{2}i^{2})\ {\bmod {\ }}m$

    Double Hashing

    $h(k,i)=(h_{1}(k)+ih_{2}(k))\ {\bmod {\ }}m$

    Verbesserung nach Brent

    $j_{1}=(j+h_{2}(k))\ {\bmod {\ }}m$

    $j_{2}=(j+h_{2}(k'))\ {\bmod {\ }}m$

Wahrscheinlichkeit für einen bestimmten Platz in der Hastabelle

Datenstrukturen in Java

• Collection: verwaltet Objekte, wird nicht direkt implementiert
  • Set: Collection ohne duplizierte Elemente
    • SortedSet:
  • List: Collection, die über den Index geordnet ist. Dupliziere Elemente sind gestattet.
  • Queue: Verwaltung von Warteschlangen
    • Dequeue: (double ended queue) Einfügen und Löschen von Elementen nur am Anfang und am Ende der Queue möglich
• Map: Verwaltung von Schlüsseln
  • SortedMap: Elemente werden in aufsteigender Reihenfolge verwaltet.

TimSort: Kombi aus Merge und Insertionsort