BuK/IIm11/BuK-Übung04

Wiki-Quelltext dieser Seite.

== Aufgabe 1 ==
Behauptung: Eine Menge M ist genau dann aufzählbar, wenn sie semi-entscheidbar ist.

=== Teilaufgabe 1 <tt>(Felix Nitsche, Stefan Lüttke, Jens Heider, Daniel Tasche)</tt> ===
zu zeigen: Wenn M aufzählbar, dann M semi-entscheidbar.

=== Teilaufgabe 2 <tt>(Max Wielsch, Raik Bieniek, Ingo Körner, Christof Ochmann)</tt> ===
zu zeigen: Wenn M semi-entscheidbar ist, dann ist M aufzählbar.

== Aufgabe 2 <tt>(Tobias Salzmann, Ronald Krause, Robert Rosenberger, Stefan Scheumann)</tt> ==
ÜA: Vervollständigen Sie die Herleitung der Funktionen für x und y aus $z = π(x, y)$ und geben Sie als Beispiel die Ermittlung von x und y aus $z = π(1, 3) = 13$ an.

Herleitung der Funktionen für $x$ und $y$ aus $z = (x; y)$

$z =\frac{(x+y)(x+y+1)}{2} +y = t + y;$ <br />
$w = x + y;$ <br />
$x,y,z \in \N, w,t \in \R_{0}^{+}$


$t = z - y = \frac{w(w+1)}{2} = \frac{w^{2}+w}{2} $

Die Lösung von $w^{2} + w + 2t = 0$ <br />
$w=-\frac{p}{2}+\sqrt{\left(\frac{p}{2}\right)^2-q}$ <br />
$w=-\frac{1}{2}+\sqrt{\left(\frac{1}{2}\right)^2+2t}$ <br />
$w=-\frac{1}{2}+\sqrt{\left(\frac{1}{4}\right)^2+\frac{8t}{4}}$ <br />
$w=-\frac{1}{2}+\sqrt{\frac{1+8t}{4}}$ <br />
$w=-\frac{1}{2}+\frac{\sqrt{1+8t}}{2}$ <br />
für positives $w$ ist $w = \frac{\sqrt{8t+1}-1}{2}$

<br />Außerdem gilt:<br />
$t \leq z $, weil $z=t+y$<br />
$z= t + w - x$<br />
$z \leq t + w \leq t + w + 1 = \frac{w^{2}+w}{2} + w + 1 = \frac{(w+1)^{2} + (w+1)}{2}$

<br />Unter verwendung von $z \leq  \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} \leq w+1 $

<br />Für $z$ wird $\frac{(w+1)^{2} + (w+1)}{2}$ eingesetzt:

$\frac{\sqrt{8\frac{(w+1)^{2} + (w+1)}{2}+1}-1}{2}$

$\frac{\sqrt{8\frac{w^2+3w+2}{2}+1}-1}{2}$

$\frac{\sqrt{\frac{8w^2+24w+16}{2}+1}-1}{2}$

$\frac{\sqrt{4w^2+12w+9}-1}{2}$ = $\frac{\sqrt{(2w+3)^2}-1}{2}$ = $\frac{2w+2}{2}$ = $\frac{2(w+1)}{2}$ = $w+1$

<br />Um die beiden natürlichen Zahlen x und y aus z zu gewinnen, ist
als erstes $w = \left\lfloor \frac{\sqrt{8z+1}-1}{2} \right\rfloor $ zu berechnen. Dann ergeben sich

$t = \frac{w(w+1)}{2}$ und
$y = z -t$ sowie 
$x = w - y$

'''Beispiel: Ermittelung von $x$ und $y$ aus $z=\pi(1,3) = 13$'''

$w = \left\lfloor \frac{\sqrt{8z+1}-1}{2} \right\rfloor = \left\lfloor \frac{\sqrt{8*13+1}-1}{2} \right\rfloor = 4,623 = 4  $ 

$y=13-\frac{w(w+1)}{2}$ = $13-\frac{(x+y)(x+y+1)}{2} $ = $13-\frac{(1+3)(1+3+1)}{2} $ $= 13 -10 = 3$

$3=3$

$x=w-y = x + y - y = 1 + 3 - 3 = 1$

$1=1$