IIm10/BuK-Übung02 G2

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== Intuitiver Berechnbarkeitsbegriff ==
<code id="4d89f4861d3aa">
(define haelt-fuer-n?
  (λ (f n)
    (if (integer? (f n))
        #t
        #f)))
</code>

<code id="4d89f4861d42c">
(define haelt?
  (λ (f)
    (haelt-fuer-n? f 0)))
</code>

<code id="4d89f4861d48a">
(define crazy
  (λ (n)
    (if (haelt? crazy n)
        (crazy n)
        n)))
</code>

<code id="4d89f4861d4e8">
(define haelt-tricky?
  (λ (f timeout)
    (letrec 
        ([ft (thread f)]
         [helper
          (λ (timeLeft)
            (if (thread-running? ft)
                (if (= timeLeft 0)
                    #f
                    (begin (sleep 1) (helper (- timeLeft 1))))
                #t))])
      (helper timeout))))
</code>

<code id="4d89f4861d54c">
(define test1
  (λ ()
    (print "hallo")))

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

<run id="4d89f4861d5c2">
(haelt-tricky? test1 10)
</run>

<run id="4d89f4861d616">
(haelt-tricky? test2 10)
</run>


=== Bijektive Funktion ===
Es sei eine Funktion <math>f:{\mathbb{N}}^{+}  \rightarrow {\mathbb{Q}}^{+}</math> gegeben: <br><br>
<math>
f(n) = \left\{\begin{matrix}
1, & \mbox{wenn } n=1 \mbox{,}\\ 
f(\frac{n}{2})+1, & \mbox{wenn } n \mbox{ gerade,}\\ 
\frac{1}{f(n-1)}, & \mbox{wenn } n \mbox{ ungerade.}
\end{matrix}\right.
</math>

Die Funktion <math>f</math> ist eine bijektive Abbildung, wenn eine Umkehrfunktion <math>f^{-1}</math> existiert. Also wenn für alle 
<math>y \in Y</math> genau ein <math>x \in X</math> mit 
<math>f\left(x\right) = y</math> existiert.

Um die Funktion zu testen, werden für <math>n = 1,2,...,7</math> die Ergebnisse per Hand begerechnet:
<br><br><math>f(1) = 1</math>
<br><br><math>f(2) = f(2/2)+1 = f(1)+1 =2</math>
<br><br><math>f(3) = \frac{1}{f(3-1)}=\frac{1}{f(2)}=\frac{1}{2}</math>
<br><br><math>f(4) = f(4/2)+1 = f(2)+1 = 2+1=3</math>
<br><br><math>f(5) = \frac{1}{f(5-1)}= \frac{1}{f(4)}= \frac{1}{3}</math>
<br><br><math>f(6) = f(3)+1=\frac{3}{2}</math>
<br><br><math>f(7) = \frac{1}{f(6)}=\frac{1}{\frac{3}{2}}=\frac{2}{3}</math>

Die Funktion sieht folgendermaßen in Scheme aus:
<code id="4d90fd9e3e421">
(define fkt
  (lambda (n)
    (if (= n 1) 
        1 
        (if (= (modulo n 2) 0) 
            (+ 1 (fkt(/ n 2)))
            (/ 1 (fkt(- n 1))) 
         )
     )
  )
)
</code>

Zu der Funktion 2 Beispiel-Aufrufe:
<run id="4d90fd9e3e4bb">
(fkt 6)
</run>
<run id="4d90fd9e3e535">
(fkt 7)
</run>

Daraus entsteht dann die Umkehrfunktion.