Prof. Dr. R. Laue WS0001 Informatik I
Übungsblatt 9
Abgabe: 21.12.00 vor der Vorlesung

URL: /axel/informatik1_ws0001_blatt9.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 27 - von Neumann Addierer - (2+3+3 Punkte)

a) Geben Sie ein n-stelliges Zahlenpaar an, bei dem der von Neumann Addierer maximale Schrittzahl benötigt. Beweis!
b) Wie groß ist die Wahrscheinlichkeit, dass der von Neumann Addierer bei n-stelligen Zahlen nach einem Schritt fertig ist. Beweis!
c) Wie groß ist die Wahrscheinlichkeit, dass der von Neumann Addierer bei n-stelligen Zahlen die maximale Schrittzahl benötigt. Beweis!

Aufgabe 28 - Karacuba - (3Punkte)

a) Multiplizieren Sie Ihre 6stellige Matrikelnummer (z.B. 123456) mit Ihrer Matrikelnummer rückwärts gelesen (z.B. 654321) mittels der Methode vom Karacuba. Verwenden Sie die Basis 1000

Aufgabe 29 - Division - (4 Punkte)

Man entwerfe ein Schaltnetz, das die Division natürlicher Zahlen mit Rest nach der Schullmethode realisiert. Verwenden Sie ein Schieberegister, das auf den vorderen Speicherplätzen den Divisionsrest und auf den hinteren den Quotienten aufnahemen soll. Man benutze ausserdem einen vorhandenen mehrstelligen Vergleicher und Subtrahierer.