Effiziente kombinatorische Algorithmen - Cheatsheet

Grundlegende Begriffe und Definitionen in der Graphentheorie

Definition:

Grundlagen der Graphentheorie: Definitionen von Graphen, Knoten, Kanten, Pfaden, Zyklen und Verbundenheit.

Details:

• Graph: bestehend aus Knotenmenge ( V ) und Kantenmenge ( E ).
• Knoten ( v ): Element aus V .
• Kante ( e ): Paar von Knoten ( u,v ).
• Pfad: Folge von Knoten, die benachbart sind.
• Kreis/Zyklus: Pfad, der zu seinem Anfangspunkt zurückkehrt.
• Verbundenheit: Graph ist verbunden, wenn jeder Knoten erreichbar.
• G wird geschrieben als ( V, E ).
• |V| : Anzahl der Knoten.
• |E| : Anzahl der Kanten.

Minimum-Spanning-Tree-Algorithmen: Kruskal und Prim

Definition:

Algorithmen zur Berechnung eines minimalen Spannbaumes (MST) in einem Graphen.

Details:

• Kruskal: Sortiere alle Kanten nach Gewicht und füge sie nacheinander hinzu, ohne Zyklen zu bilden, bis der MST vollständig ist.
• Prim: Beginne bei einem beliebigen Knoten und erweitere den MST schrittweise, indem die jeweils günstigste Kante hinzugefügt wird.
• Kruskal verwendet Union-Find für Effizienz.
• Prim bevorzugt Priority-Queue (Min-Heap) für Effizienz.
• Laufzeit Kruskal: O(E log E).
• Laufzeit Prim: O(E + V log V).

Algorithmische Techniken zur Graphfärbung

Definition:

Journalismus bezieht sich auf die Sammlung, Verfassung und Verbreitung von Nachrichten.

Details:

• Problem: Färbung der Knoten eines Graphen, sodass keine benachbarten Knoten dieselbe Farbe haben.
• Ziel: Minimierung der verwendeten Farben.
• Greedy-Algorithmus: Ordne Knoten in einer bestimmten Reihenfolge; weise jedem Knoten die erste verfügbare Farbe zu.
• DSATUR-Algorithmus: Dynamische Reihenfolge basierend auf dem Grad der Sättigung.
• Backtracking: Systematische Suche; Anwendung von Beschneidungsstrategien zur Effizienzsteigerung.
• Heuristiken: Größte Ausgangsgrad-Heuristik, kleinste Farb-Heuristik.
• NP-schwer: Optimale Graphfärbung kann in der Praxis nur für kleinere Graphen exakt gefunden werden.

Ford-Fulkerson-Algorithmus und Edmonds-Karp-Algorithmus

Definition:

Der Ford-Fulkerson-Algorithmus berechnet den maximalen Fluss in einem Flussnetzwerk. Der Edmonds-Karp-Algorithmus ist eine Implementierung des Ford-Fulkerson-Algorithmus, die BFS zur Suche von augmentierenden Pfaden verwendet.

Details:

• Ford-Fulkerson-Algorithmus: basiert auf der Idee, immer wieder augmentierende Pfade zu finden und den Fluss entlang dieser Pfade zu erhöhen
• Komplexität (Ford-Fulkerson): hängt von den Kapazitäten ab, im schlimmsten Fall unendlich
• Edmonds-Karp-Algorithmus: verwendet BFS zur Suche von augmentierenden Pfaden, garantiert Polynomialzeit
• Komplexität (Edmonds-Karp): O(VE^2), wobei V die Anzahl der Knoten und E die Anzahl der Kanten ist
• Residualgraph: Graph, der die verbleibenden Kapazitäten zur Darstellung des möglichen zusätzlichen Flusses zeigt
• Kapazitätserhöhung: cf(u,v) = c(u,v) - f(u,v)
• Optimale Lösung: Der maximale Fluss entspricht dem minimalen Schnitt im Netzwerk (Max-Flow Min-Cut Theorem)

Balanced Binary Trees: AVL und Rot-Schwarz-Bäume

Definition:

Selbstbalancierende Binärbäume zur effizienten Durchführung von Basisoperationen wie Einfügen, Löschen und Suchen.

Details:

• AVL-Bäume: Höhe der Teilbäume unterscheidet sich maximal um 1
• Rot-Schwarz-Bäume: Jeder Knoten ist entweder rot oder schwarz, zusätzliche Eigenschaften für Balancierung
• Einfügen und Löschen in \(O(\log n)\)
• Höhe eines AVL-Baums: \(O(\log n)\)
• Höhe eines Rot-Schwarz-Baums: \(2 \log (n+1)\)

Heaps und Priority Queues

Definition:

Heaps sind spezialisierte binäre Bäume, die die Heap-Eigenschaft erfüllen. Priority Queues verwenden Heaps, um Elemente effizient nach Priorität zu verwalten.

Details:

• Max-Heap: Elternknoten \textgreater \textgreater= Kindknoten
• Min-Heap: Elternknoten <= Kindknoten
• Insertion: O(log n)
• Extract Max/Min: O(log n)
• Implementation: in einer Liste/Array
• Priority Queues: Definieren, Einfügen, Entfernen

Lineare Programmierung und Simplex-Algorithmus

Definition:

Lineare Programmierung (LP) ist eine Methode zur Optimierung einer linearen Zielfunktion unter linearen Nebenbedingungen. Der Simplex-Algorithmus ist ein effizienter Algorithmus zur Lösung von LP-Problemen.

Details:

• Zielfunktion: \( z = c^T x \)
• Nebenbedingungen: \( Ax \leq b \) und \( x \geq 0 \)
• Grundlösung: \( x_B = A_B^{-1} b \)
• Schrittweise Verbesserung der Basislösung, um das Optimum zu finden
• Pivot-Operationen zur Änderung der Basis
• Dualität: Jeder LP hat ein duales Problem mit verwandter Struktur

Dynamische Programmierung für optimierende Lösungen

Definition:

Methode zur Zerlegung eines Problems in Teilprobleme und Speichern der Lösungen, um sie wiederzuverwenden.

Details:

• Verwendet bei Problemen mit überlappenden Teilproblemen
• Verbessert Effizienz durch Vermeidung mehrfacher Berechnungen
• Typische Anwendungen: Kürzeste Pfade, Sequenzalignment, Rucksackproblem
• Hauptansätze: Memoization und Bottom-Up
• Beispiel: Berechnung der Fibonacci-Zahlen
• Grundgerüst: Rekurrencegleichung, z.B. für Fibonacci: \[ F(n) = F(n-1) + F(n-2) \]