KIT Jun.-Prof. Henning Meyerhenke, Jun.-Prof. Dennis Hofheinz Institut für Theoretische Informatik Christian Staudt, Christoph Striecks 6. Übungsblatt zu Algorithmen I im SS 2015 https://crypto.iti.kit.edu/algo-sose15 {staudt,striecks}@kit.edu Mit Lösungsvorschlägen Aufgabe 1 (Algorithmendesign, 2 + 2 Punkte) Gegeben sei eine sortierte Liste mit n Elementen. Nun haben Sie k ≤ n neue unsortierte Elemente in einem Array, die in die sortierte Liste einfügt werden sollen, sodass die Liste nach dem Einfügen weiter sortiert ist. a) Geben Sie einen Algorithmus an, der Laufzeit O(kn) hat und das Problem löst. b) Geben Sie nun einen Algorithmus an, der Laufzeit O(k log k + n) hat und das Problem löst. Lösungsvorschlag: a) Man füge die Elemente nacheinander in die sortierte Liste ein. Um ein Element einzufügen, macht man lineare Suche: Man geht die Liste Stück für Stück durch und vergleicht den Wert des aktuellen Elements mit dem Wert des einzufügenden Elements, bis man die richtige Stelle gefunden hat. Die lineare Suche hat pro einzufügendem Element Aufwand O(n + k), da im schlimmsten Fall die ganze Liste durchlaufen werden muss. Da wir k Elemente einfügen, ergibt sich somit ein Gesamtaufwand von O(k(n + k)) und da k ≤ n die Abschätzung des Gesamtaufwands O(kn). b) Nun gehen wir ein wenig anders vor. Zuerst sortieren wir das Array der neuen Elemente in Zeit O(k log k) zum Beispiel mit dem Algorithmus Mergesort aus der Vorlesung. Das sortierte Array wird dann in eine Liste konvertiert. Dann haben wir zwei sortierte Listen: in der einen sortieren Liste befinden sich die k neuen Elemente und in der anderen befinden sich die n alten sortierten Elemente. Nun verwenden wir die Funktion merge (aus Mergesort) und erhalten so in Zeit O(n) eine sortierte Liste, die die Elemente beider Listen enthält. Insgesamt ergibt sich also ein Aufwand von O(k log k + n). Aufgabe 2 (Paralleles Sortieren, 3 Punkte) Die Ausführungszeit eines parallelen Algorithmus zum vergleichsbasierten Sortieren von n Elementen auf p Prozessoren sei n log2 n T (p) ∈ Θ . p Geben Sie den absoluten Speedup (Beschleunigung) und die absolute Effizienz an. Der Speedup ist das Verhältnis von sequenzieller Laufzeit zu paralleler Laufzeit in Abhängigkeit von p. Die Effizienz ist definiert als Speedup geteilt durch die Anzahl der Prozessoren, wieder in Abhängigkeit von p. Wie muss die Prozessorzahl mit der Eingabegröße asymptotisch steigen, damit der Speedup konstant bleibt? Nehmen Sie immer den schlechtesten Fall an und rechnen Sie im Θ-Kalkül. 1 Lösungsvorschlag: Der absolute Speedup ist definiert als S(p) = Tseq , T (p) wobei p die Prozessorzahl, Tseq die asymptotische Ausführungszeit des besten sequentiellen Algorithmus ist. Die (absolute) Effizienz ist definiert als Tseq S(p) = . p pT (p) E(p) = Die besten sequentiellen Algorithmen für vergleichsbasiertes Sortieren haben Laufzeit Θ(n log n). Damit ist der Speedup Θ(n log n) p =Θ S(p) = 2 log n Θ n log n p und die Effizienz Θ E(p) = p log n p =Θ 1 log n Aus konstantem Speedup S(p) = Θ p log n ! = Θ(1) folgt p ∈ Θ(log n). Aufgabe 3 (Doktor Meta, 2 + 2 Punkte) Der ebenso geniale wie fundamental fehlentworfene Robotergehilfe und Untersuperbösewicht Røbøt ist auf einem Bein und einem Rad auf dem Weg durch Doktor Metas geheime Basis in den Tunnelsystemen unter Karlsruhe. Seine neue Entdeckung sollte allen Verdacht beseitigen, dass ihm einige essentielle Schaltkreise fehlen — er hat eine Prioritätsliste entwickelt, die für beliebige Objekte und Ordnungen funktioniert und dennoch alle Prioritätslisten-Operationen (insert, deleteMin) in O(1) erledigen kann. Doktor Meta ist sehr interessiert an dieser Datenstruktur. Røbøt kann sich gerade nicht an den Quellcode erinnern, aber Doktor Meta vermutet, dass er in der Zwischenzeit schon einen Algorithmus auf Basis der neuen Prioritätsliste entwickeln kann, der seine stetig wachsende Liste von Gegenspielern nach ihrer Bedrohung sortiert. a) Sei die Prioritätslisten-Datenstruktur RøbøList gegeben, welche die Operationen insert und deleteMin (wie in der Vorlesung) abstrakt bereithält. Nehmen Sie an, dass beide Operationen in konstanter Zeit ausgeführt werden können. Nutzen Sie RøbøList, um einen Algorithmus anzugeben, der ein Array A[1..n], für n ∈ N, von natürlichen Zahlen in O(n) sortiert. Geben Sie den Algorithmus in Pseudocode an. b) Nehmen Sie an, dass eine RøbøList-Implementierung der deleteMin-Operation ausschließlich vergleichsbasiert und deterministisch arbeitet. Begründen Sie ausführlich, warum die Laufzeit einer derartigen deleteMin-Implementierung im schlechtesten Fall eine untere Schranke von Ω(log n) besitzt. Lösungsvorschlag: a) Folgender Pseudocode beschreibt das Sortieren eines Arrays A[1..n], wobei die PrioritätslistenDatenstruktur RøbøList benutzt wird. 2 Function røbøSort(A : Array [0..n − 1]; n : N) : Array [0..n − 1] for i := 1 to n do insert(A[i − 1]) for i := 1 to n do A[i − 1] = deleteMin return A b) Die RøbøList-Methoden insert und deleteMin können genutzt werden, um einen vergleichsbasierten deterministischen Sortieralgorithmus zu konstruieren. (Siehe Teilaufgabe a).) Der Satz aus der Vorlesung auf Folie 178 sagt aus, dass die Laufzeit jedes vergleichsbasierten deterministischen Sortieralgorithmus im schlechtesten Fall in Ω(n log n) liegt. Da wir laut Aufgabenstellung annehmen, dass insert in O(1) läuft, muss folglich deleteMin eine Laufzeit von Ω(log n) im schlechtesten Fall besitzen. 3