Aufgabenblatt 10 - Universität Augsburg

Informatik III
Universitä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)
erwähnt, bei der statt der Größe einer Klasse die Höhe des Baumes eingetragen wird.
Beweisen Sie, dass Lemma 5.1 auch für diese Variante, also für die entsprechende Klasse
von Union-Find-Bä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 äquivalent sind, indem Sie zeigen, dass (ii) ⇔ (i)
⇔ (iii). (13P)
(i) G ist ein Baum
(ii) G ist zusammenhä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 dürfen Sie die
Behauptung aus Teilaufgabe a) verwenden.
Aufgabe 3
Geben Sie einen Algorithmus mit hö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 verä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. Begründen
Sie knapp die Korrektheit Ihrer Lö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
Gefäßen, die 20 l, 21 l, . . ., 2n−1 l fassen. Da sich die Substanz an der Luft langsam zersetzt,
achtet er darauf, dass jedes Gefäß entweder randvoll oder komplett leer ist. Sind also z.B.
genau die Gefäße voll, die 1l, 2l und 4l fassen, so kann deren Inhalt zusammen mit dem neu
produzierten Liter in ein Behältnis der Kapazität 8l umgefüllt werden. Immer, wenn die
Lagerkapazität erschöpft ist, kommt am nächsten Tag ein Bote, der die Tagesproduktion
sowie den an den Vortagen angesammelten Vorrat der Substanz in einem Transportbehältnis abholt. Aus versicherungstechnischen Gründen darf der Bote das Entleeren der Gefäße
und das Versiegeln seines Transportbehältnisses nicht selbst übernehmen.
a) Wie häufig kommt der Bote? (2P)
b) Der Chemiker möchte das Umfüllen nicht mehr selbst machen und beschließt einen Praktikanten einzustellen. Angenommen das Versiegeln eines randvoll gefüllten Gefäßes oder
des Transportbehältnisses des Boten sowie das Entleeren des Inhalts eines Gefäßes in
ein größeres Gefäß/das Transportbehältnis dauert jeweils eine Minute. Über wie viele
Minuten pro Tag sollte der Arbeitsvertrag des Prakikanten durchnittlich laufen, wenn
am ersten Arbeitstag des Praktikanten alle Gefäße leer sind? (12P)
Hinweis: Finden Sie eine geeignete Potenzialfunktion und bestimmen Sie mit deren Hilfe
eine möglichst gute obere amortisierte Anzahl an Minuten, die pro Tag mit dem Entleeren
und Versiegeln von Gefäßen verbracht werden müssen.
c) Bonusfrage für Motivierte: Der Praktikant möchte es vermeiden an manchen Tagen n
Minuten lang arbeiten zu müssen. Aufgrund einer unerwarteten Budgeterhöhung stehen
von nun an zwei Gefäße jeder Größe zur Verfügung. Ist es nun möglich den WorstCase Zeitbedarf pro Tag auf einen Wert kleiner als n beispielsweise ⌈log n⌉ oder gar
eine Konstante c nach oben zu beschränken? Falls ja: Wie muss der Praktikant dafür
vorgehen? Was ist die Anforderung für die Bereitschaft des Boten? Falls nein: Woran
scheitert es? Können Sie Ihre Aussage beweisen? (keine Punkte, keine Korrektur)
Informationen:
• Abgabe: Bis spätestens Donnerstag, den 12.01.2017, um 12:00 im entsprechend beschrifteten Briefkasten.
2

Download Report