Informatik III Universität Augsburg Wintersemester 2016/17 Prof. Dr. W. Vogler Moritz Laudahn, M.Sc. Aufgabenblatt 10 Aufgabe 1 In der Vorlesung wurde eine Variante des Union-Find mit schnellem Union (Kap. 5.2) erwähnt, bei der statt der Größe einer Klasse die Höhe des Baumes eingetragen wird. Beweisen Sie, dass Lemma 5.1 auch für diese Variante, also für die entsprechende Klasse von Union-Find-Bäumen, gilt. (7P) Aufgabe 2 Sei G ein ungerichteter Graph mit n ≥ 1. a) Beweisen Sie ohne Induktion: G ist ein Baum mit n ≥ 2 ⇒ G hat mindestens ein Blatt. (5P) b) Beweisen Sie, dass folgende Aussagen äquivalent sind, indem Sie zeigen, dass (ii) ⇔ (i) ⇔ (iii). (13P) (i) G ist ein Baum (ii) G ist zusammenhängend mit m = n − 1 (iii) G ist kreislos mit m = n − 1 Tipp: Um aus (i) etwas zu folgern, bietet sich Induktion an. Bei Bedarf dürfen Sie die Behauptung aus Teilaufgabe a) verwenden. Aufgabe 3 Geben Sie einen Algorithmus mit höchstens 150 Zeichen an, der mit konstantem Speicher ein nicht-rekursives Find mit Pfadkompression realisiert. (9P) Aufgabe 4 Betrachten Sie einen ungerichteten Baum, in dem die Ecken mit ganzzahligen Werten beschriftet sind, und eine Ecke r. Beschreiben (6= implementieren) Sie, wie Tiefensuche von r aus so verändert werden kann, dass sie bestimmt, ob eine Ecke den Wert x hat. Im positiven Fall soll zudem ein Weg von r zu x bzw. umgekehrt ausgegeben werden. Begründen Sie knapp die Korrektheit Ihrer Lösung. (13P) 1 Aufgabe 5 Ein Chemiker der Firma Ranzchem, einer Tochterfirma von Ranzsoft, stellt am Tag exakt einen Liter (1l) einer speziellen Substanz her. Diese Substanz lagert er in n speziellen Gefäßen, die 20 l, 21 l, . . ., 2n−1 l fassen. Da sich die Substanz an der Luft langsam zersetzt, achtet er darauf, dass jedes Gefäß entweder randvoll oder komplett leer ist. Sind also z.B. genau die Gefäße voll, die 1l, 2l und 4l fassen, so kann deren Inhalt zusammen mit dem neu produzierten Liter in ein Behältnis der Kapazität 8l umgefüllt werden. Immer, wenn die Lagerkapazität erschöpft ist, kommt am nächsten Tag ein Bote, der die Tagesproduktion sowie den an den Vortagen angesammelten Vorrat der Substanz in einem Transportbehältnis abholt. Aus versicherungstechnischen Gründen darf der Bote das Entleeren der Gefäße und das Versiegeln seines Transportbehältnisses nicht selbst übernehmen. a) Wie häufig kommt der Bote? (2P) b) Der Chemiker möchte das Umfüllen nicht mehr selbst machen und beschließt einen Praktikanten einzustellen. Angenommen das Versiegeln eines randvoll gefüllten Gefäßes oder des Transportbehältnisses des Boten sowie das Entleeren des Inhalts eines Gefäßes in ein größeres Gefäß/das Transportbehältnis dauert jeweils eine Minute. Über wie viele Minuten pro Tag sollte der Arbeitsvertrag des Prakikanten durchnittlich laufen, wenn am ersten Arbeitstag des Praktikanten alle Gefäße leer sind? (12P) Hinweis: Finden Sie eine geeignete Potenzialfunktion und bestimmen Sie mit deren Hilfe eine möglichst gute obere amortisierte Anzahl an Minuten, die pro Tag mit dem Entleeren und Versiegeln von Gefäßen verbracht werden müssen. c) Bonusfrage für Motivierte: Der Praktikant möchte es vermeiden an manchen Tagen n Minuten lang arbeiten zu müssen. Aufgrund einer unerwarteten Budgeterhöhung stehen von nun an zwei Gefäße jeder Größe zur Verfügung. Ist es nun möglich den WorstCase Zeitbedarf pro Tag auf einen Wert kleiner als n beispielsweise ⌈log n⌉ oder gar eine Konstante c nach oben zu beschränken? Falls ja: Wie muss der Praktikant dafür vorgehen? Was ist die Anforderung für die Bereitschaft des Boten? Falls nein: Woran scheitert es? Können Sie Ihre Aussage beweisen? (keine Punkte, keine Korrektur) Informationen: • Abgabe: Bis spätestens Donnerstag, den 12.01.2017, um 12:00 im entsprechend beschrifteten Briefkasten. 2
© Copyright 2024 ExpyDoc