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

Aus VoWi
Zur Navigation springen Zur Suche springen

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

Stable Matching[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

Selectionsort[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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)[Bearbeiten]

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)[Bearbeiten]

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[Bearbeiten]

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

Zusammenhang in gerichteten Graphen[Bearbeiten]

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[Bearbeiten]

Dijkstra-Algorithmus[Bearbeiten]

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]+le)

Heap[Bearbeiten]

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.

Ebenweise 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[Bearbeiten]

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[Bearbeiten]

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

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

Minimaler Spannbaum[Bearbeiten]

(Minimum Spanning Tree, MST)

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

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

Zwischenstopps auswählen[Bearbeiten]

Divide-and-Conquer[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

Dichtestes Punktpaar[Bearbeiten]

Suchbäume[Bearbeiten]

  • 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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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

AVL-Bäume[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

  • 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[Bearbeiten]

  • 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