Grundlagen: Algorithmen und Datenstrukturen - Cheatsheet.pdf

Definition und Eigenschaften von Algorithmen

Definition:

Ein Algorithmus ist eine eindeutige Abfolge von Anweisungen zur Lösung eines Problems oder zur Durchführung einer Berechnung.

Details:

• Determinismus: Jeder Schritt ist eindeutig und führt stets zum selben Ergebnis.
• Endlichkeit: Ein Algorithmus muss nach endlich vielen Schritten zum Ende kommen.
• Eingaben: Algorithmen arbeiten mit gegebenen Eingabewerten.
• Ausgaben: Algorithmen produzieren mindestens einen Ausgabewert.
• Effektivität: Jeder Einzelschritt ist ausführbar und eindeutig definiert.

Algorithmische Strategien: Divide and Conquer, Greedy, Dynamic Programming

Definition:

Algorithmische Strategien zur Lösung komplexer Probleme effizient.

Details:

• Divide and Conquer: Problem in kleinere Teilprobleme zerlegen, diese rekursiv lösen und dann die Teillösungen kombinieren. Beispiel: Mergesort, Quicksort.
  • Teilproblem: in kleinere Teile zerlegen
  • Rekursion: Teilprobleme lösen
  • Kombination: Teillösungen zusammenfügen
• Greedy: Schrittweise konstruktive Lösung durch Auswahl der lokal besten Entscheidung. Beispiel: Dijkstra-Algorithmus, Kruskal-Algorithmus.
  • Lokale Wahl: in jedem Schritt die beste Auswahl treffen
  • Optimalität: führt oft zu optimalen oder naheliegenden Lösungen
• Dynamic Programming: Probleme durch Speichern von Zwischenlösungen effizient lösen. Beispiel: Fibonacci-Berechnung, Kürzeste Pfadprobleme.
  • Memoisierung: Zwischenergebnisse speichern
  • Rekursion: Teilprobleme rekursiv lösen
  • Bottom-Up: Lösung durch schrittweises Lösen von Teilproblemen

Komplexitätsanalyse: Big-O Notation, Amortisierte Analyse, Rekurrenzen

Definition:

Analyse der Effizienz von Algorithmen hinsichtlich Laufzeit und Speicherplatz.

Details:

• Big-O Notation: Beschreibt das Worst-Case-Verhalten eines Algorithmus. Formel: \( O(f(n)) \)
• Amortisierte Analyse: Durchschnittliche Laufzeit über eine Serie von Operationen. Relevant für Datenstrukturen mit teuren gelegentlichen Operationen.
• Rekurrenzen: Gleichungen, die die Laufzeit rekursiver Algorithmen definieren und oft durch Master-Theorem gelöst werden. Beispiel: \( T(n) = a T\big( \frac{n}{b} \big) + f(n) \)

Arrays, Listen und Bäume

Definition:

Verwendung und Verwaltung von Datensammlungen in der Informatik. Arrays: feste Größe, schneller Zugriff. Listen: dynamische Größe, flexibles Einfügen/Löschen. Bäume: hierarchische Struktur, effizient für Suchoperationen.

Details:

• Arrays: Feste Größe, indexbasierter Zugriff: Verwendung \texttt{a[i]}
• Listen (Singly Linked, Doubly Linked): Dynamische Größe, je nach Implementierung O(1) Einfügen/Löschen an Listenanfang oder -ende
• Bäume (Binäre Bäume, AVL-Bäume, B-Bäume): Hierarchische Struktur, Knoten und Kanten. Höhe beeinflusst Such-, Einfüge- und Löschzeit O(log n) für ausgeglichene Bäume

Hash-Tabellen und Graphen

Definition:

Hash-Tabellen implementieren assoziative Arrays; Graphen stellen Netzwerke von Knoten (Vertices) und Kanten (Edges) dar.

Details:

• Hash-Tabellen: schnelle Suche, Einfügen, Löschen mit erwarteter Zeitkomplexität O(1)
• Hash-Funktion: Zuordnung von Schlüsseln zu Speicheradressen; Gleichverteilung wichtig
• Kollisionsbehandlung: Separate Chaining, Open Addressing
• Graphen: Darstellung als Adjazenzmatrix oder Adjazenzliste
• Graph-Typen: ungerichtet/gerichtet, gewichtet/ungewichtet
• Wichtige Algorithmen: Tiefensuche (DFS), Breitensuche (BFS), Dijkstra's Algorithmus für kürzeste Wege
• Komplexität vieler Graphalgorithmen hängt von Anzahl Knoten (n) und Kanten (m) ab: z.B. BFS und DFS O(n + m)

Heaps und Balancierte Bäume: AVL-Bäume, Rot-Schwarz-Bäume

Definition:

Heaps: Binärbäume für effizientes Finden von Minimum/Maximum; Balancierte Bäume: Bäume, die durch Rotationen balanciert werden, um Performance zu optimieren.

Details:

• AVL-Bäume: Selbstbalancierende binäre Suchbäume
• Balancebedingung: Für jeden Knoten unterscheidet sich die Höhe der linken und rechten Teilbäume um höchstens 1
• Rebalancierung durch Rotationen (einfach/doppelt)
• Suchtiefe: \(O(\log n)\)
• Rot-Schwarz-Bäume: Binäre Suchbäume, die zusätzlich zu den üblichen Bäumeigenschaften Regeln zur Knoteneinfärbung haben
• Eigenschaften: Jeder Knoten ist entweder rot oder schwarz
• Regeln: Wurzel ist schwarz, rotöde Knoten haben schwarze Kinder, gleicher Pfad von Knoten zu Blättern hat gleich viele schwarze Knoten
• Suchtiefe: \(O(\log n)\)

Rekursiver Abstieg und Auflösung

Definition:

Rekursiver Abstieg: Top-Down Parsing Methode für Compiler; Auflösung: Behandlung und Vereinfachung logischer Formeln, v.a. in Prädikatenlogik

Details:

• Rekursiver Abstieg: Parser-Deklaration mit rekursiven Funktionen für Grammatikregeln
• Auflösung: Ableitungsverfahren zur Herleitung neuer Aussagen aus gegebenen Klauseln
• Wichtig: Endrekursion zur Optimierung, Erkennung und Behandlung von Linksrekursion
• Praktische Anwendung: Compilerbau, Logikprogrammierung

Effiziente Sortieralgorithmen: Merge Sort, Quick Sort, Heap Sort

Definition:

Effiziente Sortieralgorithmen, die häufig verwendet werden, um große Datenmengen zu sortieren.

Details:

• Merge Sort: Teilt das zu sortierende Array rekursiv in zwei Hälften und führt dann eine geordnete Zusammenführung durch. Laufzeit: \(O(n \log n)\)
• Quick Sort: Wählt ein Pivotelement, partitioniert das Array in zwei Teile, und sortiert diese rekursiv. Laufzeit: Durchschnittlich \(O(n \log n)\), schlechtester Fall \(O(n^2)\).
• Heap Sort: Verwendet einen binären Heap, um das größte Element wiederholt an das Ende des Arrays zu setzen. Laufzeit: \(O(n \log n)\)