Prof. Dr. R. Laue                                                                            WS0304
                                Informatik I
                                Übungsblatt 10
                                Abgabe: 22.1.04 vor der Vorlesung

URL:         /axel/informatik1_ws0304_blatt10.html
Dieses  Übungsblatt ist in Zweiergruppen zu bearbeiten. Auf dem Blatt  bitte Übungsgruppentag angeben. Um den Übungsschein zu erhalten, muß man 50% der Punkte erreichen und aktiv am Übungsbetrieb teilnehmen. D.h Vorrechnen, Bearbeitung von mindestens 80% der  Übungsblätter.

Jede Aufgabe auf einem eigenen Blatt (mit Namen und Gruppe und Matrikelnummern). Nicht mit Bleistift bearbeiten.



Aufgabe 28 -  Wabenmultiplizierer  (3+2+2+3 Punkte)

In der Vorlesung wurde ein Verfahren zur parallelen Multiplikation mit Ergebnistransport von Matrizen vorgestellt. Dazu werden die Bausteine wabenförmig angeordnet. Zeichnen Sie das schematische Netz zur Multiplikation von zwei 3x3 Matrizen (aij) und (bij). Es ist zu beachten, dass das Netz leicht auf größere Beispiel zu erweitern ist und daß die Eingaben (Matrizen A und B)  nur einmal zur Verfügung stehen.  (3 Punkte)
Erläutern Sie die Funktionsweise und zeigen Sie wieviele Schritte bei einer Multiplikation von zwei nxn Matrizen nötig sind. (2 Punkte)
Wieviele Wabenbausteine sind bei einer Multiplikation von nxn Matrizen nötig? (2 Punkte)
Nehmen Sie als ein Beispiel eine 3x3 Matrix, die als Einträge die Ziffern Ihrer Matrikelnummer in zufälliger Reihenfolge und sonst Nullen hat und quadrieren diese mit obigen Netz. Nehmen Sie für jeden Schritt eine Fotokopie Ihres Netzes und tragen  Sie die Belegungen der Bausteine ein. (3 Punkte)

Aufgabe 29 -  Cayley Graph - (4 Punkte)

Als Beispiel eines Netzwerks wurde der Cayley Graph der symmetrischen Gruppe auf den 3 Punkten (1,2,3) betrachtet. Die beiden Erzeuger waren in Zykelschreibweise a=(1,2)   und b=(2,3), damit erhielt man folgendes Netzwerk
bild
Erzeuge das Netzwerk für die symmetrische Gruppe mit 4 Punkten und dem zusätzlichen Erzeuger c=(3,4). Es gibt 2 Sonderpunkte wenn man eine schöne Platzierung des Netzwerks im 3-dimensionalen Raum findet.


Aufgabe 30 -Bitoner Sortierer (4+4 Punkte)

a) Zeichnen Sie das Schaltnetz für den bitonen Sortierer mit 16 Eingängen.  (4 Punkte)
b) Sortieren Sie damit das Wort

BIENENWABENNETZE

in absteigender Reihenfolge. Nehmen Sie dazu eine Fotokopie Ihres Schaltnetzes und tragen Sie die Belegung in den einzelnen Schichten ein. (4 Punkte)