Fakultät für Informatik Professur Theoretische Informatik und Informationssicherheit Wintersemester 2006/07 Prof. Dr. Hanno Lefmann Theoretische Informatik I 7. Übung Aufgabe 1 Eine Person möchte einen bestimmten Geldbetrag so bezahlen, dass sie kein Wechselgeld bekommt. Sie hat dafür beliebig viele Münzen mit den Werten (a1 ,a2 ,...,an ) zur Verfügung (bei der Euro-Wä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 Münzen auszahlt wie möglich. Unsere Person benutzt die Greedy-Strategie: Sie zahlt so viele Münzen mit dem höchsten Wert aus wie möglich, dann so viele Münzen wie möglich mit dem zweithöchsten Wert usw. Entwerfen Sie ein Münzsystem (also eine Folge von Münzwerten (a1 ,a2 ,...,an )), für das die Greedy-Strategie nicht optimal ist. Aufgabe 2 Zeigen Sie, dass die Greedy-Strategie beim Geldauszahlen für die EuroWährung optimal ist, d.h. immer die minimal mögliche Anzahl an Mü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 für die beiden Computer 1 ≤ i < j ≤ n. Geben sie einen mö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 möglichst groß ist.
© Copyright 2024 ExpyDoc
