BuK/IIm10/BuK-Übung02 G1
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
=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.
==Lösung==
<code id="4d8a07fbab307">
(define (haelt_fuer_n f n)
(f n) #t)
(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:
<run id="4d8a1d477f906">(haelt crazy)</run>
Beispiel-Aufruf zu haelt-tricky:
<run id="4d8a07fbab38f">(haelt-tricky crazy-tricky 0)</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==
<language>Scheme</language>
===Aufgabe 1===
Zum Beweis, dass die Menge der rationalen Zahlen abzählbar unendlich ist, muss der Nachweis der Existenz einer bijektiven Abbildung <math>\mathbb{N} \rightarrow \mathbb{Q}</math> erbracht werden. Dafür eignet sich das [http://de.wikipedia.org/wiki/Cantors_erstes_Diagonalargument erste Cantor'sche Diagonalargument].
Ein weiterer Ansatz ist es, die Menge der rationalen Zahlen mit folgender Funktion zu beschreiben:
<math>f(n) \rightarrow A, mit A \subset \mathbb{Q}^+</math>
<math>f(n) = \begin{cases}\{1\}, & n = 1\\f(n-1) \cup \begin{Bmatrix}\frac{1}{n},\frac{2}{n},\cdots,\frac{n-1}{n},\frac{n}{1},\frac{n}{2},\cdots,\frac{n}{n-1}\end{Bmatrix}, & sonst\end{cases}</math>
Lässt man dabei noch alle kürzbaren Brüche weg, so ergeben sich die Teilmengen:
<math>f(1) = \begin{Bmatrix}1\end{Bmatrix}</math>
<math>f(2) = \begin{Bmatrix}1,\frac{1}{2},\frac{2}{1}\end{Bmatrix}</math>
<math>f(3) = \begin{Bmatrix}1,\frac{1}{2},\frac{2}{1},\frac{1}{3},\frac{2}{3},\frac{3}{1},\frac{3}{2}\end{Bmatrix}</math>
<math>f(4) = \begin{Bmatrix}1,\frac{1}{2},\frac{2}{1},\frac{1}{3},\frac{2}{3},\frac{3}{1},\frac{3}{2},\frac{1}{4},\frac{3}{4},\frac{4}{1},\frac{4}{3}\end{Bmatrix}</math>
<math>\cdots</math>
Durch diese Vorgehensweise, können somit alle Elemente von <math>\mathbb{Q}^+</math> ermittelt werden.
Es kann festgestellt werden, dass das Ergebnis der Funktion <math>f(n)</math> für endliche <math>n</math> eine abzählbare endliche Menge ist.
Das Ergebnis von <math>f(\infty)</math> ist demnach abzählbar unendlich und entspricht zudem <math>\mathbb{Q}^+</math>.
Somit ist <math>\mathbb{Q}^+</math> abzählbar unendlich. Das selbe muss demnach auch für <math>\mathbb{Q}^-</math> gelten, da beide Mengen die selbe Größe haben. Einzig die 0 muss noch abgebildet werden, was natürlich ebenfalls kein Problem darstellt.
Somit ist klar, dass eine bijektive Abbildung <math>\mathbb{N} \rightarrow \mathbb{Q}</math> existiert und somit <math>\mathbb{Q}</math> abzählbar unendlich ist.
Diese Funktion lässt sich ebenfalls in einem entsprechendem Algorithmus abbilden.
===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===
<math>
\begin{array}{ccc}
Z & \rightarrow & \mathbb{R} \text{ \"uberabz\"ahlbar unendlich} \\
\overline{Z} & \rightarrow & \mathbb{R} \text{ abz\"ahlbar unendlich}
\end{array}
</math>
Auflisten von allen reellen Zahlen zwischen 0 und 1:
<math>
\begin{array}{ccc}
a_0&=&0.\text{ }a_{00}\text{ }a_{01}\text{ }a_{02}\text{ }a_{03}...\\
a_1&=&0.\text{ }a_{10}\text{ }a_{11}\text{ }a_{12}\text{ }a_{13}...\\
a_2&=&0.\text{ }a_{20}\text{ }a_{21}\text{ }a_{22}\text{ }a_{23}...\\
a_3&=&0.\text{ }a_{30}\text{ }a_{31}\text{ }a_{32}\text{ }a_{33}...\\
&usw.&
\end{array}
</math>
Nimmt man nun die Ziffern auf der Diagonalen (<math>a_{00},a_{11},...</math>), ändert diese Zahlen nach dem Muster
:<math>
\overline{a_i}=\begin{cases}
a_{ii}+1, & \text{wenn }a_{ii}<9\\
0, & \text{sonst}
\end{cases}
</math>
und bildet aus den einzelnen Ziffern eine neue Zahl <math>\overline{a}=0.\text{ }\overline{a_0}\text{ }\overline{a_1}\text{ }\overline{a_2}\text{ }\overline{a_3}...</math>, so ist diese Zahl eine neue Zahl in <math>\mathbb{R}</math>. Dies kann unendlich oft wiederholt werden, man kann nie alle reelle Zahlen zwischen 0 und 1 auflisten. Damit ist auch eine Abbildung von den reellen Zahlen <math>\mathbb{R}</math> auf die natürlichen Zahlen <math>\mathbb{N}</math> nicht möglich.
Daraus folgt: <math>\overline{Z}</math> gilt nicht <math>\rightarrow</math> <math>Z</math> gilt.
=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>
<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:
<run id="4d8a103de47de">(biject 5)</run>
Beispiel-Aufruf mit Memoizing:
<run id="4d8a103de4842">(memobiject 1000)</run>
"Naive" Implementation der Umkehrfunktion
<code id="4d909d64f2d57">(define nzuq
(lambda (n)
(if (= n 1)
1
(if (= 0 (modulo n 2))
(+ (nzuq (/ n 2)) 1)
(/ 1 (nzuq (- n 1)))))))
(define count 0)
(define umkehr
(lambda (n)
(set! count (+ count 1))
(if (= (nzuq count) n)
count
(umkehr n))))</code>
Beispielaufruf:
<run id="4d909d64f2e30">(umkehr 1/3)</run>
Implementation der echten Umkehrfunktion:
<math>f(n) = \begin{cases}1, & n = 1 \\ f(n-1) * 2, & n > 1 \\ f(\frac{1}{n}) + 1, & sonst\end{cases}</math>
<code>
(define (biject-umkehr n)
(cond
((= n 1) 1)
((> n 1) (* (biject-umkehr (- n 1)) 2))
(else (+ (biject-umkehr (/ 1 n)) 1))))
</code>
Beispielaufruf:
<run>
(biject-umkehr 17/3)
</run>