Theoretische Informatik I

Fakultät für Informatik
Professur Theoretische Informatik
und Informationssicherheit
Wintersemester 2006/07
Prof. Dr. Hanno Lefmann
Theoretische Informatik I
7. Übung
Aufgabe 1 Eine Person möchte einen bestimmten Geldbetrag so bezahlen, dass
sie kein Wechselgeld bekommt. Sie hat dafür beliebig viele Münzen mit den Werten
(a1 ,a2 ,...,an ) zur Verfügung (bei der Euro-Währung ist z.B. a1 = 1, a2 = 2, a3 = 5
usw.). Es gibt nun verschiedene Strategien, das Geld auszuzahlen. Optimal ist eine
Strategie genau dann, wenn sie so wenige Münzen auszahlt wie möglich. Unsere Person benutzt die Greedy-Strategie: Sie zahlt so viele Münzen mit dem höchsten Wert
aus wie möglich, dann so viele Münzen wie möglich mit dem zweithöchsten Wert
usw. Entwerfen Sie ein Münzsystem (also eine Folge von Münzwerten (a1 ,a2 ,...,an )),
für das die Greedy-Strategie nicht optimal ist.
Aufgabe 2 Zeigen Sie, dass die Greedy-Strategie beim Geldauszahlen für die EuroWährung optimal ist, d.h. immer die minimal mögliche Anzahl an Münzen bezahlt.
Aufgabe 3 Wir betrachten gewichtete Graphen mit reellen Kantengewichten G =
(V, E, w : E → R). Zeigen Sie, dass der Algorithmus von Kruskal auch mit diesen
Kantengewichten einen minimalen Spannbaum findet, und dass er leicht so modifiziert werden kann, dass er einen maximalen Spannbaum findet, d. h. eine Teilmenge
T der Kantenmenge E, so dass (V, T ) ein Baum ist und so dass T maximales Gewicht
hat unter allen solchen Teilmengen.
Aufgabe 4 Es sei ein Netzwerk von n ∈ N Computern gegeben, in dem je zwei
eine direkte Verbindung besitzen, die eine Ausfallwahrscheinlichkeit von pij ∈ (0, 1)
besitzt für die beiden Computer 1 ≤ i < j ≤ n. Geben sie einen möglichst effizienten
Algorithmus an, der in dem Graphen, der dieses Netzwerk modelliert, eine Spannbaum findet, so dass die Wahrscheinlichkeit, dass alle Verbindungen des Spannbaums
gleichzeitig funktionieren möglichst groß ist.

Download Report