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

From VoWi
Jump to navigation Jump to search

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

Stable Matching[edit]

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

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

" ist eine obere Schranke von ."

" ist eine untere Schranke von ."

" ist eine scharfe Schranke von ."

Additivität
(analog für Θ und Ω)
Transitivität
(analog für Θ und Ω)

Laufzeiten einiger gebräuchlicher Funktionen[edit]

Laufzeit Notation Beispiele
konstant
logarithmisch binäre Suche
linear Maximumsuche, merge two sorted lists to one sorted
n log n Mergesort
quadratisch
kubisch
polynomiell
exponentiell
Polynomialzeit
Es existiert eine Konstante , sodass die Laufzeit in liegt.

Sortieren als praktisches Beispiel[edit]

Selectionsort[edit]

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

Wikipedia, worst, best & average-case: , 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[edit]

Füge unsortiertes Element an der richtigen Stelle ein.

Wikipedia, worst-case: , best-case: , average-case: , 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[edit]

G = (V,E)

n=|V|, m=|E|

Adjazenzmatrix Adjazenzliste
Platzbedarf
Laufzeit adjazent
Aufzählen aller Kanten
  • Pfade und Zusammenhang
  • Kürzeste Pfade und Distanz
  • Kreis
  • Baum
    • Wurzelbaum

Breitensuche (BFS)[edit]

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:

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

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

Wikipedia, worst case:

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

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

Zusammenhang in gerichteten Graphen[edit]

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

Dijkstra-Algorithmus[edit]

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

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:
  • Elternknoten
Erstellen aus Array
Einfügen

Element wird an Position 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

Element an Stelle 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[edit]

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

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

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

Minimaler Spannbaum[edit]

(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[edit]

Divide-and-Conquer[edit]

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

, 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[edit]

best & average: , instabil

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

Inversionen zählen[edit]

Dichtestes Punktpaar[edit]

Suchbäume[edit]

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

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

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

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

AVL-Bäume[edit]

Wikipedia

  • Höhe linker Unterbaum
  • Höhe rechter Unterbaum
balanciert
Rebalancierung
Rotation nach rechts
Doppelrotation links-rechts
Rotation nach links
Doppelrotation rechts-links

B-Bäume und B*-Bäume[edit]

Wikipedia

B-Baum der Ordnung
  1. Blätter haben gleiche Tiefe und sind leere Knoten.
  2. Jeder Knoten hat bis zu Kinder.
  3. Jeder innere Knoten außer der Wurzel hat mindestens Kinder. Die Wurzel hat mindestens 2 Kinder.
  4. Jeder Knoten mit Schlüssel hat Kinder.
  5. Für jeden Knoten mit Schlüsseln und Kindern gilt: :
    • Alle Schlüssel in sind kleiner gleich
    • ist kleiner gleich allen Schlüsseln in
    ( bezeichnet den Teilbaum mit Wurzel )

B-Bäume wachsen immer an der Wurzel.

Hashing[edit]

  • Hashfunktion
    • Divisions-Rest-Methode (m idealerweise prim)
    • Multiplikationsmethode , (A ist irrational)
  • Kollisionsbehandlung
    • Verkettung der Überläufer: Jedes Element der Hashtabelle ist eine verkettete Liste
    • offene Hashverfahren (Flag )
      lineares Sondieren
      quadratisches Sondieren
      Double Hashing
      Verbesserung nach Brent

Wahrscheinlichkeit für einen bestimmten Platz in der Hastabelle

Datenstrukturen in Java[edit]

  • 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