URL:        /axel/informatik1_ws0001_blatt11.html
Dieses Übungsblatt ist in Zweiergruppen zu bearbeiten. Auf dem Blatt bitte den Übungsgruppentag angeben. Um den Übungsschein zu erhalten, muß man 50% der Punkte erreichen und zweimal erfolgreich eine Aufgabe vorrechnen.

Aufgabe 33 -  Benes   (3+3+4 Punkte)

a) Man berechne für das Benes Permutationsnetz mit 2n Eingängen die Anzahl der möglichen Kombinationen von Schalterstellungen.
b) Zeigen Sie, daß diese Anzahl für Netze mit mehr als zwei Eingängen größer ist als die Anzahl der möglichen Permutationen der Eingabedaten.
c) Wieviele Schritte sind beim Benes Netz mit m = 2n Prozessoren höchstens nötig, um eine Information vom Prozessor i zu einem Prozessor j zu senden. Die vorherige Berechnung der Schalterstellung bleibt dabei unberücksichtigt.

Aufgabe 34 - Benes (3+3 Punkte)

a) Sei ein 8 Prozessor Netzwerk gegeben. Die Prozessoren seien über ein Benes Netz verbunden. Die Daten aus Prozessor 1 sollen zum Prozessor 6 (1->6) die weiteren Zuordungen seien (2->4, 3->8, 4->2, 5->1, 6->7, 7->5, 8->3). Man zeichne das Benes Permutationsnetz und berechne eine Schalterstellung zur Realisierung dieser Permutation.
b) Man gebe eine 8 stellige Permutation und zwei verschiedene Schalterstellungen an, die diese Permutation realisieren.
 

Aufgabe 35 - Würfel (4 Punkte)

Realisieren Sie die Permutation aus 34a auf einem dreidimensionalen Würfel:

Dabei kann in einem Schritt entlang einer Kante in jede Richtung nur eine Information weitergegeben werden. In einem Knoten kann nur ein Datensatz gespeichert werden.  Versuchen Sie mit möglichst wenigen Schritten auszukommen.