BuK/IIm10/BuK-Übung02 G2

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
<language>Java</language>
= Halteproblem =
== Aufgabe ==
Spielen Sie die Betrachtungen zum Halteproblem mit Scheme-Prozeduren
nach.
Hinweis: Definieren Sie ggf. auch eine Prozedur haelt-tricky?, die #t zurück gibt,
wenn das betrachtete Programm P ein Ergebnis berechnet, und #f, wenn die Berech-
nung in einer gewissen Zeit T zu keinem Ergebnis führt. Verwenden Sie zeitbeschränkte
Berechnungen, deren Implementierungsidee einige Kreativität erfordert.

== Lösung für Racket==
<code id="4d8b0c366b24c">
(define (haelt-fuer-n? f n)
    (if (integer? (f n))
        #t
        #f))

(define (haelt? f)
    (haelt-fuer-n? f 0))

(define (crazy n)
    (if (haelt? crazy n)
        (crazy n)
        n))

(define (haelt-tricky? f timeout)
    (letrec 
        ([ft (thread f)]
         [helper
          (lambda (timeLeft)
            (if (thread-running? ft)
                (if (= timeLeft 0)
                    #f
                    (begin (sleep 1) (helper (- timeLeft 1))))
                #t))])
      (helper timeout)))

(define test1
  (lambda ()
    (print "hallo")))

(define test2
  (lambda ()
    (test2)))
</code>

Aufrufbeispiele:
<code>
(haelt-tricky? test1 10)
</code>
<code>
(haelt-tricky? test2 10)
</code>

Eine ähnliche Implementation in Java kann [[hier]] gefunden werden.

= Beweise =

== Aufgabe 1 ==
Zeigen Sie, dass die Menge der rationalen Zahlen abzählbar unendlich ist.

== Lösung ==
Eine Menge ist dann abzählbar unendlich wenn sie gleichmächtig zur Menge der natürlichen Zahlen <math>\mathbb{N}</math> ist. Mit [http://de.wikipedia.org/wiki/Cantors_erstes_Diagonalargument Cantors erstes Diagonalargument] lässt sich zeigen, dass die unendliche Menge der rationalen Zahlen <math>\mathbb{Q}</math> gleichmächtig mit der Menge der natürlichen Zahlen <math>\mathbb{N}</math> ist.

== Aufgabe 2 ==
Zeigen Sie, dass die Wortmenge <math>A^{\ast}</math> über <math>A</math> abzählbar unendlich ist.

== Lösung ==

Gegeben sei ein Alphabet <math>A</math> mit den Elementen <math>\{a_1,a_2,a_3\ldots,a_n\}</math>.

== Aufgabe 3 ==
Zeigen Sie, dass die Menge der reellen Zahlen überabzählbar unendlich ist.

== Lösung ==

Durch Widerspruch kann gezeigt werden, dass die Menge der reellen Zahlen <math>\mathbb{R}</math> überabzählbar unendlich ist. Für den Beweis wird das offene Intervall (0,1)  betrachtet was eine echte Teilmenge der reellen Zahlen darstellt.<br>
'''Annahme:''' Die Menge der reellen Zahlen im offenen Intervall (0,1) ist abzählbar.<br>
Es muss eine bijektive Abbildung der reellen Zahlen auf die natürlichen Zahlen existieren. Sei nun <math>l_{i}</math> eine beliebige Folge von reellen Zahlen im offenen Intervall (0,1). Die Folge lässt sich dezimal wie folgt darstellen:<br>
<math>
\begin{array}{ccc}
l_1 & = & 0,a_{1;1}a_{1;2}a_{1;3}\ldots\\
l_2 & = & 0,a_{2;1}a_{2;2}a_{2;3}\ldots\\
l_3 & = & 0,a_{3;1}a_{3;2}a_{3;3}\ldots\\
&\vdots
\end{array}
</math>
<br>
wobei <math>l_{i}</math> reelle Zahlen sind und <math>a_{i;j}</math> die Dezimalstellen dieser Zahlen. Nun lässt sich eine Zahl <math>z</math> konstruieren die nicht in der Folge <math>l_{i}</math> zu finden ist.<br>
<math>z = 0,f_1f_2f_3\cdots</math><br>
wobei 
<math>
f_i=\begin{cases}
0, &\text{wenn } a_{i;i} = 9;\\
a_{i;i} + 1 &\text{wenn } a_{i;i} < 9;\\
\end{cases}
</math><br>
Diese Diagonalzahl <math>z</math> unterscheidet sich von allen anderen Zahlen der Folge <math>l_{i}</math> und ist ebenfalls im Intervall (0,1). Es kann also für jede beliebige Folge <math>l_{i}</math> eine Zahl gefunden werden die nicht in der Folge enthalten ist.<br>
Es existiert keine surjektive Abbildung der natürlichen Zahlen auf das offene Intervall (0,1). D.h. es kann auch keine bijektive Abbildung existieren. Die Menge der reellen Zahlen im Intervall (0,1) ist also nicht abzählbar. Sie ist überabzählbar unendlich. Da das Intervall eine echte Teilmenge der reellen Zahlen <math>\mathbb{R}</math> ist, gilt das auch für die Menge der reellen Zahlen.

= Kreativität =

Schauen Sie sich das [http://www.youtube.com/watch?v=oyo_oGUEH-I Video] an, um den Begriff der Kreativität besser zu verstehen.

= Bijektive Funktion =
== Aufgabe ==
Verifizieren Sie, dass die folgende Funktion <math>f : \mathbb{N}^{+} \rightarrow \mathbb{Q}^{+}</math> eine bijektive Funktion ist und
implementieren Sie eine Prozedur, die die zugehörige Umkehrfunktion <math>f^{-1}</math> berechnet.<br>
<math>
f(n)=\begin{cases}
1, &\text{wenn }n = 1;\\
f(\frac{n}{2}) + 1, & \text{wenn n gerade};\\
\frac{1}{f(n - 1)}, & \text{wenn n ungerade}.
\end{cases}
</math>

== Lösung ==
=== Scheme Prozedur ===
<code>
(define (f n)
    (cond
      [(= n 1) 1]
      [(= (modulo n 2) 0) (+ (f (/ n 2)) 1)]
      [else (/ 1 (f (- n 1)))]))
</code>
<run>
(f 3)
</run>

=== Handrechnung ===
<math>
\begin{array}{ccccc}
f(1) & = & 1 \\
f(2) & = & f(1) + 1 & = & 2 \\
f(3) & = & 1 / f(2) & = & 1 / 2 \\
f(4) & = & f(2) + 1 & = & 3 \\
f(5) & = & 1 / f(4) & = & 1 / 3 \\
f(6) & = & f(3) + 1 & = & 3 / 2 \\
f(7) & = & 1 / f(6) & = & 2 / 3 \\
...\\
\end{array}
</math>

=== Effizienzsteigerung mit Memoizing ===