Transcript
Universit¨ at zu K¨ oln Institut f¨ ur Informatik Dr. O. Schaudt A. van der Grinten
¨ Ubung zu Parallele Algorithmen Blatt Nr. 5 ¨ Dieses Ubungsblatt muss bis zum 25.05.2016, 15:30 abgegeben werden. Schreiben Sie Ihren Namen ¨ und Ihre Ubungsgruppe 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¨ aumen 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¨ aume (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
