s3tomack

Übungsaufgaben

Dieses Kapitel enthält die Übungsaufgaben geordnet nach den Vorlesungen.

Vorlesung 1: Vorbereitungen

Vorlesung 2: Berechenbarkeitsbegriff

abzählbar unendliche Mengen

Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: \Z, \Q, die Menge der Primzahlen, die geraden Zahlen.

Für \Z:

z.z.: Die Menge \Z ist abzählbar unendlich.

• abzählbar, d.h. \exists f : \N \rightarrow \Z | \text{ bijektiv }

Für \Q:

z.z.: Die Menge \Q ist abzählbar unendlich.

• abzählbar, d.h. \exists f : \N \rightarrow \Q | \text{ bijektiv }
• Elemente von \Q sind darstellbar durch: \frac{p}{q} | q \neq 0 \text{ und } p, q \in \Z

Unter Zuhilfenahme des Cantorschen Diagonalisierungsverfahren 1. Art lassen sich alle Elemente erreichen.

Für die Menge der Primzahlen P:

z.z.: Die Menge P ist abzählbar unendlich.

• abzählbar, d.h. \exists f : \N \rightarrow P | \text{ bijektiv }
• Die Menge der Primzahlen P ist nach dem Satz von Euklid unendlich.
• Die Menge der Primzahlen P ist abzählbar, da gilt P \subset \N (nach Definition der Primzahlen).

Für die Menge der geraden Zahlen G:

z.z.: Die Menge P ist abzählbar unendlich.

• abzählbar, d.h. \exists f : \N \rightarrow G | \text{ bijektiv }
• Die Menge der geraden Zahlen G ist abzählbar, da gilt G \subset \Z.

Vorlesung 3: Entscheidbarkeit und Aufzählbarkeit

Vorlesung 4: Sätze und Zusammenhänge

Vervollständigen Sie die Herleitung der Funktionen für x und y aus z = \pi(x, y).

z=\frac{(x+y)(x+y+1)}{2}+y=t+y
w=x+y
t,x,y,z,w \in \N

t=z-y=\frac{w(w+1)}{2}=\frac{w^2+w}{2}
Lösung von w^2+w-2t=0:
allgemeine Form: w^2+pw-q=0
pq-Formel: w_{1,2}=-\frac{p}{2}\pm\sqrt{\left(\frac{p}{2}\right)^2-q}
w_{1,2}=-\frac{1}{2}\pm\sqrt{\left(\frac{1}{2}\right)^2+2t}
w_{1,2}=-\frac{1}{2}\pm\sqrt{\frac{1}{4}+\frac{8t}{4}}
w_{1,2}=-\frac{1}{2}\pm\sqrt{\frac{8t+1}{4}}
w_{1,2}=-\frac{1}{2}\pm\frac{\sqrt{8t+1}}{2}
Für positive w ergibt sich w_1:
w_1=-\frac{1}{2}+\frac{\sqrt{8t+1}}{2}
w_1=\frac{\sqrt{8t+1}-1}{2}

Außerdem gilt:
t \leq z, \text{ da } z = t + y
z = t + w - x, \text{ da } z = t + y \text{ und } y = w - x
z \leq t + w < t + w + 1
t + w + 1 = \frac{w^2 + w}{2} + w +1 = \frac{w^2+w+2x+2}{2} = \frac{(w^2+2x+1)+(w+1)}{2} = \frac{(w+1)^2+(w+1)}{2}
z < \frac{(w+1)^2+(w+1)}{2}

Unter Verwendung von z < \frac{(w+1)^2+(w+1)}{2} können wir w nach oben abschätzen:

w = \frac{\sqrt{8t + 1} - 1}{2} \leq \frac{\sqrt{8z + 1} - 1}{2} < w + 1

Für z wird \frac{(w+1)^2+(w+1)}{2} eingesetz:
\frac{\sqrt{8\left(\frac{(w+1)^2+(w+1)}{2}\right) + 1} - 1}{2}
\frac{\sqrt{8\left(\frac{w^2+3w+2}{2}\right) + 1} - 1}{2}
\frac{\sqrt{\left(\frac{8w^2+24w+16}{2}\right) + 1} - 1}{2}
\frac{\sqrt{4w^2+12w+9} - 1}{2}
\frac{\sqrt{(2w+3)^2} - 1}{2}
\frac{2w+2}{2}=w+1
Daher ergibt sich w=\lfloor \frac{\sqrt{8z + 1} - 1}{2} \rfloor \in \N

Um die beiden natürlichen Zahlen x und y aus z zu gewinnen, ist als erstes w=\lfloor \frac{\sqrt{8z + 1} - 1}{2} \rfloor zu berechnen.
Danach ergeben sich:
t = \frac{w (w + 1)}{2}
y = z - t
x = w - y

Geben Sie als Beispiel die Ermittlung von x und y aus z = \pi(1, 3) = 13 an:

w = \lfloor \frac{\sqrt{8z + 1} - 1}{2} \rfloor = \lfloor \frac{\sqrt{8 * 13 + 1} - 1}{2} \rfloor = \lfloor 4,6235 \rfloor = 4
t = \frac{w (w + 1)}{2} = \frac{4 (4 + 1)}{2} = \frac{20}{2} = 10
y = z - t = 13 - 10 = \underline{3}
x = w - y = 4 - 3 = \underline{1}

Kreativaufgaben