BuK/IIm14/Studenten/s3tomack

Wiki-Quelltext dieser Seite.

== Ü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 }$
{| border="1" cellpadding="5" cellspacing="0"
|-
|| $\N$ || 0 || 1 || 2 || 3 || 4 || 5 || 6 || ...
|-
|| $\Z$ || 0 || -1 || 1 || -2 || 2 || -3 || 3 || ...
|-
|}
$$f(n) = \begin{cases}
\frac{n}{2}, & \text{wenn } n \text{ gerade}\\
-\left(\frac{n+1}{2}\right), & \text{wenn } n \text{ ungerade}\\
\end{cases}$$

'''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$
{| border="1" cellpadding="5" cellspacing="0"
|-
|| $p / q$ || -1 || 1 || -2 || 2 || -3 || 3 || -4 || 4 || -5 || 5 || $\ldots$
|-
|| 1 || $\frac{-1}{1}$ || $\frac{1}{1}$ || $\frac{-2}{1}$ || $\frac{2}{1}$ || $\frac{-3}{1}$ || $\frac{3}{1}$ || $\frac{-4}{1}$ || $\frac{4}{1}$ || $\frac{-5}{1}$ || $\frac{5}{1}$ || $\ldots$
|-
|| 2 || $\frac{-1}{2}$ || $\frac{1}{2}$ || $\frac{-2}{2}$ || $\frac{2}{2}$ || $\frac{-3}{2}$ || $\frac{3}{2}$ || $\frac{-4}{2}$ || $\frac{4}{2}$ || $\frac{-5}{2}$ || $\frac{5}{2}$ || $\ldots$
|-
|| 3 || $\frac{-1}{3}$ || $\frac{1}{3}$ || $\frac{-2}{3}$ || $\frac{2}{3}$ || $\frac{-3}{3}$ || $\frac{3}{3}$ || $\frac{-4}{3}$ || $\frac{4}{3}$ || $\frac{-5}{3}$ || $\frac{5}{3}$ || $\ldots$
|-
|| 4 || $\frac{-1}{4}$ || $\frac{1}{4}$ || $\frac{-2}{4}$ || $\frac{2}{4}$ || $\frac{-3}{4}$ || $\frac{3}{4}$ || $\frac{-4}{4}$ || $\frac{4}{4}$ || $\frac{-5}{4}$ || $\frac{5}{4}$ || $\ldots$
|-
|| 5 || $\frac{-1}{5}$ || $\frac{1}{5}$ || $\frac{-2}{5}$ || $\frac{2}{5}$ || $\frac{-3}{5}$ || $\frac{3}{5}$ || $\frac{-4}{5}$ || $\frac{4}{5}$ || $\frac{-5}{5}$ || $\frac{5}{5}$ || $\ldots$
|-
|| $\vdots$ || $\vdots$ || $\vdots$ || $\vdots$ || $\vdots$ || $\vdots$ || $\vdots$ || $\vdots$ || $\vdots$ || $\vdots$ || $\vdots$ || $\ddots$
|-
|}

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$.
$$f(n)=2n$$

=== 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)$.
<blockquote>
$z=\frac{(x+y)(x+y+1)}{2}+y=t+y$<br/>
$w=x+y$<br/>
$t,x,y,z,w \in \N$<br/><br/>
$t=z-y=\frac{w(w+1)}{2}=\frac{w^2+w}{2}$<br/>
Lösung von $w^2+w-2t=0$:<br/>
allgemeine Form: $w^2+pw-q=0$<br/>
pq-Formel: $w_{1,2}=-\frac{p}{2}\pm\sqrt{\left(\frac{p}{2}\right)^2-q}$<br/>
$w_{1,2}=-\frac{1}{2}\pm\sqrt{\left(\frac{1}{2}\right)^2+2t}$<br/>
$w_{1,2}=-\frac{1}{2}\pm\sqrt{\frac{1}{4}+\frac{8t}{4}}$<br/>
$w_{1,2}=-\frac{1}{2}\pm\sqrt{\frac{8t+1}{4}}$<br/>
$w_{1,2}=-\frac{1}{2}\pm\frac{\sqrt{8t+1}}{2}$<br/>
Für positive $w$ ergibt sich $w_1$:<br/>
$w_1=-\frac{1}{2}+\frac{\sqrt{8t+1}}{2}$<br/>
$w_1=\frac{\sqrt{8t+1}-1}{2}$<br/><br/>
Außerdem gilt:<br/>
$t \leq z, \text{ da } z = t + y$<br/>
$z = t + w - x, \text{ da } z = t + y \text{ und } y = w - x$<br/>
$z \leq t + w < t + w + 1$<br/>
$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}$<br/>
$z < \frac{(w+1)^2+(w+1)}{2}$<br/><br/>
Unter Verwendung von $z < \frac{(w+1)^2+(w+1)}{2}$ können wir $w$ nach oben
abschätzen:<br/>
$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:<br/>
$\frac{\sqrt{8\left(\frac{(w+1)^2+(w+1)}{2}\right) + 1} - 1}{2}$<br/>
$\frac{\sqrt{8\left(\frac{w^2+3w+2}{2}\right) + 1} - 1}{2}$<br/>
$\frac{\sqrt{\left(\frac{8w^2+24w+16}{2}\right) + 1} - 1}{2}$<br/>
$\frac{\sqrt{4w^2+12w+9} - 1}{2}$<br/>
$\frac{\sqrt{(2w+3)^2} - 1}{2}$<br/>
$\frac{2w+2}{2}=w+1$<br/>
Daher ergibt sich $w=\lfloor \frac{\sqrt{8z + 1} - 1}{2} \rfloor \in \N$<br/><br/>
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.<br/>
Danach ergeben sich:<br/>
$t = \frac{w (w + 1)}{2}$<br/>
$y = z - t$<br/>
$x = w - y$<br/>
</blockquote>

----

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$<br/>
$t = \frac{w (w + 1)}{2} = \frac{4 (4 + 1)}{2} = \frac{20}{2} = 10$<br/>
$y = z - t = 13 - 10 = \underline{3}$<br/>
$x = w - y = 4 - 3 = \underline{1}$<br/>

== Kreativaufgaben ==