BuK/IIm10/BuK-Übung02 G2

Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
= Halteproblem =
== Aufgabe ==
== Lösung ==
<code id="4d8b0c366b24c">
(define haelt-fuer-n?
  (lambda (f n)
    (if (integer? (f n))
        #t
        #f)))

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

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

(define haelt-tricky?
  (lambda (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>
<run id="4d8b0c366b3cf">
(haelt-tricky? test1 10)
</run>
<run id="4d8b0c366b485">
(haelt-tricky? test2 10)
</run>
= 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 ==

== 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).

= Kreativität =

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

= Bijektive Funktion =
== Aufgabe ==
Veriﬁzieren 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 ==
Für die Funktion f(n) gibt es keine Umkehrfunktion, da diese nicht streng monoton ist.
=== Scheme Prozedur ===
<code id="4d90a7d9e439f">
(define f
  (λ (n)
    (cond
      [(= n 1) 1]
      [(= (modulo n 2) 0) (+ (f (/ n 2)) 1)]
      [else (/ 1 (f (- n 1)))])))
</code>
<run id="4d90a7d9e4438">
(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 ===
BuK/IIm10/BuK-Übung02 G2

Suche
