DSAL Rossmanith Wikiskript/Zusammenfassung

Aus Infostudium Wiki

Dieser Artikel soll in Zukunft noch erweitert bzw. überarbeitet werden. Dies soll aber nicht als Reservierung aufgefasst werden. Mitarbeit ist erwünscht.

Algorithmen

Graphalgorithmen

Minimale Spannbäume

Algorithmus von Prim (Alle Knoten auf Unendlich setzen, immer die Kante mit der geringsten Gewichtung auswählen; alle Knoten müssen berührt werden)
Algorithmus von Kruskal (Kanten nach geringsten Gewichtung sortiert ohne einen Kreis zu schließen auswählen; alle Knoten müssen berührt werden)

Starke Zusammenhangskomponenten

Algorithmus von Kosaraju (Berechnung starker Komponenten: Wege umdrehen, Tiefensuche, Wege umdrehen, mit höchster finish-time anfangen). Laufzeit: O(|V| + |E|)

Kürzeste Pfade

Single Source (ungewichtet)

Breitensuche (Aktive Knoten auf FIFO-Queue)

Single Source (gewichtet)

Dijkstra-Algorithmus (Alle Knoten auf Unendlich setzen, Addition der Gewichte der Kanten schrittweise vom Ausgangspunkt (Unterscheid zum Prim), hohe berechnete Knotenwerte durch geringere ersetzen wenn möglich) O((|V|+|E|)*log |V|)
Spezialfall für azyklische Graphen: Relaxieren in topologischer Reihenfolge, Priority Queue fällt weg, dadurch O(|V|+|E|)
Bellman-Ford (Eignet sich auch für negative Kantengewichtung. Erweiterung vom Dijkstra. Spürt negative Zyklen auf) |V|-1 mal wird jede Kante relaxiert. Gibt es danach immer noch Verbesserungsmöglichkeiten, so existiert ein negativer Kreis im Graph O(|V| * |E|)

All Pairs (gewichtet)

Floyd: Wir schauen für jeden Knoten k, ob wir über diesen Knoten einen kürzeren Weg von i nach j finden für alle i und j => O(|V|^3)

Hilfsmittel

Union-Find( Rangheuristik: kleinere Bäume werden immer an die Wurzel von größeren drangehangen; Pfadkompression: beim Ausführen von find(x) wird x an die Wurzel seines Baumes gehängt um später schneller gefunden zu werden

Sortieralgorithmen

Name	Beschreibung	Laufzeit	in-place	stabil
Quicksort	Divide-and-Conquer-Prinzip, Per Pivot-Element teilen, sortieren und rekursiv wiederholen	O(n log n)	ja	nein
HeapSort	Manuelle Sortierung durch Baum-Darstellung, Einfügen und Löschen durch Anhängen und Aufsteigen bzw. Vertauschung durch letztes Element und Hinuntersinken	O(n log n)	ja
InsertionSort	Vorne wird ein sortiertes Teilarray gebildet, worin sortiert aus dem hinteren eingefügt wird	O(n^2)	ja
MergeSort	Divide-and-Conquer-Prinzip, mittig trennen, Teilmengen jeweils sortieren, Teilmengen sortiert verschmelzen. So auch der Programmcode aufgebaut.	O(n log n)	nein	ja
RadixSort

Graphische Algorithmen

Sweepline-Algorithmus: Elemente nach X-Koordinate sortieren, von links nach rechts durchgehen und Y-Koordinate in aktive Menge aufnehmen, je nach Problemstellung Vergleiche ausführen
Nächste-Nachbarn: Elemente nach X-Koordinate ordnen, teile in linke und rechte Hälfte, finde rekursive Nachbarn links und rechts (Abstand d), bei Rekursinsrücksprung: finde nächste Nachbarn in einem Streifen der Breite 2d um die jeweilige Trennlinie, Laufzeit: O(log n)

String-Matching

Boyer-Moore: Strings von hinten vergleichen, bei Mismatch, Substring um delta(x) verschieben, delta ist eine Funktion die vorher bestimmt wird, Laufzeit: O(n/m) n-> Textlänge, m-> Substring-Länge
Rabin-Karp: Vergleiche der Strings mittels Hashwerten, gute Hashfunktion nötig

Bäume

Name	Beschreibung	Suchen	Einfügen	Löschen	Vereinigen	Aufsplitten	Speicherverbrauch
Binär-Baum	Standard Suchbaum	O(log n)	O(log n)	O(log n)
Splay Tree	nach Ausführen einer Operation wird splay-Operation ausgeführt (aktiver Knoten wird zur Wurzel hochrotiert), aufpassen bei zig-zig und zag-zag, Laufzeiten amortisiert	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)
Heap	min-Heap: Wurzel hat kleinsten Wert, alle Kinder haben größeren Wert als ihre Eltern; max-Heap umgekehrt	nicht so einfach, da keine Suchbaumeigenschaft	Neues Element am Ende einfügen und an die passende Stelle hochtauschen (nicht rotieren)	interessant: extract_min: Wurzel durch letztes Element ersetzen und dieses dann an passende Stelle runtertauschen
Treap	Üblichen Eigenschaften eines Suchbaumes + Heapeigenschaft	O(log n)	Als Blatt einfügen und an passende Stelle hochrotieren: O(log n)	runterrotieren am Kind mit kleinster Priorität bis Blatt, dann löschen: O(log n)
AVL-Baum	Die Höhen des rechten und linken Unterbaums jeden Knotens unterscheiden sich höchstens um 1	O(log n)	O(log n)	O(log n)
(a,b)-Baum	jeder Knoten höchstens b Kinder und jeder Knoten außer Wurzel mindestens a Kinder; alle Blätter haben gleiche Tiefe		als Blatt einfügen und eventuell (a,b)-Eigenschaft wiederherstellen	Blatt löschen und eventeull (a,b)-Eigenschaft wiederherstellen
Skip-List		O(log n)	O(log n)	O(log n)			O(n)

Netzwerkalgorithmen

Flüsse

Zulässigkeit
Symmetrie
Flußerhaltung

Augmentierte Pfade, Restkapazität

Ford–Fulkerson–Methode

Initialisiere das Netzwerk mit einem Fluss von 0.
Bestimme das Residualnetzwerk (Von den Kapazitäten den Fluss abziehen)
Gibt es im Residualnetzwerk einen augmentierenden Pfad, so bestimmen wir den Fluss, addieren ihn zu dem alten Fluss und machen bei 2 weiter. Sonst sind wir fertig, und der gefundene Fluss ist der maximale Fluss

Edmond-Karps–Methode

Die Ford Fulkerson-Methode kann beliebig schlecht sein, Edmond-Karps ist immer polynomiell zur Netzwerkgröße.

Ähnlich wie Ford-Fulkerson, nur dass wir immer den kürzesten augmentierenden Pfad nehmen

Schnitte

Kapazität, c(S,T)

Optimale Suchbäume

Schlüssel $k i$
Zugriffswahrscheinlichkeit für Knoten i

p i

Zugriffswahrscheinlichkeit für Teilbaum von i bis j

$w_{i,j} = \sum_{k=i}^j p_i$

Erwartungswert für Anzahl der Vergleiche im Teilbaum von i bis j

$e_{i,j} = \min_{i \le r \le j}\left(e_{i,r-1}+e_{r+1,j}\right)+w_{i,j}$

(Das

r

das wir wählen, um das Minimum zu erreichen, ist unsere Wurzel für den Teilbaum von i bis j)

Beispiel

Hashing

Lastfaktor alpha=Größe/Anzahl der Elemente -> Laufzeit/Amortisierte Kosten: O(alpha)
Rehashing

Unsortiert

Tiefensuche (DFS=Depth First Search); Aktive Knoten auf Stack

Starke Zusammenhangskomponente - Unterteilung eines gerichteten Graphen in Komponenten; von jedem Knoten in einer Komponente kann jeder andere Knoten in der selben Komponente erreicht werden.

Quellenkomponenten

Senkenkomponenten

discover/finish times

Landau-Notation: Alternative Definition

Vergleichsbaum

Topologische Sortierung (Tiefensuche) in O(|V| + |E|)

DAG (Gerichteter azyklischer Graph): Kürzeste Pfade hier in linearer Zeit

Rucksackproblem

Kanten

Baumkanten: Die beim DFS benutzten Kanten
Querkante: Eine Kante zwischen zwei DFS-Zyklen
Rückwärtskante: Eine Kante, die innerhalb eines Zyklus zu einem vorher besuchten Knoten (höhere finish-time) zeigt
Vorwärtskante: