Übungsblatt 6 - Aufgabe 1 + Aufgabe 2

Hallo,
ich habe zwei Fragen:

Zu Aufgabe 1:
Ist mit s_n das n-te Summenbit gemeint, also das Ergebnis nach der Addition

Zu Aufgabe 2:
Wie ist die Funktion g(n) definiert?

Vielen Dank

Hallo,

Aufgabe 2 hat sich erledigt.

Die Frage zu Aufgabe 1 bleibt. Also insbesondere meine ich ob s_n = NXOR(a_n, b_n) ist oder ob das c_{n-1} noch mitspielt.

Vielen Dank.

Hallo,

ich weis nicht ob ich die Frage vollständig verstanden habe,
allerdings würde ich sagen, c_{n-1} "spielt noch mit".

Wenn man mit 0 zu zählen beginnt, dann ist s_n das n-te Bit der Summe.

Vgl. Kapitel 3.4 Arithmetische Schaltungen
Folie 19 - Aufbau eines Carry-Ripple Addierers.

Grüße

Für mich hat sich Aufgabe 2 nicht erledigt, weil wieder mal nichts (außer f) definiert ist.
So wie die Aufgabe dort steht kann man sie nicht eindeutig lösen.
Ich kann z.B. annehmen, dass g(n) := 0 oder := i (komplex) ist oder a := 0, was das ganze ad absurdum führt.

Also was soll das sein?

BITTE in Zukunft vollständige Definitionen angeben, denn falsch kann eine Lösung die Annahmen wie oben macht nicht sein, da ohne Vorgaben jede Lösung Annahmen über den Definitionsbereich der Variablen / Funktionen machen muss.

Hi RL,

wenn g(n):=0 passt das trotzdem. Aber das a \in R und a != 0 und g: R -> R hätte man schon noch dazu schreiben können, finde ich auch.

Liebe Grüße

Kann a tatsächlich in R sein? Da f : N => N und f(n) = a f(n/b) + g(n) muss meiner Meinung nach sogar a \in N sein, außer g(n) ist antiproportional zu a. Das schränkt das ganze schon deutlich ein!

Ich habe mir mal noch etwas mehr Gedanken darüber gemacht:

Für k=0 müsste gelten n=b^0=1. Jetzt wird das ganze schwierig, da f(n/b) immer noch von N => N abbilden soll. Somit müsste auch 1/b \in N => b = 1.

Mit log1(1) = 0:
=> f(1) = c + sum_0^{-1} a^i g(1 / 1^i) = c

Mit log1(1) = 1, schließlich ist auch 1^1=1:
=> f(1) = a c + sum_0^0 a^i g(1 / 1^i) = a c + g(1)
Nach f(1) = c müsste dann c = g(1) / (1-a) und das allgemein, da die Gleichung ja für alle n = b^k gelten soll!

Jetzt habe ich schon so viele Einschränkungen, dass der Beweis praktisch kaum noch Sinn macht, da die Gleichung sowieso nur unter diesen speziellen Vorrausstzungen gültig ist.

Wenn ich hier einen Fehler gemacht habe, möge man mich bitte korrigieren (was für mein mathematisches Verändnis sehr hilfreich und wichtig wäre ;)

Genau deshalb finde ich einen Definitionsbereich zwingend notwendig, vor allem in der Klausur!



1 mal bearbeitet. Zuletzt am 05.12.2014 00:11 von RL.

Hi RL,

ja k \in N und b > 1 sollte auch noch da stehen. Falls b=1 => n = 1 und log1(n) ist nicht definiert.

Aber für a \in R habe ich kein Gegenbeispiel. Ich denke die Aufgabe wurde so gestellt, damit man bei dem Abschätzen Kosten ein paar Aufgaben später sieht, dass wir das Ergebnis verwerten können..

Lg