Also ich habe drei Aufgaben, welche jeweils ein Problem geben und ich einen Greedy Algorithmus entwickeln soll, dann die Laufzeit und den Speicherverbrauch berechnen und anschließend beweisen, dass dieser Algorithmus optimal ist. Die ersten beiden Teilaufgaben habe ich bereits gelöst. Jedoch bei dem Beweis hänge ich im Moment etwas...xD
Uns wurden zwei Beweis Strategien vorgestellt: Einmal "Greedy stays ahead" und "Greedy Exchangeargument".
Ich wollte diese Beweise gerne mit "Greedy stays ahead" führen.
Der erste Schritt dieses Beweises ist es ja erstmal eine Lösung zu konstruieren (was ich bereits getan habe). Im zweiten Schritt soll man ein "Measure" finden.
Hier stellt sich meine Frage:
Soll ich mir hier einen beliebigen "Non" Greedy Algorithmus ausdenken? Also beispielsweise man soll Aufgaben schedulen und die Aufgaben habe eine verschiedene Arbeitsdauer. Somit wäre mein Greedy Algorithmus ja die Aufgaben erstmal aufsteigend nach Arbeitszeit zu sortieren um so viele wie möglich in einer gewissen Zeit abzuhandeln.
Der Comparison Algorithmus könnte dann also z.B. sein: Aufgaben absteigend nach Arbeitszeit sortieren und in dieser Reihenfolge abarbeiten? Und dann muss ich ich für alle Indizes zeigen, dass der Greedy Algorithmus immer besser ist ?
Uns wurden zwei Beweis Strategien vorgestellt: Einmal "Greedy stays ahead" und "Greedy Exchangeargument".
Ich wollte diese Beweise gerne mit "Greedy stays ahead" führen.
Der erste Schritt dieses Beweises ist es ja erstmal eine Lösung zu konstruieren (was ich bereits getan habe). Im zweiten Schritt soll man ein "Measure" finden.
Hier stellt sich meine Frage:
Soll ich mir hier einen beliebigen "Non" Greedy Algorithmus ausdenken? Also beispielsweise man soll Aufgaben schedulen und die Aufgaben habe eine verschiedene Arbeitsdauer. Somit wäre mein Greedy Algorithmus ja die Aufgaben erstmal aufsteigend nach Arbeitszeit zu sortieren um so viele wie möglich in einer gewissen Zeit abzuhandeln.
Der Comparison Algorithmus könnte dann also z.B. sein: Aufgaben absteigend nach Arbeitszeit sortieren und in dieser Reihenfolge abarbeiten? Und dann muss ich ich für alle Indizes zeigen, dass der Greedy Algorithmus immer besser ist ?