Algorithmen und Datenstrukturen: Ein umfassender Leitfaden

Grundlagen der Algorithmen

Ein Algorithmus ist eine Berechnungsvorschrift, die aus einer endlichen Menge von Schritten besteht und zur Lösung eines Problems dient. Er zeichnet sich durch folgende Eigenschaften aus:

• Terminiertheit: Jede Eingabe führt nach endlich vielen Schritten zu einem Abbruch oder Ergebnis.
• Finitheit: Der Algorithmus besteht aus einer endlichen Anzahl von Befehlen.
• Effektivität: Die Auswirkung eines Befehls muss eindeutig sein.
• Determiniertheit: Gleiche Eingabe führt zu gleichem Output.
• Determinismus: Gleiche Eingabe führt zur gleichen Folge von Zuständen.

Die Komplexität wird häufig in der O-Notation angegeben: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).

Wichtige Datenstrukturen

Datenstrukturen dienen dazu, Daten auf eine bestimmte Art zu verwalten und zu verknüpfen, um den Zugriff und die Manipulation zu optimieren.

Arrays und Listen

• Array: Elemente gleichen Typs, Zugriff über einen Index (Random Access), statische Größe, Speicher liegt nebeneinander.
• Linked List (LL): Besteht aus Wert und Zeiger auf das nächste Element. Dynamisch, keine Garantie auf zusammenhängenden Speicher.
• Singly Linked List (SLL): Speichert Referenz auf den Kopf (Head), nur Nachfolger-Zeiger.
• Doubly Linked List (DLL): Besitzt Vorgänger- und Nachfolgerzeiger, höherer Speicherbedarf, einfaches Löschen und Einfügen.

Stack, Queue und Deque

• Stack: LIFO-Prinzip (Last-In-First-Out), Operationen push, pop und peek.
• Queue: FIFO-Prinzip (First-In-First-Out), Einfügen hinten (enqueue), Entfernen vorne (dequeue).
• Deque (Double-Ended Queue): Einfügen und Entfernen an beiden Enden möglich.

Graphen und Bäume

Ein Graph besteht aus einer nicht leeren Menge von Knoten (V) und Kanten (E). Ein Baum ist ein zyklenfreier Graph mit einem Startknoten (Wurzel).

• Binärbaum: Jeder Knoten hat maximal zwei Kinder.
• Balancierter Baum: Die Höhe der Teilbäume unterscheidet sich maximal um eins.
• Entarteter Baum: Jeder Knoten hat höchstens einen Teilbaum (entspricht einer Liste).

Suchalgorithmen für Graphen

• Breitensuche (BFS): Nutzt eine Queue, besucht Ebene für Ebene.
• Tiefensuche (DFS): Nutzt einen Stack (oder Rekursion), besucht Pfade bis zum Blatt.

Programmierung: Iteration und Rekursion

Iterative Verfahren nutzen Schleifen (for, while). Rekursion beschreibt die Selbstbezüglichkeit, bei der eine Funktion sich selbst mit geänderten Parametern aufruft. Wichtig ist eine Abbruchbedingung (Basisfall), um einen StackOverflow zu vermeiden.

Divide and Conquer

Dieses Prinzip zerlegt Probleme in Teilprobleme (Divide), löst diese (Conquer) und setzt sie zusammen (Merge). Ein weiteres Verfahren ist Backtracking (Trial-and-Error), bei dem Teillösungen bei Sackgassen rückgängig gemacht werden.

Suchverfahren und Hashing

Die Suche dient dem Auffinden eines Schlüssels in einer Datenmenge.

• Sequenzielle Suche: O(n), für unsortierte Daten.
• Binäre Suche: O(log n), setzt sortierte Daten voraus.
• Interpolationssuche: O(log log n) im Durchschnitt, für linear wachsende Daten.

Hash-Tabellen

Eine Hash-Tabelle berechnet den Index eines Datums direkt aus dem Schlüssel mittels einer Hashfunktion. Bei Kollisionen (gleicher Index für verschiedene Schlüssel) helfen:

• Überlauflisten (Chaining): Speicherung in verketteten Listen.
• Offene Adressierung: Suche nach dem nächsten freien Platz (Linear Probing, Double Hashing).

Sortieralgorithmen

Sortierverfahren ordnen Elemente anhand einer Relation. Wichtige Eigenschaften sind In-Place (kein extra Speicher), Stabilität (Reihenfolge gleicher Schlüssel bleibt) und Adaptivität.

• Insertion Sort: Sortiert durch Einfügen, effizient bei kleinen Mengen.
• Selection Sort: Sucht das Minimum und tauscht es an die richtige Position.
• Merge Sort: Divide-and-Conquer, O(n log n), stabil, aber nicht In-Place.
• Quick Sort: Nutzt ein Pivot-Element, im Durchschnitt O(n log n), In-Place.

Heaps und Priority Queues

Ein Heap ist eine Datenstruktur, bei der die Wurzel immer das größte (Max-Heap) oder kleinste Element enthält. Die Haldenbedingung besagt, dass jeder Knoten größer oder gleich seinen Kindern sein muss. Operationen wie Heapify und Build-Heap ermöglichen effizientes Sortieren (Heapsort).

Binäre Suchbäume (BST)

In einem sortierten Binärbaum gilt: Linkes Kind < Eltern < Rechtes Kind. Traversierungsarten:

• Inorder (L-W-R): Liefert die Elemente in sortierter Reihenfolge.
• Preorder (W-L-R): Wurzel zuerst.
• Postorder (L-R-W): Wurzel zuletzt.