BuK/IIm10/BuK-Übung02 G1

Wiki-Quelltext dieser Seite.

=Halteproblem=
==Aufgabenstellung==
Spielen Sie die Betrachtungen zum Halteproblem (s. Vorlesung) mit Scheme-Prozeduren nach.

Hinweis: Definieren Sie ggf. auch eine Prozedur <math>haelt-tricky?</math>, die <math>\#t</math> zurück gibt, wenn das betrachtete Programm P ein Ergebnis berechnet, und <math>\#f</math>, wenn die Berechnung in einer gewissen Zeit T zu keinem Ergebnis führt. Verwenden Sie zeitbeschränkte Berechnungen, deren Implementierungidee einige Kreativität erfordert.

<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
==Lösung==
<code id="4d8a07fbab307">
(define (haelt_fuer_n f n)
   (f n) #t)
(define (test n) n)
(define (haelt f)
  (f 0) #t)
(define (crazy n)
  (cond
    ((haelt crazy) n)
    (else crazy n)))
(define (haelt-tricky f n)
  (cond
    ((= n 10000) #f)
    (else (haelt-tricky f (f n)))))
(define (crazy-tricky n)
  (+ n 1))
</code>

Beispiel-Aufruf für haelt: (haelt crazy)

<run id="4d8a1d477f906"></run>

Beispiel-Aufruf: (haelt-tricky crazy-tricky 0)

<run id="4d8a07fbab38f"></run>

=Beweise=
==Aufgabenstellung==
# Zeigen Sie, dass die Menge der rationalen Zahlen abzählbar unendlich ist.
# Zeigen Sie, dass die Wortmenge <math>A^\ast</math> über <math>A</math> abzählbar unendlich ist.
# Zeigen Sie, dass die Menge der reellen Zahlen überabzählbar unendlich ist.

==Lösung==
===Aufgabe 1===
===Aufgabe 2===
Die Anzahl der Wörter aus einem Alphabet <math>A</math> mit einer bestimmten Länge <math>l</math> ist endlich. Die Zahl der Wörter, die mit der Länge <math>l</math> aus dem Alphabet <math>A</math> gebildet werden können, kann mit

:<math>
\begin{array}{ccc}
\text{Anzahl der Elemente des Alphabets}^\text{Wortl\"ange}&=&A^l
\end{array}</math>

berechen werden.
====Beispiel====
<math>A={a,b,c,d}</math>

<math>
\begin{array}{ccccc}
|A|&=&4&&\\
|A^0|&=&4^0&=&1\\
|A^1|&=&4^1&=&4\\
|A^2|&=&4^2&=&16\\
&&usw.&&\\
\end{array}
</math>

Die Wortmenge <math>A^\ast</math> bildet sich nun aus den unendlich vielen Teilmengen <math>A^i</math>.

Um eine Abbildung der Wortmenge <math>A^\ast</math> auf die natürlichen Zahlen <math>\mathbb{N}</math> zu ermöglichen, ordnet man nun die einzelnen Wörter der Wortmenge nach der längenlexikografischen Ordnung. Anschließend kann jedem Wort eine natürliche Zahl zugeordnet werden.


====Beispiel====
:{| class="wikitable"
|-
! <math>\epsilon</math>!! a !! b !! c !! d !! aa
|-
| 1 || 2 || 3 || 4 || 5 || 6
|}

===Aufgabe 3===

=Bijektive Funktion=
==Aufgabenstellung==
Verifzieren 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.
:<math>
f(n)=\begin{cases}
1, &\text{wenn }n=1;\\
f(\frac{n}{2}), & \text{wenn n gerade};\\
\frac{1}{f(n-1)}, & \text{wenn n ungerade}.
\end{cases}
</math>

<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
==Lösung==

<code id="4d8a1ce97152c" hidden>
(require-library 'sisc/libs/srfi/srfi-69)
(import srfi-69)
</code>

<code id="4d8a103de4770">
(define (biject n)
  (cond
    ((or (< n 1) (not (= (round n) n))) (display "Bitte nur natürliche Zahlen eingeben!"))
    ((= n 1) 1)
    ((ist-gerade n) (+ 1 (biject (/ n 2))))
    (else (/ 1 (biject (- n 1))))))

(define (ist-gerade n)
  (cond
   ((= 1 (modulo n 2)) #f)
   (else #t)))

(define  values (make-hash-table))

(define (memobiject  n)
  (cond
    ((number? (hash-table-ref values n false))(hash-table-ref values n false))
    ((or (< n 1) (not (= (round n) n))) (display "Bitte nur natürliche Zahlen eingeben!"))
    ((= n 1) (hash-table-set! values 1 1))
    ((ist-gerade n) (hash-table-set! values n (+ 1 (biject (/ n 2)))))
    (else (hash-table-set! values n (/ 1 (biject (- n 1))))))
 (hash-ref values n false))
</code>

Beispiel-Aufruf: (biject 5)

<run id="4d8a103de47de"></run>

Beispiel-Aufruf mit Memoizing: (memobiject 1000)

<run id="4d8a103de4842"></run>