Algorithmen

Algorithmen sind die Grundbausteine der Informatik und prägen unseren digitalen Alltag. Sie steuern Suchmaschinen, medizinische Diagnosen, Finanztransaktionen und sogar autonome Fahrzeuge.

Grundlagen

Ein Algorithmus ist eine präzise, endliche Folge von Anweisungen, um ein Problem zu lösen oder eine Aufgabe zu bewältigen (Cormen et al., 2009). Er besteht aus Eingabe, Verarbeitung und Ausgabe und muss folgende Eigenschaften erfüllen:
• Determiniertheit: Jeder Schritt ist eindeutig definiert.
• Endlichkeit: Der Algorithmus terminiert nach endlich vielen Schritten.
• Effektivität: Jede Anweisung ist ausführbar.
• Allgemeingültigkeit: Er löst eine Klasse von Problemen, nicht nur ein Einzelfall.

Klassifikation von Algorithmen

Algorithmen lassen sich nach verschiedenen Kriterien einteilen:

Nach Lösungsstrategie
• Divide-and-Conquer (Teile und herrsche): Das Problem wird in Teilprobleme zerlegt (z. B. Merge Sort).
• Greedy-Algorithmen: Lokal optimale Entscheidungen führen (hoffentlich) zur globalen Lösung (z. B. Dijkstra für kürzeste Pfade).
• Dynamische Programmierung: Zwischenergebnisse werden gespeichert, um Wiederholungsberechnungen zu vermeiden (z. B. Fibonacci-Zahlen).

Nach Komplexität
Die Laufzeitkomplexität (O-Notation) klassifiziert Algorithmen nach ihrer Skalierbarkeit:
• O(1): Konstanter Aufwand (z. B. Array-Zugriff).
• O(n): Linearer Aufwand (z. B. Suche in einer Liste).
• O(n²): Quadratischer Aufwand (z. B. Bubble Sort).

Nach Anwendungsbereich
Algorithmen sind oft auf spezifische Problemdomänen zugeschnitten.

Suchalgorithmen
• Lineare Suche (O(n)) – Durchsucht eine Liste sequenziell.
• Binäre Suche (O(log n)) – Voraussetzung: sortierte Daten (Divide-and-Conquer).
• Hash-basierte Suche (O(1)) – Nutzt eine Hashtabelle für direkten Zugriff.

Graphenalgorithmen
Breitensuche (BFS) & Tiefensuche (DFS) – Für Pfadfindung in Netzwerken.
• Dijkstra-Algorithmus – Kürzeste Wege in gewichteten Graphen (Greedy-Ansatz).
• A*-Algorithmus – Optimierte Suche mit Heuristik (KI-Anwendungen).

Numerische Algorithmen
• Newton-Raphson-Verfahren – Näherungsweise Nullstellenberechnung.
• Fast Fourier Transform (FFT) – Signalverarbeitung und Datenkompression.

Kryptografische Algorithmen
• RSA (asymmetrische Verschlüsselung) – Basierend auf Primfaktorzerlegung.
• AES (symmetrische Verschlüsselung) – Blockchiffre für sichere Datenübertragung.

Nach Parallelisierbarkeit
Manche Algorithmen lassen sich effizient parallelisieren, andere nicht.

Sequenzielle Algorithmen
• Nur ein Schritt wird zur gleichen Zeit ausgeführt (z. B. Bubble Sort).

Parallelisierbare Algorithmen
• MapReduce – Verarbeitung großer Datenmengen (z. B. bei Hadoop).
• Bitonic Sort – Ein paralleles Sortierverfahren für GPUs.

Beispiel: Matrixmultiplikation
• Sequenziell: O(n³)
• Parallel (Strassen-Algorithmus): O(n^2.81)

Nach Determiniertheit
Algorithmen können deterministisch oder nicht-deterministisch sein.

Deterministische Algorithmen
Immer gleiche Eingabe → gleiche Ausgabe (z. B. Euklidischer Algorithmus).

Nicht-deterministische Algorithmen
• Randomisierte Algorithmen – Nutzen Zufall (z. B. QuickSort mit zufälligem Pivot).
• Monte-Carlo-Algorithmen – Liefern mit einer gewissen Wahrscheinlichkeit das richtige Ergebnis (z. B. in Kryptographie).

Nach Lernfähigkeit (KI & Maschinelles Lernen)
Moderne Algorithmen können aus Daten lernen und sich anpassen.

Überwachtes Lernen
• Lineare Regression – Vorhersage kontinuierlicher Werte.
• Support Vector Machines (SVM) – Klassifikation mit maximalem Margin.

Unüberwachtes Lernen
• k-Means-Clustering – Gruppierung ähnlicher Datenpunkte.
• Principal Component Analysis (PCA) – Dimensionsreduktion.

Verstärkendes Lernen (Reinforcement Learning)
• Q-Learning – Belohnungsbasierte Optimierung (z. B. autonomes Fahren).

„Ein Algorithmus ist nicht intelligent, nur weil er lernt – aber er wird nützlicher, wenn er aus Erfahrung optimiert.“ Donald Knuth.

Herausforderungen

Moderne Algorithmen müssen mit Big Data, Echtzeitanforderungen und unsicheren Umgebungen umgehen. Eine Studie von Google (2020) untersuchte, wie Machine-Learning-Algorithmen durch Optimierung der Hyperparameter um 30% effizienter gemacht werden können (Bardenet et al., 2020).

„Algorithmen sind wie Rezepte – sie müssen präzise sein, aber ihre wahre Kunst liegt in der Anpassung an unvorhergesehene Zutaten.“ – Donald Knuth.

Rückgrat der digitalen Welt

Algorithmen sind das Rückgrat der digitalen Welt. Ihr Verständnis reicht von grundlegenden Strukturen bis hin zu hochkomplexen Optimierungsstrategien. Durch ständige Weiterentwicklung, etwa in Quantencomputing oder KI, bleiben sie ein dynamisches Forschungsfeld.

Ressourcen & Quellen
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms.Knuth, D. E. (1997). The Art of Computer Programming Fundamental Algorithms.Bardenet, R., et al. (2020). „Towards Scalable Hyperparameter Optimization.