Aus ProgrammingWiki

Inhaltsverzeichnis

1 Halteproblem
- 1.1 Aufgabenstellung
- 1.2 Lösung
2 Beweise
- 2.1 Aufgabenstellung
- 2.2 Lösung
3 Bijektive Funktion
- 3.1 Aufgabenstellung
- 3.2 Lösung

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

(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))

Beispiel-Aufruf für haelt:

(haelt crazy)

Beispiel-Aufruf zu haelt-tricky:

(haelt-tricky crazy-tricky 0)

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, muss der Nachweis der Existenz einer bijektiven Abbildung $\mathbb{N} \rightarrow \mathbb{Q}$ erbracht werden. Dafür eignet sich das erste Cantor'sche Diagonalargument.

Ein weiterer Ansatz ist es, die Menge der rationalen Zahlen mit folgender Funktion zu beschreiben:

$f(n) \rightarrow A, mit A \subset \mathbb{Q}^+$

$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}$

Lässt man dabei noch alle kürzbaren Brüche weg, so ergeben sich die Teilmengen:

$f(1) = \begin{Bmatrix}1\end{Bmatrix}$

$f(2) = \begin{Bmatrix}1,\frac{1}{2},\frac{2}{1}\end{Bmatrix}$

$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}$

$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}$

$\cdots$

Durch diese Vorgehensweise, können somit alle Elemente von $\mathbb{Q}^+$ ermittelt werden. Es kann festgestellt werden, dass das Ergebnis der Funktion $f(n)$ für endliche $n$ eine abzählbare endliche Menge ist. Das Ergebnis von $f(\infty)$ ist demnach abzählbar unendlich und entspricht zudem $\mathbb{Q}^+$ . Somit ist $\mathbb{Q}^+$ abzählbar unendlich. Das selbe muss demnach auch für $\mathbb{Q}^-$ 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 $\mathbb{N} \rightarrow \mathbb{Q}$ existiert und somit $\mathbb{Q}$ 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 $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

$\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

(require-library 'sisc/libs/srfi/srfi-69) (import srfi-69)

(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))

Beispiel-Aufruf:

(biject 5)

Beispiel-Aufruf mit Memoizing:

(memobiject 1000)

"Naive" Implementation der Umkehrfunktion

(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))))

Beispielaufruf:

(umkehr 1/3)

Implementation der echten Umkehrfunktion:

$f(n) = \begin{cases}1, & n = 1 \\ f(n-1) * 2, & n > 1 \\ f(\frac{1}{n}) + 1, & sonst\end{cases}$

(define (biject-umkehr n) (cond ((= n 1) 1) ((> n 1) (* (biject-umkehr (- n 1)) 2)) (else (+ (biject-umkehr (/ 1 n)) 1))))

Beispielaufruf:

(biject-umkehr 17/3)

BuK-Übung02 G1

Aus ProgrammingWiki

Inhaltsverzeichnis

Halteproblem

Aufgabenstellung

Lösung

Beweise

Aufgabenstellung

Lösung

Aufgabe 1

Aufgabe 2

Beispiel

Beispiel

Aufgabe 3

Bijektive Funktion

Aufgabenstellung

Lösung

Ansichten

Persönliche Werkzeuge

Navigation

Suche

Werkzeuge