Transcript
Lehrstuhl für Informatik I Algorithmen, Komplexität und wissensbasierte Systeme
Universität Würzburg
Würzburg, den 10. Januar 2017 Prof. Dr. Alexander Wolff Fabian Lipp, M. Sc. Andre Löffler, M. Sc. Johannes Blum, B. Sc.
4. Präsenzübungsblatt zur Vorlesung Algorithmen und Datenstrukturen (Winter 2016/17) Aufgabe 1 – Tödlicher Bocksbeutel Vor langer Zeit lebte in Franken ein guter König, der in seinem Weinkeller tausend Bocksbeutel kostbaren Weines verwahrte. Eines Tages ertappten seine Wachen einen (bayerischen) Agenten, der gerade dabei war des Königs Wein zu vergiften. Zwar wusste man, dass der Agent es nur geschafft hatte eine einzige Flasche zu präparieren, allerdings war es ihm im Handgemenge bei seiner Festnahme gelungen, die Flasche zu den anderen zu stellen, so dass niemand wusste, welcher Bocksbeutel vergiftet war. Das Gift war tödlich; schon ein Tropfen des vergifteten Weines führte unweigerlich zum Tod. Dabei wirkte das Gift sehr langsam; nach genau einem Monat erlag man urplötzlich an seinen Folgen. Da er seinen Wein sehr liebte, wollte er das Ergebnis innerhalb eines Monats kennen. Leider stehen ihm dafür nur zehn mutige Vorkoster zur Verfügung. Zeigen Sie dem König, dass diese zehn Vorkoster ausreichen. Aufgabe 2 – Bäume transformieren Als ADS-HörerIn stellen Sie sich zu Hause natürlich nicht irgendeinen, sondern einen binären Such-Weihnachtsbaum auf. Ihr Such-Weihnachtsbaum heißt B1 und hat n Knoten. Ihr(e) Übungspartner(in) hat auch einen binären Such-Weihnachtsbaum, der B2 genannt wird und zufälligerweise genau dieselben Schlüssel wie Ihr SuchWeihnachtsbaum enthält. Er sieht aber schöner aus. Deshalb möchten Sie Ihren SuchWeihnachtsbaum so transformieren, dass er am Ende wie B2 aussieht. Zeigen Sie hierzu, dass Sie stets in der Lage sind B1 durch O(n) Rotationen in B2 zu transformieren, egal wie die beiden binären Such-Weihnachtsbäume konkret aussehen. Hinweis: Zeigen Sie zunächst, dass n − 1 Rotationen ausreichen, um einen beliebigen Such-Weihnachtsbaum in einen Such-Weihnachtsbaum zu transformieren, in dem kein Knoten einen linken Kindknoten hat.
Aufgabe 3 – Schlange aus zwei Stapeln analysieren Eine Schlange Q lässt sich folgendermaßen durch das Verwenden von zwei Stapeln S1 und S2 darstellen: • Enqueue(x): führe S1 .Push(x) aus – lege also x auf den ersten Stapel. • Dequeue(): Sollte S2 leer sein, führe solange S2 .Push(S1 .Pop()) aus, bis S1 leer ist – die Elemente von S1 werden einzeln der Reihe nach auf S2 verschoben. Danach führe S2 .Pop() aus. • Empty(): gibt true zurück, falls S1 und S2 leer sind, sonst false. Betrachten Sie nun eine zufällige Folge der Länge n bestehend aus Enqueue-, Dequeueund Empty-Operationen auf Q. a) Argumentieren Sie, warum die Worst-Case-Laufzeit einer einzelnen DequeueOperation auf Q in Θ(n) liegt. b) Zeigen Sie mit Hilfe von amortisierter Analyse, dass die Gesamtlaufzeit für jede Folge ebenfalls in Θ(n) liegt. Eine einzelne Dequeue-Operation benötigt amortisiert also nur konstante Laufzeit. Wieso ist dies kein Widerspruch zu Teilaufgabe a)?
Diese Aufgaben werden eventuell gemeinsam in den Übungen am 10.01. und 11.01. gelöst. Sie brauchen Sie nicht vorher zu lösen und auch nicht abzugeben.
