BuK-Übung02 G1

Aus ProgrammingWiki
< BuK < IIm10
Archivierte Version vom 2011-03-23T16:16:41+00:00. Aktuelle Version

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: (haelt-tricky crazy-tricky 0)



Beweise
Aufgabenstellung
  1. Zeigen Sie, dass die Menge der rationalen Zahlen abzählbar unendlich ist.
  2. Zeigen Sie, dass die Wortmenge A^\ast über A abzählbar unendlich ist.
  3. 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 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
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)