Aufgabenblatt 12 - Universität Augsburg

Informatik III
Universität Augsburg
Wintersemester 2016/17
Prof. Dr. W. Vogler
Moritz Laudahn, M.Sc.
Aufgabenblatt 12
Aufgabe 1 (Nachtrag zum Weihnachtsfest)
Algo und Loga Rithmic beschließen, ihrem Kind zu Weihnachten eine besondere Freude
machen. Zu diesem Zweck stapeln sie n Geschenke zu einem Haufen, so dass jedes Geschenk
einer Schicht (mit Ausnahme der untersten) auf zwei Geschenken der Schicht darunter
liegt und jedes Geschenk mit Ausnahme eines einzelnen Geschenks an der Spitze genau ein
Geschenk unmittelbar über sich hat. Sei k = log(n + 1) die Anzahl der Schichten. Das Kind
darf sich k Geschenke nehmen, aber es darf sich ein Geschenk nur dann nehmen, wenn kein
anderes Geschenk mehr darauf liegt.
Um die Wahl nicht komplett zufällig zu gestalten, haben die Eltern auf jedes Geschenk
einen Schätzwert (∈ N, ohne Wiederholungen) geschrieben, der aussagt wie sehr sich das
Kind über das Geschenk freuen wird. Dabei sind die Geschenke so angeordnet, dass jedes
Geschenk zwei wertvollere verdeckt.
Unser Ziel ist es nun, k Geschenke so zu wählen, dass die Freude maximal ist.
a) Beweisen Sie, dass eine Wahl von Geschenken mit maximaler Freude von jeder Schicht
genau ein Geschenk enthalten muss. (8 Punkte)
b) Beschreiben Sie einen Algorithmus, der eine optimale Wahl bestimmt. Sie dürfen dazu
Verfahren verwenden und/oder anpassen, die aus der Vorlesung bzw. den Übungen
bekannt sind. Beschreiben Sie auch knapp, wieviel Speicherplatz Sie benötigen und
wie Sie ihn verwenden. Welche Laufzeit hat Ihr Verfahren? Falls Ihr Algorithmus
in mehreren Phasen arbeitet, so nutzen die Gegebenheiten auch für einzelne Phasen
möglichst effizient. (12 Punkte)
Aufgabe 2
a) Beschreiben Sie ein Verfahren, das für einen Graphen G und eine Sequenz seiner Ecken
v1 , . . . , vn in O(n + m) Zeit prüft, ob die Sequenz einen Hamiltonischen Kreis bildet.
Welchen Unterschied macht die Speicherung des Graphen in Adjazenzlisten oder einer
Adjazenzmatrix für Ihr Verfahren? (8 Punkte)
b) Führen Sie Teil i) des Beweises von Satz 8.4 genauer als im Skript, indem Sie ein
passendes, effizientes Programm in Pseudocode angeben. Machen Sie zunächst klar, wie
Sie eine Belegung codieren. Beschreiben Sie bei Bedarf benutzte Methoden für Literale,
z.B.: int index(Literal l). (8 Punkte)
1
Aufgabe 3
Die Firma Ranzsoft verkauft eine tatsächlich funktionierende Kürzeste-Wege-Blackbox, die
Dijkstras Algorithmus anwendet. Man kann sie per USB an seinen Computer anschließen,
ihr einen gewichteten ungerichteten Graphen ohne negative Kantengewichte sowie eine Startecke s zusenden und erhält nach O(m + n log n) Berechnungszeit den Baum aller kürzesten
Wege mit s als Wurzel. Da die Firmenleitung wünscht, dass die Kunden für jede Berechnung der Firma Geld zahlen, funktioniert die Blackbox nur einmal und sabotiert sich dann
selbst.
Gegeben ein ungerichteter Graph G ohne negative Kantengewichte. Gesucht ist ein
kürzester Weg von einer Ecke s zu einer Ecke z, der über eine Ecke x führt. (Für x =
vi+1 eines solchen s,x,z-Weges v1 v2 . . . vn sei hierbei die im Skript auf Seite 52 genannte
Nebenbedingung vi 6= vi+2 außer Kraft gesetzt.) Beschreiben Sie ein Verfahren, das effizient
einen derartigen kürzesten Weg findet und dabei ein einziges Mal Dijkstras Algorithmus
als Methode verwendet.
Beweisen Sie die Korrektheit Ihres Verfahrens und begründen Sie seine Effizienz. (12
Punkte)
Aufgabe 4
Beweisen Sie die Korrektheit von Kruskals Algorithmus (Skript s. 80f). Zeigen Sie dafür,
wie bei Prim, durch Induktion über k, dass ∃ M ST M : Tk ⊆ M . (10 Punkte)
Informationen:
• Abgabe: Bis spätestens Donnerstag, den 26.01.2017 um 12:00 im entsprechend beschrifteten Briefkasten.
2

Download Report