Greedy-Muster

Beginner Algorithmen und Datenstrukturen Deutsch

Also available: English

Created by Best · 16.08.2026 at 09:13 UTC

Greedy wählt lokal optimale Schritte in der Hoffnung auf ein globales Optimum. Manchmal korrekt (Huffman, Intervallscheduling mit richtiger Regel), manchmal nur Heuristik.

Beweisbedarf: Matroid oder Austauschargument, sonst Gegenbeispiel.

Wo gebraucht

Scheduling nach Deadline, Huffman-ähnliche Codierung, kanonischer Münzwechsel, Activity Selection. Schnell, aber nur korrekt mit Beweis oder klarem Gegenbeispiel-Check.

Vertiefung

Ein Greedy-Algorithmus baut eine Lösung schrittweise auf und wählt jeweils den nach einem Kriterium günstigsten nächsten Schritt. Frühere Entscheidungen werden im normalen Ablauf nicht erneut untersucht. Effizienz allein beweist jedoch nicht, dass das Resultat global optimal ist.

Ein Korrektheitsbeweis verwendet häufig ein Austauschargument: Eine optimale Lösung lässt sich so umformen, dass sie die Greedy-Entscheidung enthält, ohne schlechter zu werden. Alternativ zeigt eine Greedy-Choice-Eigenschaft zusammen mit optimaler Teilstruktur, dass die Restaufgabe dieselbe Form behält.

Schwierigkeitsstufen

Wahlregel und verbleibende Teilaufgabe benennen.
Ein Gegenbeispiel für eine plausible Regel suchen.
Ein Austauschargument für eine korrekte Regel formulieren.

Fallstricke

Eine anschauliche Heuristik ist noch kein Beweis. Besonders bei Gewichten oder Nebenbedingungen kann eine zunächst günstige Entscheidung spätere Möglichkeiten so einschränken, dass das Gesamtergebnis schlechter wird.

University approvals: 0

Tasks

Question 1

Was charakterisiert Greedy?

Immer Backtracking über alle Äste

Lokale Wahl ohne Rücknahme der Entscheidung

Nur Merge Sort

Nur Threads

Question 2

Welche Beweisidee stützt eine Greedy-Wahl am direktesten?

Jede optimale Lösung kann ohne Verschlechterung an diese erste Wahl angepasst werden.

Die Wahl sieht in einem einzelnen Beispiel plausibel aus.

Der Algorithmus verwendet keine Schleife.

Alle späteren Entscheidungen werden zufällig getroffen.

Question 3

Bestimme mit dem Greedy-Verfahren die maximale Anzahl nichtüberlappender Aktivitäten. Die Intervalle sind nach Endzeit sortiert.

Hint

Auf Start und Ende eines Intervalls greifst du mit interval[0] und interval[1] zu. Über int[][] ist eine for-each-Schleife möglich.

class Activities {
  static int activityCount(int[][] intervals) {
    // TODO
    return 0;
  }
}

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Algorithmen und Datenstrukturen
Difficulty: Beginner
Completed: 0 users

Creator

Best

BestBuddy