Prof. Dr. R. Laue WS9900 Informatik I
Übungsblatt 9
Abgabe: 25.1.00 vor der Vorlesung

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

a) Geben Sie ein 8-stelliges Dualzahlenpaar an, welches bei der Addition mit dem v. Neumann Addierer maximale Schrittzahl benötigt. Zeichnen Sie die Registerbelegung in den einzelnen Schritten. Zeichnen Sie das gesamte Schaltwerk.

b) Wie groß ist die Wahrscheinlichkeit dass der v. N. Addierer nach einem Schritt fertig ist? Beweis

c) Wie groß ist die Wahrscheinlichkeit dass der v. N. Addierer maximale Schrittzahl braucht? Beweis

Aufgabe 25 - Karacuba (3+6 Punkte)

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 (3 Punkte)

b) Beweisen Sie: Der Zeitaufwand der nötig ist um 2 Zahlen der Länge k mittels Karacuba zu multiplizieren ist: O(k^log₂3) (6 Punkte)