Beweis ganzzahlige Division über dyadische Darstellung

01.07.2021, 16:34	Enomine	Auf diesen Beitrag antworten »
Beweis ganzzahlige Division über dyadische Darstellung Hallo, gezeigt werden solll, dass sich die ganzzahlige Division auch über die dyadische Darstellung ausrechnen lässt und dies soll über die dyadische Darstellung bewiesen werden. zunächst die Definition, für Leute, die sich erst noch reinlesen: [attach]53254[/attach] [attach]53258[/attach] Die "Eckigen Klammern, wo oben der Strich fehlt" bedeuten "ganzzahlige Division", dh. nach unten ganzzahlig abgerundet. Für den Beweis sehe ich zwei Wege: Direkter Beweis durch Implikationskette oder Vollständige Induktion. Für eine Implikationskette fehlt mir eine anständige mathematische Definition von "ganzzahlige Division", die ich ja dann durch ergänzen und umwandeln so umschreiben müsste, dass sich nachher eine dyadische Darstellung abließt. Die vollständige Induktion habe ich hier mal in Ansätzen probiert: [attach]53255[/attach] [attach]53256[/attach] Für x=0 habe ich einen Gegenbeweis geliefert. Deswegen denke ich, dass die Aufgabenstellung (Altklausur) unvollständig ist und ein "nur für x >0" fehlt. Frage 1: Sehe ich das richtig? Frage 2: Wie ist die Aufgabenstellung zu beweisen? Dankeschön Enomine
01.07.2021, 21:26	HAL 9000	Auf diesen Beitrag antworten »
Du hast vergessen zu erwähnen, dass im Vorfeld der Aufgabe wohl von $\begin{eqnarray} \operatorname{dya}\left(x\right) = a_m\ldots a_0 \end{eqnarray}$ (bzw. äquvivalent $\begin{eqnarray} x = \operatorname{dya}^{-1}\left(a_m\ldots a_0\right) \end{eqnarray}$ ) ausgegangen werden soll... Im Prinzip unterscheidet man die beiden Fälle " $\begin{eqnarray} x \end{eqnarray}$ ungerade" (bedeutet $\begin{eqnarray} a_0=1 \end{eqnarray}$ ) und " $\begin{eqnarray} x \end{eqnarray}$ gerade" (bedeutet $\begin{eqnarray} a_0=2 \end{eqnarray}$ ), in beiden Fällen folgt die Behauptung aus 2. P.S.: Für $\begin{eqnarray} x=0 \end{eqnarray}$ ist die dyadische Darstellung $\begin{eqnarray} a_m\ldots a_0 \end{eqnarray}$ bereits "leer", es gibt da also gar kein $\begin{eqnarray} a_0 \end{eqnarray}$ , damit macht die Aussage schon allein deshalb da gar keinen Sinn.
01.07.2021, 21:33	Leopold	Auf diesen Beitrag antworten »
RE: Beweis ganzzahlige Division über dyadische Darstellung Auf der rechten Seite der zu beweisenden Formel wird die Existenz eines $\begin{align} a_0 \end{align}$ vorausgesetzt. Bei $\begin{align} x=0 \end{align}$ ist $\begin{align} \operatorname{dya}(0) = \varepsilon \end{align}$ , so daß es ein solches $\begin{align} a_0 \end{align}$ nicht gibt. Die Formel wird für $\begin{align} x=0 \end{align}$ sinnlos. In der Aufgabe sollte es daher tatsächlich heißen: "Zeigen Sie für $\begin{align} x>0 \end{align}$ , dass ..." Ansonsten könnte man direkt mit der Definition arbeiten. Sei also $\begin{align} x>0 \end{align}$ mit $\begin{align} \operatorname{dya}(x) = a_m a_{m-1} \ldots a_0 \end{align}$ gegeben. Es gilt daher $\begin{align} x = a_0 + \sum_{i=1}^m a_i 2^i \end{align}$ Für $\begin{align} x=1 \end{align}$ oder $\begin{align} x=2 \end{align}$ erstreckt sich die Summation über die leere Indexmenge, die Summe ist als 0 zu interpretieren. Division durch 2 ergibt $\begin{align} \frac{x}{2} = \frac{a_0}{2} + \sum_{i=1}^m a_i 2^{i-1} = \frac{a_0}{2} + \underbrace{\sum_{i=0}^{m-1} a_{i+1} 2^i}_y \end{align}$ Jetzt wird nach unten abgerundet. Ist $\begin{align} a_0 = 1 \end{align}$ , verschwindet der erste Summand, ist $\begin{align} a_0 = 2 \end{align}$ , wird er zu 1. Dasselbe erreicht man mit dem Term $\begin{align} a_0 - 1 \end{align}$ . Der Summand $\begin{align} y \end{align}$ ist ganz und bleibt unverändert: $\begin{align} \left \lfloor \frac{x}{2} \right \rfloor = a_0 - 1 + y \end{align}$ Nun ist aber gerade $\begin{align} \operatorname{dya}(y) = a_m a_{m-1} \ldots a_1 \end{align}$ , also $\begin{align} \operatorname{dya}^{-1} \left( a_m a_{m-1} \ldots a_1 \right) = y \end{align}$ . Es folgt: $\begin{align} \left \lfloor \frac{x}{2} \right \rfloor = a_0 - 1 + \operatorname{dya}^{-1} \left( a_m a_{m-1} \ldots a_1 \right) \end{align}$
04.07.2021, 14:39	Enomine	Auf diesen Beitrag antworten »
Hallo, ich danke für eure Hilfe. Kann ich es wie folgt aufschreiben? Seht ihr noch Fehler? EDIT: Wenn man auf das erste Bild drauf klickt dann erscheint es waagerecht. Warum die Vorschau senkrecht ist, weiß ich nicht. [attach]53269[/attach] [attach]53270[/attach] Danke Enomine

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »