Ein Problem festlegen: Eingabe, Ausgabe und Schritte
Bevor du Code schreibst, beschreibe das Problem genau. Das nennt man die Spezifikation.
- Eingabe: Welche Daten bekommen wir, welchen Typ und welche Grenzen haben sie (z. B. "n ganze Zahlen, 1 ≤ n ≤ 1000").
- Ausgabe: Was müssen wir zurückgeben (z. B. "die größte davon").
- Bedingungen: Was gilt vorher (Vorbedingung) und nachher (Nachbedingung).
Die Schritte aufschreiben
Ein Algorithmus ist eine endliche Liste klarer Schritte, die jede gültige Eingabe in die richtige Ausgabe verwandelt. Du kannst ihn so aufschreiben:
- in normaler Sprache: "Sieh dir jede Zahl an; ist sie größer als die bisher beste, merke sie dir."
- als nummerierte Schrittliste: 1. beste ← erste Zahl. 2. Für jede weitere Zahl x: wenn x > beste, dann beste ← x. 3. Gib beste aus.
- als Pseudocode oder Flussdiagramm, wenn es genauer sein soll.
Teste ihn von Hand mit kleinen Eingaben, auch mit kniffligen (alle gleich, negative Zahlen, nur eine Zahl).
Top-down- und Bottom-up-Entwurf
Top-down (schrittweise Verfeinerung): Du startest mit der ganzen Aufgabe, teilst sie in ein paar große Schritte und teilst jeden Schritt weiter, bis jeder Teil leicht zu programmieren ist. Beispiel: "Zeugnis erstellen" → Noten einlesen → Durchschnitte berechnen → Noten vergeben → ausdrucken.
Bottom-up: Du baust und testest zuerst kleine, wiederverwendbare Bausteine (eine Funktion für das Maximum, eine zum Sortieren) und fügst sie dann zum ganzen Programm zusammen.
Echte Projekte mischen beides: von oben planen, von unten bauen und testen.
Teile und Herrsche und das Halbierungsverfahren
Teile und Herrsche hat drei Züge: Das Problem in kleinere Teile derselben Art teilen, jeden Teil lösen (oft per Rekursion) und die Antworten zusammensetzen.
- Binäre Suche (Halbieren): In einer sortierten Liste vergleichst du mit der Mitte und wirfst eine Hälfte weg. n Elemente brauchen etwa log₂ n Prüfungen: 16 → 4, 1 000 000 → 20.
- Mergesort: Die Liste in zwei teilen, jede Hälfte sortieren, beide zusammenführen: O(n log n).
- Schnelle Potenz: a⁸ = ((a²)²)²: 3 Multiplikationen statt 7.
- Nullstelle per Intervallhalbierung: Ein Intervall halbieren, in dem die Funktion das Vorzeichen wechselt.
Greedy-Algorithmen
Ein Greedy-Algorithmus (gieriger Algorithmus) trifft die Wahl, die gerade am besten aussieht, und ändert sie nie mehr.
- Wechselgeld mit 50, 20, 10, 5, 2, 1: erst die größte Münze. Bei dieser Art von Münzsystem ist das optimal.
- Die meisten Aktivitäten an einem Tag auswählen: immer die nehmen, die am frühesten endet. Optimal.
- Fraktionales Rucksackproblem: Zuerst die Gegenstände mit dem besten Wert pro kg nehmen. Optimal.
Aber Greedy ist nicht immer richtig: Mit den Münzen 1, 3, 4 ergibt 6 nach Greedy 4 + 1 + 1 (3 Münzen), während 3 + 3 nur 2 braucht. Um einer Greedy-Methode zu trauen, musst du sie beweisen oder mit einer sicheren Methode vergleichen.
Dynamische Programmierung und Backtracking
Dynamische Programmierung (DP)
Wenn sich dieselben kleineren Probleme wiederholen, löse jedes nur einmal und speichere die Antwort in einer Tabelle. Wenigste Münzen für den Betrag a: best[a] = 1 + min(best[a - c]) über alle Münzen c ≤ a, beginnend mit best[0] = 0. Für die Münzen 1, 3, 4: best = 0, 1, 2, 1, 1, 2, 2. Die Tabelle von klein nach groß zu füllen ist bottom-up; Rekursion mit Gedächtnis ist top-down (Memoisierung). Mehr dazu in der eigenen Lektion über dynamische Programmierung.
Backtracking
Baue eine Lösung Wahl für Wahl auf. Verletzt eine Wahl eine Regel oder führt in eine Sackgasse, nimm sie zurück und probiere die nächste Möglichkeit. Das nutzt man bei Labyrinthen, Sudoku, dem N-Damen-Problem und beim Auflisten aller Teilmengen. Es ist ein vorsichtiges Brute Force: Es überspringt ganze Äste, die nicht funktionieren können.
Brute Force
Jede mögliche Antwort ausprobieren. Immer richtig, aber oft viel zu langsam (2ⁿ Teilmengen, n! Reihenfolgen).
Eine Technik wählen: Korrektheit, Effizienz und Datenstrukturen
| Technik | Einsatz, wenn | Beispiel | Typische Zeit |
|---|---|---|---|
| Brute Force | die Eingabe winzig ist | alle 3-stelligen Passwörter probieren | oft 2ⁿ oder n! |
| Teile und Herrsche | die Teile unabhängig sind | binäre Suche, Mergesort | O(log n), O(n log n) |
| Greedy | eine beste lokale Wahl nachweislich sicher ist | Aktivitätenauswahl, Wechselgeld | O(n log n) |
| Dynamische Programmierung | sich Teilprobleme wiederholen | Münzwechsel, kürzeste Wege | Größe der Tabelle |
| Backtracking | man mit Regeln sucht | Labyrinth, Sudoku | exponentiell, aber beschnitten |
Begründe die Wahl
Korrektheit: Zeige, dass der Algorithmus immer anhält und die richtige Ausgabe liefert (eine Schleifeninvariante, ein Beweis oder Tests mit Grenzfällen). Effizienz: Zähle die Schritte, wenn n wächst (Groß-O), und vergleiche mit anderen Methoden.
Datenstrukturen helfen
Arrays für Tabellen (DP), Stapel für Backtracking (merken, wohin man zurückgeht), Warteschlangen für die Suche Ebene für Ebene. Ein Binärbaum speichert Elemente so, dass jeder Knoten höchstens zwei Kinder hat; in einem binären Suchbaum gehen kleinere Schlüssel nach links und größere nach rechts, sodass die Suche auf jeder Ebene die Arbeit halbiert, genau wie die binäre Suche.
Probier es aus: Münzen und ein Ratespiel
- Spiele das Ratespiel 1 bis 100 mit einem Freund. Frage immer nach der Mitte. Gewinnst du immer in 7 Fragen? (2⁷ = 128.)
- Schreibe mit den Münzen 1, 3, 4 die DP-Tabelle für die Beträge 0 bis 10 auf Papier. Wo scheitert Greedy?
- Öffne den letzten 3D-Schritt. Probiere die Münzen 1, 7, 10 und den Betrag 14. Greedy ergibt 10 + 1 + 1 + 1 + 1; DP ergibt 7 + 7.
- Schreibe eine Schrittliste für "finde die kleinste Zahl in einer Liste" und teste sie mit 5, 5, 5 und mit nur einer Zahl.
Wichtige Formeln und Definitionen
- Spezifikation = Eingabe + Ausgabe + Bedingungen
- Halbieren: etwa log₂ n Schritte (16 → 4, 1024 → 10)
- Münz-DP: best[0] = 0; best[a] = 1 + min best[a - c]
- Teile und Herrsche = teilen + lösen + zusammensetzen
- Greedy ist schnell, muss aber als optimal bewiesen werden
Gelöste Beispiele
1. Schreibe eine Spezifikation und eine Schrittliste, um die größte von n Zahlen zu finden.
Eingabe: n ≥ 1 Zahlen. Ausgabe: die größte. Schritte: 1. beste ← erste Zahl. 2. Für jede andere Zahl x: wenn x > beste, beste ← x. 3. Gib beste aus. Für 4, 9, 2, 7, 12, 5, 10, 3 ist die Ausgabe 12 nach 7 Vergleichen.
2. Wie viele Fragen braucht das Halbieren, um eine Zahl von 1 bis 1000 zu finden?
Jede Frage halbiert den Bereich: 1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1. Das sind 10 Fragen (2¹⁰ = 1024 ≥ 1000).
3. Zahle 87 nach Greedy mit den Münzen 50, 20, 10, 5, 2, 1.
50 (37 übrig), 20 (17), 10 (7), 5 (2), 2 (0): 50 + 20 + 10 + 5 + 2 = 5 Münzen.
4. Fülle die DP-Tabelle für die Münzen 1, 3, 4 bis zum Betrag 7.
best[0]=0, [1]=1, [2]=2, [3]=1, [4]=1, [5]=min(best4, best2, best1)+1=2, [6]=min(best5, best3, best2)+1=2, [7]=min(best6, best4, best3)+1=2 (3 + 4).
5. Aktivitäten (Start-Ende): A 9-11, B 10-12, C 11-13, D 12-14, E 13-15. Wähle die meisten Aktivitäten, die sich nicht überschneiden.
Greedy nach frühestem Ende: A (endet 11), dann C (startet 11, endet 13), dann E (startet 13). 3 Aktivitäten: A, C, E.
6. Plane top-down: ein Programm, das einer Klasse den Durchschnitt der Noten und den besten Schüler nennt.
Ebene 1: Daten einlesen → berechnen → ausgeben. Ebene 2: Namen und Noten in Listen einlesen; Summe und Durchschnitt berechnen; die beste Note und ihren Namen finden; beides ausgeben. Jedes Stück wird dann bottom-up programmiert und getestet.
Häufige Fehler
- Mit dem Programmieren anfangen, bevor Eingabe und Ausgabe feststehen. Viele 'Fehler' sind in Wahrheit eine unklare Spezifikation.
- Annehmen, dass Greedy immer optimal ist. Das gilt nur, wenn man es beweisen kann (die Münzen 1, 3, 4 widerlegen es).
- Binäre Suche auf einer unsortierten Liste benutzen. Halbieren braucht sortierte Daten.
- DP mit Teile und Herrsche verwechseln. DP ist für überlappende Teilprobleme, die man speichert; Teile und Herrsche zerlegt in unabhängige Teile.