Grundlagen: algorithmen und Datenstrukturen - Cheatsheet.pdf

Greedy-Algorithmen

Definition:

Algorithmus, der in jedem Schritt die lokal beste Wahl trifft, um ein global optimales Ergebnis zu erreichen.

Details:

• Optimalitätsprinzip: oft nicht immer global optimal
• Anwendungen: z.B. Prim's Algorithmus, Dijkstra, Kruskal
• Komplexität: typischerweise effizient, abhängig von der Implementierung
• Ziel: Maximierung oder Minimierung bestimmter Kriterien
• Eigenschaften: Lokale Entscheidung, meist einfache Implementierung, aber keine Garantie für globale Optimalität

Dynamische Programmierung

Definition:

Dynamische Programmierung ist eine Methode zur Lösung von Problemen durch Zerlegung in überlappende Teilprobleme und Speicherung der Lösungen dieser Teilprobleme, um Redundanzen zu vermeiden.

Details:

• Zieht Nutzen aus optimalen Teilstrukturen
• Verwendet Memoisierung oder tabellarische Berechnung
• Zwei Hauptansätze: Top-Down (mit Memoisierung) und Bottom-Up
• Beispiele: Fibonacci-Zahlen, Knapsack-Problem, Kürzeste Pfade (Floyd-Warshall)
• Komplexität häufig reduziert von exponentiell auf polynomiell

Bäume und Graphen

Definition:

Bäume und Graphen sind fundamentale Strukturen in der Informatik zur Darstellung von Daten und deren Beziehungen.

Details:

• Baum: Hierarchische Struktur, bestehend aus Knoten (V) und Kanten (E).
• Graph: Besteht aus Knoten (V) und Kanten (E), keine Hierarchie notwendig.
• Binärbaum: Jeder Knoten hat max. 2 Kinder.
• Suchbaum: Binärbaum, bei dem linkes Kind ≤ und rechtes Kind > Elternknoten.
• AVL-Baum: Selbst-balancierender Binärbaum, Höhenunterschied zwischen links und rechts max. 1.
• Graph-Arten: Gerichtete (Richtungen der Kanten sind vorgegeben) und ungerichtete Graphen.
• Zusammenhang: Ein Graph ist zusammenhängend, wenn zwischen jedem Paar von Knoten ein Weg existiert.
• Minimale Spannbäume: Ein Untergraph eines ungerichteten, gewichteten Graphen, der alle Knoten verbindet und die Summe der Kantengewichte minimal ist.
• DFS (Tiefensuche) und BFS (Breitensuche): Algorithmen zur Durchsuchung von Graphen.
• Adjazenzmatrix und Adjazenzliste: Datenstrukturen zur Darstellung von Graphen.

Hash-Tabellen

Definition:

Datenstruktur zur schnellen Suche, Einfügen und Löschen von Elementen mithilfe einer Hash-Funktion.

Details:

• \textbf{Hash-Funktion}: Transformiert Schlüssel in einen Index des Arrays.
• \textbf{Kollisionsbehandlung}: Notwendig, da verschiedene Schlüssel denselben Index erzeugen können. Methoden: \textbf{Verkettung} und \textbf{offene Adressierung}.
• \textbf{Verkettung} (\textit{chaining}): Kollidierende Elemente werden in einer Liste an einem Array-Index gespeichert.
• \textbf{Offene Adressierung} (\textit{open addressing}): Sucht nach alternativen Positionen im Array.
• \textbf{Laufzeitkomplexität}: Durchschnittlich \textit{O(1)} für Suche, Einfügen und Löschen; Im schlechtesten Fall \textit{O(n)}.

Tiefensuche und Breitensuche in Graphen

Definition:

Tiefensuche (DFS) und Breitensuche (BFS) in Graphen sind grundlegende Traversierungsalgorithmen. DFS exploriert so tief wie möglich entlang jedem Branch bevor es backtrackt, während BFS alle Nachbarn eines Knotens vor deren Kindern erkundet.

Details:

• DFS verwendet Stack (rekursiv oder explizit).
• BFS verwendet Queue.
• DFS: Implementierung mit Rekursion oder Stack, Zeitkomplexität: O(V + E).
• BFS: Implementierung mit Queue, Zeitkomplexität: O(V + E).
• Anwendungen:
• DFS: Pfadfindung, Zykluserkennung, Topologische Sortierung.
• BFS: Kürzester Pfad in ungewichteten Graphen.
• DFS pseudocode:

DFS(v):  markiere v  für alle Knoten w adj zu v:    wenn w nicht markiert:      DFS(w)

BFS(v):  setze v in die Queue  markiere v  während die Queue nicht leer ist:    u = dequeue()    für alle Knoten w adj zu u:      wenn w nicht markiert:        markiere w        enqueue(w)

AVL-Bäume

Definition:

Ein selbstbalancierender binärer Suchbaum, benannt nach den Erfindern Adelson-Velsky und Landis.

Details:

• Jeder Knoten hat eine Balance-Faktor von \(-1, 0, 1\).
• Sorgt dafür, dass die Höhe des Baums logarithmisch bleibt.
• Ermöglicht Einfügen, Löschen und Suchen in \(O(\log n)\).
• Erfordert Rotationen (Single und Double) zum Ausbalancieren nach jedem Einfügen und Löschen.

Amortisierte Analyse

Definition:

Technik zur Bestimmung der durchschnittlichen Laufzeit oder Kosten von Operationen in einem Algorithmus über eine Serie von Operationen.

Details:

• Unterscheidet sich von der worst-case und average-case Analyse.
• Three main methods: Aggregierte Methode, Bankkonto-Methode (Banker's Method), Potenzial-Methode (Potential Method).
• \textbf{Aggregierte Methode}: Berechnet die Gesamtkosten aller Operationen und teilt durch die Anzahl der Operationen.
• \textbf{Bankkonto-Methode}: Weist Operationen 'Credits' zu, die später verwendet werden können, um teurere Operationen zu bezahlen.
• \textbf{Potenzial-Methode}: Nutzt eine Potenzialfunktion \Phi, um Veränderungen in der 'amortisierten' Kostenstruktur zu modellieren.

NP-Vollständigkeit

Definition:

Ein Problem ist NP-vollständig, wenn es in NP liegt und jedes Problem in NP auf dieses Problem in polynomieller Zeit transformiert werden kann.

Details:

• NP: Nichtdeterministische polynomielle Zeit
• Ein Problem P ist in NP, wenn eine Lösung in polynomieller Zeit verifiziert werden kann.
• Reduktion: Ein Problem Q kann auf ein Problem P in polynomieller Zeit reduziert werden, wenn Q auf P abgebildet werden kann und die Lösung von P die Lösung von Q ermöglicht.
• Bekannte NP-vollständige Probleme: SAT, 3-SAT, Hamiltonkreis-Problem
• Wenn ein NP-vollständiges Problem in polynomieller Zeit lösbar ist, sind alle Probleme in NP in polynomieller Zeit lösbar (P = NP).