BuK-Übung02 G1
Inhaltsverzeichnis |
Halteproblem
Aufgabenstellung
Spielen Sie die Betrachtungen zum Halteproblem (s. Vorlesung) 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 Berechnung in einer gewissen Zeit T zu keinem Ergebnis führt. Verwenden Sie zeitbeschränkte Berechnungen, deren Implementierungidee einige Kreativität erfordert.
Lösung
Beispiel-Aufruf für haelt:
Beispiel-Aufruf zu haelt-tricky:
(Hinweis: Wir empfehlen den lokalen Aufruf der Funktion, da dieser im Wiki, zu einer noch ungeklärten Endlosschleife führt.)
Beweise
Aufgabenstellung
- Zeigen Sie, dass die Menge der rationalen Zahlen abzählbar unendlich ist.
- Zeigen Sie, dass die Wortmenge A^\ast über A abzählbar unendlich ist.
- Zeigen Sie, dass die Menge der reellen Zahlen überabzählbar unendlich ist.
Lösung
Aufgabe 1
Zum Beweis, dass die Menge der rationalen Zahlen abzählbar unendlich ist, also, dass eine bijektive Abbildung \N \rightarrow \Q existiert, ist es zunächst erforderlich, die Abbildung \N \rightarrow \Q^+ zu beweisen.
Dazu eignet sich die Darstellung der rationalen Zahlen in einer Tabelle der folgenden Form:
Aufgabe 2
Die Anzahl der Wörter aus einem Alphabet A mit einer bestimmten Länge l ist endlich. Die Zahl der Wörter, die mit der Länge l aus dem Alphabet A gebildet werden können, kann mit
- \begin{array}{ccc} \text{Anzahl der Elemente des Alphabets}^\text{Wortl\"ange}&=&A^l \end{array}
berechen werden.
Beispiel
A={a,b,c,d} \begin{array}{ccccc} |A|&=&4&&\\ |A^0|&=&4^0&=&1\\ |A^1|&=&4^1&=&4\\ |A^2|&=&4^2&=&16\\ &&usw.&&\\ \end{array}Die Wortmenge A^\ast bildet sich nun aus den unendlich vielen Teilmengen A^i.
Um eine Abbildung der Wortmenge A^\ast auf die natürlichen Zahlen \mathbb{N} 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"
|- ! \epsilon!! a !! b !! c !! d !! aa |- | 1 || 2 || 3 || 4 || 5 || 6 |}
Aufgabe 3
\begin{array}{ccc} Z & \rightarrow & \mathbb{R} \text{ \"uberabz\"ahlbar unendlich} \\ \overline{Z} & \rightarrow & \mathbb{R} \text{ abz\"ahlbar unendlich} \end{array}Auflisten von allen reellen Zahlen zwischen 0 und 1:
\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}Nimmt man nun die Ziffern auf der Diagonalen (a_{00},a_{11},...), ändert diese Zahlen nach dem Muster
- \overline{a_i}=\begin{cases} a_{ii}+1, & \text{wenn }a_{ii}<9\\ 0, & \text{sonst} \end{cases}
und bildet aus den einzelnen Ziffern eine neue Zahl \overline{a}=0.\text{ }\overline{a_0}\text{ }\overline{a_1}\text{ }\overline{a_2}\text{ }\overline{a_3}..., so ist diese Zahl eine neue Zahl in \mathbb{R}. 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 \mathbb{R} auf die natürlichen Zahlen \mathbb{N} nicht möglich.
Daraus folgt: \overline{Z} gilt nicht \rightarrow Z gilt.
Bijektive Funktion
Aufgabenstellung
Verifzieren Sie, dass die folgende Funktion f : \mathbb{N}^+ \rightarrow \mathbb{Q}^+ eine bijektive Funktion ist und implementieren Sie eine Prozedur, die die zugehörige Umkehrfunktion f^{-1} berechnet.
- 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}
Lösung
Beispiel-Aufruf: (biject 5)
Beispiel-Aufruf mit Memoizing: (memobiject 1000)