TU Ilmenau, Fakultät für Informatik und Automatisierung FG Komplexitätstheorie und Effiziente Algorithmen Univ.-Prof. Dr. M. Dietzfelbinger, M.Sc. Stefan Walzer http://www.tu-ilmenau.de/iti/lehre/lehre-ws-20152016/ea/ Effiziente Algorithmen – Übung 11 Besprechung am 20. bzw. 22. Januar 2016 Abgabe von Lösungsvorschlägen für die markierten Aufgaben (*) bis zum 20.1.2015, 11:00 Uhr, per EMail an [email protected] oder direkt in meinem Büro (Zusebau R 1057). Bitte nennen Sie auch einen Übungstermin, an dem Sie Ihre Lösung vorstellen möchten! Aufgabe 1 (Fibonacci-Heaps) Führen Sie auf dem folgenden Fibonacci-Heap die Operationen insert(11), decreaseKey(v,22), decreaseKey(w,8) und deleteMin() hintereinander aus. Grau unterlegte Knoten sind dabei markiert. 7 26 24 17 46 30 18 23 21 38 39 41 52 v 35 w Aufgabe 2 (Zweiendige Prioritätswarteschlage)* Gesucht ist eine Datenstruktur, die zusätzlich zu den Operationen eines Fibonacci-Heaps auch noch Folgendes unterstützt: • increaseKey(v,x): Erhöhe den Schlüssel, auf den v zeigt, auf x. (Fehler wenn x kleiner als der alte Schlüssel von v ist.) • max(): Gib einen Eintrag mit maximalem Schlüssel aus. • deleteMax(): Gib einen Eintrag mit maximalem Schlüssel aus und lösche ihn aus der Datenstruktur. Die alten Operationen (insert, meld, deleteMin, min) sollen in der neuen Datenstruktur allenfalls um einen konstanten Faktor und/oder Summanden teurer sein als in Fibonacci-Heaps. Die neuen Operationen increaseKey und deleteMax sowie die alte Operation decreaseKey sollen amortisierte Kosten O(log n) haben, die neue Operation max soll amortisierte Kosten O(1) haben. Effiziente Algorithmen – Übung 11 2 Hinweis: Nutzen Sie die delete Operation aus der Vorlesung. Um max und deleteMax zu realisieren, benötigen Sie möglicherweise zusätzlichen Platz. Aufgabe 3 (Zweifelhafte Abwandlungen)* Auf der Conference for Rarely Accurate Propositions (CRAP) werden die neuesten Innovationen im Bereich von Fibonacci-Heaps diskutiert. (a) Professor Pinocchio behauptet, dass auf die Markierung von Knoten (und die sich daraus ergebenen kaskadierenden Schnitte) verzichtet werden kann, ohne die amortisierten Kosten der Operationen zu beeinträchtigen. (b) Professor Pisa behauptet, dass ein Fibonacci-Heap nach n Operationen Tiefe O(log n) hat. (c) Professor Schnurrbart stellt seine neuartige Operation quickDelete(v) vor, die angewendet werden darf, wenn v nicht das aktuelle Minimum ist und der Vaterknoten von v (falls existent) nicht markiert ist. In dem Fall wird v gelöscht, indem zunächst die (zyklische) Kindliste von v in die (zyklische) Wurzelliste eingehängt wird. Anschließend wird der Knoten v aus der Kindliste seines Vaterknotens ausgehängt und der Vaterknoten wird markiert (falls v einen Vater hat). Amortisierte Kosten hin oder her, Professor Schnurrbart behauptet, seine Operation von quickDelete sei korrekt und habe echte Kosten O(1). Zeigen Sie, dass die Behauptungen Unsinn sind. Geben Sie möglichst konkrete Gegenbeispiele an. Bonuspunkteregelung: Da die ersten beiden Teilaufgaben gar nicht so einfach sind, genügt es für einen Bonuspunkt wenn Sie zwei von drei Teilaufgaben lösen. Teilnehmer die alle drei Teilaufgaben lösen, werden bei der Auswahl allerdings bevorzugt. Hinweis zu (c): Brüten Sie über Abbildung 4.5 im Skript.