Informatik Algorithmen – Greedy-Algorithmen
Karteikarten zum Thema „Informatik“ · 14 Karten · von atrio. Beispiele: Was ist ein Greedy-Algorithmus? · Was besagt das Greedy-Choice-Property?
Karten
14 KartenWas ist ein Greedy-Algorithmus?
Rückseite
Ein Algorithmus, der in jedem Schritt die lokal beste Wahl trifft, in der Hoffnung, damit ein globales Optimum zu erreichen.
Was besagt das Greedy-Choice-Property?
Rückseite
Eine global optimale Lösung kann durch eine lokal optimale (gierige) Wahl erreicht werden; die erste Entscheidung hängt nicht von späteren Teilproblemen ab.
Was bedeutet optimale Substruktur bei Greedy-Algorithmen?
Rückseite
Eine optimale Lösung des Gesamtproblems enthält optimale Lösungen der Teilprobleme, die nach der gierigen Wahl übrig bleiben.
Worin unterscheidet sich Greedy von Dynamic Programming?
Rückseite
Greedy trifft irrevocable Entscheidungen ohne Rückblick; DP löst alle Teilprobleme und kombiniert sie, oft mit Memoisierung oder Bottom-Up.
Wie funktioniert der Algorithmus von Kruskal für MST?
Rückseite
Sortiert alle Kanten nach Gewicht, fügt sie aufsteigend hinzu, wenn sie keinen Zyklus erzeugen (Union-Find), bis n-1 Kanten erreicht sind.
Wie funktioniert der Algorithmus von Prim für MST?
Rückseite
Startet mit einem Knoten, erweitert den Baum iterativ um die leichteste Kante, die einen neuen Knoten verbindet (Priority Queue).
Warum ist Dijkstra ein Greedy-Algorithmus?
Rückseite
Wählt in jedem Schritt den unerreichten Knoten mit minimalem Tentativabstand (gierige Wahl) und finalisiert dessen kürzesten Pfad.
Was ist die Idee der Huffman-Codierung?
Rückseite
Baut einen binären Baum bottom-up: vereint stets die zwei seltensten Symbole zu einem Knoten, dessen Gewicht die Summe ist; ergibt präfixfreie optimale Codes.
Wie löst Greedy das Aktivitätsauswahl-Problem?
Rückseite
Sortiert Aktivitäten nach Endzeit, wählt stets die frühest endende, die mit der letzten gewählten nicht kollidiert – liefert optimale maximale Menge.
Warum funktioniert Greedy beim bruchteilbaren Rucksack, aber nicht beim 0/1-Rucksack?
Rückseite
Bruchteilbar: Wert-Gewicht-Verhältnis sortieren, nehmen was passt – optimal. 0/1: Gegenbeispiel zeigt, dass lokale Optimalität (höchster Wert/kg) nicht global optimal ist.
Wann liefert der gierige Münzwechsel die optimale Lösung?
Rückseite
Bei kanonischen Münzsystemen (z. B. Euro: 1,2,5,10,20,50,100,200), wo jede Münze ein Vielfaches der vorherigen ist oder bestimmte Bedingungen erfüllt.
Was ist ein Matroid im Kontext von Greedy-Algorithmen?
Rückseite
Eine Struktur (Menge + unabhängige Teilmengen), die Vererbbarkeit und Austauscheigenschaft erfüllt; Greedy findet darauf für Gewichtsfunktionen immer ein Optimum.
Nenne einen Nachteil von Greedy-Algorithmen.
Rückseite
Keine Garantie für globales Optimum bei beliebigen Problemen; ohne Beweis von Greedy-Choice-Property und optimaler Substruktur kann die Lösung willkürlich schlecht sein.
Gib ein Beispiel, wo Greedy nicht optimal ist.
Rückseite
0/1-Rucksack: Gegenstände (Wert/Gewicht): A(60/10), B(100/20), C(120/30), Kapazität 50. Greedy nimmt A+B (160), Optimum ist B+C (220).