Universität zu Köln Institut für Informatik Dr. O. Schaudt A. van der Grinten Übung zu Parallele Algorithmen Blatt Nr. 5 Dieses Übungsblatt muss bis zum 25.05.2016, 15:30 abgegeben werden. Schreiben Sie Ihren Namen und Ihre Übungsgruppe oben auf die Abgabe! Aufgabe 1: Pre- und Postorder (15 Punkte) (a) Entwickeln Sie auf Basis von Aufgabe 2 des letzten Blattes Verfahren um die Pre- und Postorder in gewurzelten Bäumen mit O(n) Prozessoren in Zeit O(log n) zu berechnen. (6 Punkte) (b) Geben Sie an, wie man aufgrund dieser Informationen in O(1) bestimmen kann, ob ein Knoten im Teilbaum eines anderen Knoten enthalten ist oder nicht. (3 Punkte) (c) Geben Sie weiterhin ein Verfahren an, dass mit O(n) Prozessoren in O(log n) Zeit den maximalen Wert in jedem Teilbaum berechnet. (6 Punkte) Aufgabe 2: Minimale Spannbäume (10 Punkte) Wir betrachten den Graphen von Blatt 3, Aufgabe 1 und versehen die Kanten wie folgt mit Kosten: w(1, 4) = 1 w(1, 5) = 2 w(2, 3) = 1 w(2, 7) = 3 w(3, 6) = 4 w(3, 7) = 9 w(4, 6) = 9 w(5, 6) = 10 w(6, 8) = 5 w(6, 9) = 5 w(8, 9) = 6 Berechnen Sie einen Spannbaum mit minimalen Kosten in dem resultierenden Graphen. Aufgabe 3: 2-Zusammenhangskomponenten (15 Punkte) Sei G ein Graph. Wir betrachten den Algorithmus zum Berechnen von 2-ZHKs aus der Vorlesung. Sei G0 der Graph mit V (G0 ) = E(G), der durch die drei in der Vorlesung aufgelisteten Regeln gebildet wird. Beweisen Sie die folgende Aussage: Sei T ein aufspannender Baum von G. Dann gilt: Zwei Kanten, die auf demselben Fundamentalkreis von G bzgl. T liegen, befinden sich in G0 in derselben Zusammenhangskomponente. 1
© Copyright 2024 ExpyDoc