Algorithmus

Dieser Beitrag ist eine Begriffserklärung zum Thema Algorithmus – inklusive Prüfungsfragen, Merkpunkten und Tags.

In a Nutshell

Ein Algorithmus ist eine endliche, eindeutig beschriebene Folge von Schritten zur Lösung eines Problems. Bewertet wird u.a. nach Korrektheit, Laufzeit, Speicherbedarf, Stabilität und Robustheit.

Kompakte Fachbeschreibung

Ein Algorithmus verarbeitet wohldefinierte Eingaben und liefert deterministische oder probabilistische Ausgaben. Beschrieben wird er häufig in Pseudocode mit Vor- und Nachbedingungen.

Für die Analyse nutzt man asymptotische Notationen:

• O (obere Schranke)
• Ω (untere Schranke)
• Θ (enge Schranke)

Oft getrennt nach Best-/Average-/Worst-Case und ergänzt um amortisierte Analyse.

Typische Entwurfsparadigmen:

• Divide and Conquer
• Greedy
• Dynamische Programmierung
• Backtracking
• Randomisierung

Datenstrukturen (Array, Liste, Heap, Hash-Tabelle, Baum, Graph) bestimmen reale Kosten stark.

Security-Aspekt: Worst-Case-Inputs können Algorithmic Complexity Attacks auslösen, daher sind Eingabevalidierung und Ressourcenlimits relevant.

Prüfungsrelevante Stichpunkte

• Exakt vs heuristisch/approximativ; deterministisch vs randomisiert
• O/Ω/Θ; Best/Average/Worst; amortisiert
• Paradigmen: D&C, Greedy, DP, Backtracking
• IHK: Vor-/Nachbedingungen, Terminierung, Schleifeninvarianten
• Praxis: Datenstruktur passend wählen, erst messen dann optimieren
• Security: Worst-Case-Härtung, Limits
• Doku: Problemdefinition, Pseudocode, Komplexität, Testprotokolle

Kernkomponenten

1. Spezifikation (Input/Output/Randbedingungen)
2. Kostenmodell (Zeit/Speicher/I/O)
3. Pseudocode (Sequenz, Auswahl, Schleife)
4. Datenstrukturwahl
5. Korrektheit (Invarianten/Induktion/Terminierung)
6. Komplexitätsanalyse
7. Entwurfsansatz
8. Implementierungsdetails (Rekursion/Iteration)
9. Robustheit/Sicherheit
10. Tests (Grenzwerte, Fuzzing, Regression)

Praxisbeispiel: Insertion Sort (Pseudocode)

funktion insertionSort(a)
  fuer i von 1 bis laenge(a)-1
    key <- a[i]
    j <- i-1
    solange j >= 0 und a[j] > key
      a[j+1] <- a[j]
      j <- j-1
    ende
    a[j+1] <- key
  ende
  gib a zurueck

Erklärung: Stabil, in-place, Worst-Case O(n^2), Best-Case O(n) bei fast sortierten Daten.

Typische Prüfungsfragen (mit Kurzantwort)

1. O vs Ω vs Θ? O obere Schranke, Ω untere Schranke, Θ enge Schranke.
2. Wann ist Greedy korrekt? Wenn optimale Substruktur und Greedy-Choice-Property gelten.
3. Woran erkennt man DP? Überlappende Teilprobleme + optimale Substruktur.
4. Wie zeigt man Terminierung? Variationsfunktion, die strikt sinkt und nach unten beschränkt ist.

Freie Antwort

Für IHK-Aufgaben zählt: Problem klar definieren, Pseudocode sauber schreiben, Komplexität begründen und Randfälle testen. In realen Systemen sind Cache-/I/O-Effekte und Robustheit gegen Worst-Case-Inputs entscheidend.

Lernstrategie

1. Pseudocode + Invariante zu Altfragen schreiben.
2. Laufzeiten messen (linear vs binär, verschiedene Sorts).
3. DP-Beispiel (Rucksack) als Tabelle modellieren.
4. Randfälle und Abbruchbedingungen immer testen.

Wichtigste Quellen

1. https://de.wikipedia.org/wiki/Algorithmus
2. https://cp-algorithms.com/