Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Greedy heißt 'gierig': bei jeder Entscheidung nimmst du die lokal beste Option, ohne dich umzuschauen. Manchmal landet das beim globalen Optimum, manchmal nicht. Klausur-Pflicht in 13/17 WInf-Algo-Klausuren, wichtige Counterpart-Strategie zu DP.
Klausur-Tipp: Bei Klausur-Aufgaben zur Activity-Selection IMMER nach Endzeit sortieren. Das ist die einzige korrekte Greedy-Strategie. Begründung: nach Austauschargument.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
Greedy heißt 'gierig': bei jeder Entscheidung nimmst du die lokal beste Option, ohne dich umzuschauen. Manchmal landet das beim globalen Optimum, manchmal nicht. Klausur-Pflicht in 13/17 WInf-Algo-Klausuren, wichtige Counterpart-Strategie zu DP.
Greedy-Algorithmus: Trifft an jeder Stelle eine lokal optimale Entscheidung in der Hoffnung, dass die Gesamtlösung global optimal wird.
Zwei Voraussetzungen (analog zu DP, aber stärker):
Klausur-Faustregel: Wenn beides gilt → Greedy ist optimal. Wenn nur (2) gilt → DP nötig.
Problem: Gib 20€ Wechselgeld mit den wenigsten Münzen.
Münzen Euro-System: {1, 2, 5, 10, 20, 50, 100, 200}
Greedy: nimm immer die größte Münze ≤ Rest.
Bei Münzen \1, 6, 10\ für 12 Cent:
Greedy ist im Euro-System optimal, in beliebigen Systemen NICHT.
Gegeben Events mit Start- und Endzeit. Wähle die maximale Anzahl nicht-überlappender Events.
Greedy-Regel: Sortiere nach Endzeit. Nimm erstes Event, dann das nächste, dessen Start ≥ vorherigem End ist.
Korrekt! Beweis durch Austauschargument: wenn du eine andere Lösung hättest, könntest du das erste Event durch das mit frühester Endzeit ersetzen, ohne schlechter zu werden.
Optimale Präfix-Codes für Datenkompression. Iterativ die zwei seltensten Symbole zu einem Knoten verschmelzen → Binärbaum mit optimaler durchschnittlicher Codewort-Länge.
Greedy auf Kanten (Kruskal: nimm immer billigste Kante ohne Zyklus) oder Knoten (Prim: erweitere Baum mit billigster Außen-Kante). Beide finden den global minimalen Spannbaum.
Wie 0/1-Knapsack, aber Items teilbar. Greedy: nimm Items in absteigender Reihenfolge nach v_i / w_i (Wert pro Gewichtseinheit), nimm so viel wie passt.
Achtung: 0/1-Knapsack (Items unteilbar) ist NICHT Greedy-lösbar — braucht DP.
Auch ein Greedy-Algorithmus! In jedem Schritt: extrahiere Knoten mit kleinster Distanz (= lokal beste Wahl). Bei nicht-negativen Gewichten optimal.
| Greedy | DP | |
|---|---|---|
| Entscheidung | lokal, einmalig | global, alle Optionen geprüft |
| Speicher | O(1) oder O(n) typisch | O(n) bis O(n²) typisch |
| Laufzeit | meist O(n log n) (durch Sortierung) | meist O(n²) oder mehr |
| Optimal? | nur bei Greedy-Auswahl-Eigenschaft | immer (bei korrekter Rekurrenz) |
| Implementierung | einfacher | komplexer |
Faustregel: Erst Greedy probieren (einfacher). Wenn das nicht optimal ist (Gegenbeispiel finden!), DP nutzen.
Annahme: Es gibt eine bessere Lösung als die von Greedy. Zeige: Du kannst die Greedy-Entscheidung in die andere Lösung einbauen ohne Verschlechterung. Daraus folgt Greedy = optimal.
Bei jedem Schritt liegt die Greedy-Lösung mindestens so gut wie jede andere Teil-Lösung mit gleicher Anzahl Schritte.
greedy_algorithm(input):
sort/prepare input by greedy criterion
solution = empty
for each candidate in sorted order:
if candidate is feasible:
add candidate to solution
return solution
selectActivities(activities):
sort activities by end time ascending
selected = []
lastEnd = -infinity
for activity in activities:
if activity.start >= lastEnd:
selected.append(activity)
lastEnd = activity.end
return selected
Laufzeit: O(n log n) wegen Sortierung. Greedy-Loop selbst ist O(n).
1. Greedy = lokal beste Entscheidung. Nie zurück, nie umentscheiden.
2. Sortieren ist oft erster Schritt. Activity-Selection nach Endzeit, Knapsack nach v/w, Huffman nach Häufigkeit.
3. Greedy ist nicht immer optimal. Münzwechsel kann schiefgehen, 0/1-Knapsack braucht DP.
4. Beweise mit Austauschargument. Annehmen: andere Lösung besser → tausche greedy-Schritt rein → kein Schaden → Greedy ist optimal.
5. Greedy vs. DP: Greedy einfacher + schneller, DP optimal. Wenn unsicher: probiere Gegenbeispiele.
1. Greedy ohne Korrektheits-Beweis. Funktioniert manchmal "rein zufällig". Bei Klausur immer prüfen: gibt's ein Gegenbeispiel?
2. 0/1-Knapsack mit Greedy. Falsch! Nur Fractional Knapsack ist greedy-optimal. 0/1 (Items unteilbar) braucht DP.
3. Falsches Sortier-Kriterium. Activity-Selection nach Start-Zeit funktioniert NICHT. Muss nach Endzeit sein. Bei Knapsack: Wert pro Gewicht (v/w), nicht nur Wert.
4. Greedy für Probleme ohne Greedy-Auswahl-Eigenschaft. TSP (Traveling Salesman) ist NICHT greedy-lösbar (NP-schwer).
5. Greedy mit Backtracking verwechseln. Greedy macht eine Entscheidung pro Schritt und vergisst Alternativen. Backtracking probiert systematisch alle Möglichkeiten durch.
Du hast 8 Vorlesungen mit verschiedenen Start- und Endzeiten. Wähle die maximale Anzahl, die du besuchen kannst ohne Überlappung.
Vergleich:
Beobachte, welche Strategie die meisten Vorlesungen auswählt.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Bei Klausur-Aufgaben zur Activity-Selection IMMER nach Endzeit sortieren. Das ist die einzige korrekte Greedy-Strategie. Begründung: nach Austauschargument.
6 Aufgaben zu Greedy-Konzepten, klassischen Problemen, Korrektheit.
Klausurfragen mit Lösungen (6)
Antwort: Lokal beste Entscheidung treffen, ohne zurückzuschauen
Erklärung: Greedy: an jeder Stelle die LOKAL BESTE Entscheidung, ohne Alternativen zu erwägen oder zurückzusetzen. Schnell + einfach, aber nicht immer optimal.
Antwort: Nach Endzeit aufsteigend
Erklärung: Nach ENDZEIT sortieren! Begründung: das Event mit frühester Endzeit lässt am meisten Raum für die folgenden Events. Beweis durch Austauschargument — Klausur-Klassiker.
Antwort: Falsch
Erklärung: FALSCH. Greedy findet das Optimum NUR bei Problemen mit Greedy-Auswahl-Eigenschaft. Klassisches Gegenbeispiel: 0/1-Knapsack. Greedy nach v/w sortieren funktioniert NICHT optimal bei unteilbaren Items.
Typ: Wahr/Falsch
Antwort: 0/1-Knapsack
Erklärung: 0/1-Knapsack (Items unteilbar) braucht DP, nicht Greedy. Fractional Knapsack (teilbare Items) ist greedy-optimal mit Sortierung nach v/w. Huffman + MST sind Greedy-Klassiker.
Richtige Antworten: Dijkstra ist ein Greedy-Algorithmus; Greedy ist meist O(n log n) (wegen Sortierung); Activity-Selection nach Endzeit sortieren; Korrektheits-Beweise nutzen oft Austauschargument
Erklärung: Richtig: Dijkstra=Greedy, O(n log n) durch Sortierung, Endzeit für Activity-Sel., Austauschargument. Falsch: Greedy ist NICHT immer optimal (nur bei spezifischen Eigenschaften); Greedy braucht WENIGER Speicher als DP.
Typ: Multi-Select
Zuordnungen:
Erklärung: Klassiker-Probleme: Fractional Knapsack greedy, 0/1 DP, Activity-Selection greedy by end time, Huffman greedy bottom-up.
Typ: Zuordnung
Klausurfragen mit Lösungen (6)
Antwort: Austauschargument: tausche Greedy-Schritt in optimale Lösung
Erklärung: Austauschargument: Nimm an, optimale Lösung weicht in Schritt k von Greedy ab. Zeige: tausche Greedy-Wahl rein → Lösung bleibt mindestens so gut → Greedy ist optimal. Standard-Beweis-Methode.
Antwort: Wahr
Erklärung: RICHTIG. Das Euro-System ist 'kanonisch' — Greedy findet das Optimum. Beweis nicht trivial (Pearson, Verma). Bei anderen Münzsystemen (z.B. {1, 6, 10}) ist Greedy nicht optimal.
Typ: Wahr/Falsch
Antwort: Wenn das beste v/w-Item zu schwer für den Rucksack ist und Kombinationen besser wären
Erklärung: Beispiel: Items (w=10, v=100, ratio=10), (w=5, v=40, ratio=8), (w=5, v=40, ratio=8). Kapazität 10. Greedy nimmt Item 1 (Wert 100). Optimal: Items 2+3 (Wert 80) NEIN, Item 1 ist besser. Anderes Beispiel: Kap=15, (w=10,v=100), (w=6,v=70), (w=4,v=60), (w=2,v=30). Greedy nach ratio (10, 11.67, 15, 15): nimmt 4+2 (v=90), 6 (Σ 12, v=160), kann nicht 10 nehmen. Optimal: 10+4+? wäre Σ14, v=160. Es ist sehr knapp aber zeigt: Greedy ist NICHT garantiert optimal bei 0/1.
Antwort: O(n log n)
Erklärung: O(n log n) — wegen der Sortierung nach Endzeit. Die Greedy-Schleife danach ist O(n). Insgesamt von Sortierung dominiert.
Lösungen pro Lücke:
Erklärung: Greedy-Vokabular. Lokal-beste-Wahl, Greedy-Auswahl-Eigenschaft, optimal-bei-Korrektheit, Endzeit-Sortierung, Austauschargument.
Typ: Lückentext
Richtige Reihenfolge:
Erklärung: Standard-Activity-Selection-Workflow. Sortierung → Init → Loop mit Konflikt-Check → lastEnd-Update → Return. Laufzeit O(n log n).
Typ: Reihenfolge