BuK/IIm12/Studenten/sifedeut/uebung3
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
<code id="516bf286e74d7" hidden>
(define stream-car car)
(define stream-cdr
(lambda (stm)
(force (cdr stm))))
;; Konstruktoren
(define-syntax stream-cons
(syntax-rules ()
((_ head tail) (cons head (delay tail)))))
(define stream-item
(lambda (str k)
(if (= k 0)
(stream-car str)
(stream-item (stream-cdr str) (- k 1)))))
(define print-stream
(lambda (stm n)
(cond
((<= n 0) (display "...\n"))
(else
(display (number->string(stream-car stm)))
(display ", ")
(print-stream (stream-cdr stm) (- n 1))))))
(define stream-map
(lambda (stm proc)
(stream-cons
(proc (stream-car stm))
(stream-map (stream-cdr stm) proc))))
(define nat-stream-maker
(lambda ()
(letrec ((n 0)
(nat-stream-maker-helper
(lambda (start)
(stream-cons start (nat-stream-maker-helper (+ start 1))))))
(nat-stream-maker-helper 0))))
(define natstream (nat-stream-maker ))
</code>
=Theorie=
Im Gegensatz zu Funktionen sind Mengen nicht ''berechenbar'', sondern ''entscheidbar''. Man spricht bei '''Mengen''' von '''Entscheidbarkeit'''
==relativ entscheidbare Mengen==
Eine Menge $M_1$ ist <b>relativ entscheidbar</b> zur Menge $M_2 (M_1,M_2\subseteq A^*)$, wenn die <b>charakteristische Funktion</b> $\chi_{M_1,M_2}$ mit
$\chi_{M_1,M_2}(w)=\begin{cases}wahr & \text{,wenn } w\in M_1\\falsch & \text{, wenn } w\in M_2\setminus M_1\end{cases}$
eine totale und berechenbare (kurz: <b>total berechenbar</b>) Funktion ist. D.h. man kann für <u>jedes</u> Element der Menge $M_2$ sagen, ob es sich um ein Element der Menge $M_1$ handelt oder nicht.
==(absolut) entscheidbare Mengen==
Eine Menge $M\subseteq A^*$ ist (absolut) <b>entscheidbar</b>, wenn $M$ zu $A^*$ relativ entscheidbar ist, d.h. wenn $\chi_{M,A^*}$, kurz $\chi_{M}$, mit
$\chi_{M}(w)=\begin{cases}wahr & \text{,wenn } w\in M\\falsch & \text{, wenn } w\in A^*\setminus M\end{cases}$
eine total berechenbare Funktion ist.
Anders gesagt: $M$ ist entscheidbar, wenn es eine Prozedur (eine in einer beliebigen Programmiersprache implementierte Funktion) <tt>chi</tt> gibt, die für jedes Wort $w$ aus $A^*$ nach endlicher Zeit stoppt und entweder <tt>#t</tt> ($w\in M$) oder <tt>#f</tt> ($w \not\in M$) ausgibt.
<nowiki>
> (chi "bin_in_M")
#t
> (chi "bin_nicht_in_M")
#f</nowiki>
==Aufzählbar==
Eine Menge $M\subseteq A^*$ heißt (rekursiv) aufzählbar, wenn es entweder eine total berechbare surjektive Funktion $f\colon\N\mapsto M$ gibt, oder es gilt $M = \emptyset$. Man nennt $f$ eine <b>Aufzählprozedur</b> oder ein <b>Aufzählverfahren</b> von $M$.
Stark vereinfacht: aufzählbar $=$ abzählbar + berechenbar
==von Aufzählbar zu Entscheidbar==
Im allgemeinen Fall sichert die Aufzählbarkeit einer Menge lediglich deren Semi-Entscheidbarkeit.
Eine Menge $M\subseteq A^*$ ist <b>semi-entscheidbar</b>, wenn die partielle (semi-charakteristische) Funktion $\chi'_M \colon A^*\mapsto\{\text{wahr}\}$ mit
$\chi'_M(w)=\begin{cases}wahr & \text{, wenn }w\in M\\\perp & \text{, sonst}\end{cases}$
berechenbar ist.
=Übungsaufgaben zur Entscheidbarkeit und Aufzählbarkeit=
==Aufgabe 1 (Deutschmann, Horbach)==
Wie viele berechenbare charakteristische Funktionen gibt es?
Hinweis: Potenzmenge unendlicher Mengen
$\mathscr{P}(A^*)$ besitzt überabzählbar unendlich viele Mengen
Die Teilmengen von $A^*$ sind selbst endlich oder abzählbar unendlich.
Deshalb gibt es überabzählbar unendlich viele charakteristische Funktionen $\chi_M$.
==Aufgabe 2==
Zeigen Sie, dass die beiden Mengen aus den Beispielen entscheidbar sind. Schreiben Sie je eine entsprechende Prozedur für die jeweilige charakteristische Funktion (ProgrammingWiki).
'''Beispiel 1''': endliche Menge
$A^*=\{a,b\}^*$ und $M\subset A^*=\{w | w\in A^* \text{und } \left|w\right|=3\}$
<code id="51647c6ec3afa">
(define
endlicheMenge (list 'aaa 'aab 'aba 'abb 'baa 'bab 'bba 'bbb))
(define inList
(lambda (wrd lst)
(cond
[(eq? (car lst) wrd) #t]
[(not (null? (cdr lst))) (inList wrd (cdr lst))]
[else #f]))
)
</code>
<run id="51647cc8c7eb7">
(car endlicheMenge)
</run>
'''Beispiel 2''': abzählbar unendliche Menge
$M$ ist die Menge aller Wörter, die aus beliebig vielen <tt>a</tt>'s und <tt>b</tt>'s bestehen und mit <tt>a</tt> beginnen.
$A^*=\{a,b\}^*$ und $M\subset A^*=\{w=aw'| w'\in A^*\}$
<code id="516482c382508">
(define istWortInAlphabet
(lambda (wrd)
(cond
[(string=? (string (car (string->list wrd))) "a") #t]
[else #f])))
</code>
<run id="516482fa04d5f">
(istWortInAlphabet "aaabb")
</run>
==Aufgabe 3 (Deutschmann, Horbach)==
Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.
Wdh: Aufzählbar = abzählbar + berechenbar
<u>abzählbar:</u> Für die Menge der geraden Zahlen $G$ gilt: $G\subset\Z$, die abzählbar unendlich sind [[BuK/IIm12/Studenten/sifedeut/uebung2#Aufgabe_2_.28Deutschmann.2C_Horbach.29 | Beweis]]
<u>berechenbar:</u> Es existiert ein Algorithmus, der für die Funktion $f(x)$ für jedes $x \in D_f$ den zugehörigen Funktionswert $f(x)$ ermittelt
$f(x)=\begin{cases}-i & \text{, wenn i gerade}\\i+1 & \text{, wenn i ungerade}\end{cases}$
<code id="51648baa09280">
(define gibGeradeZahl
(lambda (x)
(cond
[(= (modulo x 2) 0) (* -1 x)]
[else (+ x 1)])))
</code>
<run id="51648bd18dedd">
(gibGeradeZahl 4)
</run>
<language>Scheme</language>
==Aufgabe 4==
Zeigen Sie, dass die Menge der Primzahlen P aufzählbar ist.
Primzahlen sind abzählbar unendlich [[BuK/IIm12/Studenten/sifedeut/uebung2#Aufgabe_2_.28Deutschmann.2C_Horbach.29|Beweis]].
Aufzählbar = abzählbar + berechenbar
Aufzählbar:
# es gibt eine Aufzählprozedur $h:\N\mapsto A^*$
# total berechenbar
# mind. surjektiv
Berechenbar = "Es existiert eine implementierte Funktion (also eine Prozedur)"
Für die Aufzählbarkeit fehlt noch ein Algorithmus für eine Funktion, welche die Primzahlen berechnen kann.
<code id="516bfdd965f03">
(define kleinster-teiler
(lambda (n)
;finde a, sodass gilt: a^n mod n = a
(finde-teiler 2 n)
)
)
(define finde-teiler
(lambda (a n)
;teile n durch a, wobei 2 < a < sqrt(n)
(cond ((> (sqrt a) n) n)
((teilt? a n) a)
(else (finde-teiler (+ a 1) n))
)
)
)
(define teilt?
(lambda (a b)
(= (modulo b a) 0 )
)
)
(define prime?
(lambda (n)
(= (kleinster-teiler n) n)
)
)
(define f
(lambda (x)
(cond
[(prime? x) x]
[else 2])))
(define primeStream (stream-map natstream f))
</code>
<run id="516c57374d066">(print-stream primeStream 30)</run>
==Aufgabe 5==
Wir wissen, dass $A^*$ eine abzählbar unendliche Menge ist. Zeigen Sie, dass $A^*$ auch aufzählbar ist.
Hinweis: Hierzu ist es notwendig ein Aufbauschema für $A^*$ zu entwerfen und anschließend eine Prozedur dafür zu implementieren.
<code id="516c710a372ad">(define pow
(lambda (number exp)
(if (= exp 0)
1
(* number (pow number (- exp 1))))))
(define getElement
(lambda (set index)
(if (= index 1)
(car set)
(getElement (cdr set) (- index 1)))))
(define cardinalNumber
(lambda (set)
(if (null? set)
0
(+ 1 (cardinalNumber (cdr set))))))
(define calculateWordSize
(lambda (set index)
(letrec ((calculateWordSizeReal
(lambda (cardinalNumber index sum exp)
(if (>= sum index)
0
(+ 1
(calculateWordSizeReal
cardinalNumber
index
(+ sum (pow cardinalNumber exp))
(+ 1 exp)))))))
(calculateWordSizeReal (cardinalNumber set) index 0 1))))
;Berechnet die Anzahl der Wörter mit Länge <= letterCount
(define numberOfWords
(lambda (cardinalNumber letterCount)
(if (= letterCount 0)
0
(+
(pow cardinalNumber letterCount)
(numberOfWords cardinalNumber (- letterCount 1))))))
(define createWord
(lambda (set wordnumber cardinalNumber lettersRemaining)
(if (= 0 lettersRemaining)
""
(let ((sectionSize (pow cardinalNumber (- lettersRemaining 1))))
(let ((rest (modulo wordnumber sectionSize))
(result (quotient wordnumber sectionSize)))
(if (= 0 rest)
(string-append
(string (getElement set result))
(createWord set sectionSize cardinalNumber (- lettersRemaining 1)))
(string-append
(string (getElement set (+ result 1)))
(createWord set rest cardinalNumber (- lettersRemaining 1)))))))))
(define fCreator
(lambda (set)
(lambda (index)
(if (= index 0)
""
(let((cardinalNumber (cardinalNumber testSet))
(lettersRemaining (calculateWordSize testSet index)))
(createWord testSet (- index (numberOfWords cardinalNumber (- lettersRemaining 1))) cardinalNumber lettersRemaining))))))</code>
<run id="516c7139d0aab">(define testSet
'(#\a #\b #\c))
(define f
(fCreator testSet))
(f 30)</run>
== Aufgabe 6 ==
Zeigen Sie, dass jede endliche Menge $M$ aufzählbar ist.
Lösung:
Aufzählbar = abzählbar + berechenbar
Laut Definition heißt eine Menge $M$ endlich, wenn es eine natürliche Zahl $n$ gibt, sodass eine Bijektion zwischen $M$ und der Menge aller natürlichen Zahlen kleiner als $n$ existiert, d.h. jede endliche Menge ist abzählbar.
Eine Menge $M$ heißt (rekursiv) aufzählbar wenn es entweder eine total berechenbare surjektive Funktion $f:N \mapsto M$ gibt, oder es gilt $M = \emptyset$. Man nennt $f$ eine Aufzählprozedur oder ein Aufzählverfahren von M.
Es gibt eine Funktion $f$, die als Eingabe die natürlichen Zahlen $\N$ nimmt und auf jedes Element der endlichen Menge $M$ abbildet. $f$ ist berechenbar, da es eine total berechenbare surjektive Funktion $f : \N \mapsto M$ gibt. Es wird der Reihe nach jedes Element aus $\N$ einem Element aus $M$ zugeordnet. Ist $f$ surjektiv, können die restlichen Elemente aus $\N$ auf ein beliebiges Element von $M$ abgebildet werden. Somit ist $f$ surjektiv, total und berechenbar.
<language>Scheme</language>
<language>Scheme</language>
==Aufgabe 7==
Die Menge $G$ der Gitterpunkte $(0,0),(0,1),...$ einer x-y-Ebene ist aufzählbar.
# Geben Sie eine Funktion f an, die $\N$ bijektiv auf $G$ abbildet.
# Definieren Sie eine Ordnungsrelation $p<$ in G
# Geben Sie eine Funktion k zur Berechnung der Platznummer $k(x,y)$ des betrachteten Gitterpunktes $(x,y)$ an.
# Geben Sie eine Aufzählprozedur für $G$ an und begründen Sie deren Berechenbarkeit.
Lösung:
zu 1.
$$g(z) =
\begin{cases}
(x,y) & \text{, mit } x=w-y,\\
& y = z - t \text{, wobei }\\\\
& w = \lfloor \frac{\sqrt{8z+1}-1}{2}\rfloor,\\\\
& t = \frac{w(w+1)}{2}
\end{cases} \text{, mit }z\in\N$$
zu 2.
Die Paare sollen nach dem aufsteigendem Funktionswert der Funktion $\pi (x,y) = \frac{(x + y)(x + y + 1)}{2} + y$ geordnet werden.
zu 3.
Die Funktion aus 2. sei $k(x,y)$.
zu 4.
<code id="516da1d9e1df3">
(define getX
(lambda (z)
(- (getW z) (getY z)) ))
(define getY
(lambda (z)
(- z (getT z))))
(define getW
(lambda (z)
(floor (/ (- (sqrt (+ (* 8 z) 1)) 1) 2))))
(define getT
(lambda (z)
(/ (* (getW z) (+ (getW z) 1)) 2)))
(define g
(lambda (z)
(cons (getX z) (getY z))))
(define pointStream (stream-map natstream g))
(define getStreamItems
(lambda (stm cnt)
(cond
[(<= cnt 0) (cons '... '())]
[else (cons (stream-car stm) (getStreamItems (stream-cdr stm) (- cnt 1)))])))
</code>
<run id="516da3563f2a9">(getStreamItems pointStream 10)
;(stream-item pointStream 10)</run>
==Aufgabe 8==
Das Halteproblem ist semi-entscheidbar. Beweisen Sie diese Aussage.
==Aufgabe 9==
Geben Sie für die Menge $FIBS$ der Fibonacci-Zahlwörter eine Aufzählfunktion an und begründen Sie deren Berechenbarkeit. Weisen Sie nach, dass $FIBS$ sogar entscheidbar ist.
Per Definition ist eine Menge $M$ aufzählbar, wenn es eine totale berechenbare Prozedur $f$ gibt, welche die Menge $\N$ auf die Menge $M$ abbildet.
$M$ ist hier die Menge der Fibonacci-Zahlwörter.
#
'''Überarbeiten!!!'''
Die Aufzählprozedur lautet wie folgt:
$$f(n) = \begin{cases}
g(n), & \text{wenn } g(n) \in \text{ M};\\
0, & sonst.
\end{cases}$$
Für $g(n)$ gilt:
$$g(n) = \begin{cases}
0, & \text{wenn } n=0;\\
1, & \text{wenn } n=1;\\
(n-1) + (n-2), & sonst.
\end{cases}$$
Für beide, also für $f$ und $g$, lassen sich entsprechende Scheme Ausdrücke angeben:
<code id="516c02885fa86">
; g(n)
(define g
(lambda (n)
(cond
((= n 0) 0)
((= n 1) 1)
(else (+ (g (- n 1)) (g (- n 2)))))))
; natstream ist schon zu Begin dieser Wiki-Seite erstellt worden und kann einfach genutzt werden
(define fibstream stream-map natstream g)
</code>
<run id="516c02885faf0">
(display "Die ersten 10 Elemente der Fibonacci-Menge\n")
(print-stream fibstream 10)
</run>
Es wird noch eine charakteristische Funktion $\chi$ benötigt.
<code id="516c0bc814bc0">
(define semi_chi
(lambda (m w)
(letrec
(( helfer
( lambda ( stm )
(if (string=? w (stream-car stm ))
#t
(helfer (stream-cdr stm ))))))
(helfer m ))))
</code>
<run id="516c130945269">(semi_chi fibstream 5)</run>
==Aufgabe 10==
Übertragen Sie die vorhergehende Übungsaufgabe sinngemäß auf die Menge der Quadratzahlen $QZ = \{n^2 | n\in\N\}$.
==Aufgabe 11==
Weisen Sie nach, dass die Menge $M$ aller "Wörter" aus $\{a,b\}^*$, die mit a beginnen, semi-entscheidbar ist.
==Aufgabe 12==
Definieren Sie die Menge der geraden Zahlen (Zahlwörter) und die der ungeraden Zahlen (Zahlwörter) und veranlassen Sie das ProgrammingWiki 30 Elemente der Vereinigungsmenge auszugeben.
$M_1$ ist die Menge der geraden Zahlen
$f_1(i)=string(2i)$
$M_2$ ist die Menge der ungeraden Zahlen
$f_2(i)=string(2i+1)$
Für die Vereinigung der beiden Mengen kann die folgende Funktion genommen werden:
$h(i)=\begin{cases}f_1(\frac{i}{2}) & \text{, wenn }i\text{ gerade}\\f_2(\frac{i-1}{2}) & \text{, wenn }i\text{ ungerade}\end{cases}$
<code id="51646bc0d522b">
; Die Funktion, die die Menge der geraden Zahlen berechnet
(define funktionGeradeZahlen
(lambda (i)
(* 2 i)))
; Die Funktion, die die Menge der ungeraden Zahlen berechnet
(define funktionUngeradeZahlen
(lambda (i)
(+ (* 2 i) 1)))
(define geraderStream (stream-map natstream funktionGeradeZahlen))
(define ungeraderStream (stream-map natstream funktionUngeradeZahlen))
; Funktion für die Vereinigungsmenge der beiden Streams
(define geradeVungerade-stream-maker
(lambda (ungerade gerade)
(letrec ((n 0)
(geradeVungerade-stream-maker-helper
(lambda (n ungeradestm geradestm)
(if (even? n)
(stream-cons (stream-car geradestm) (geradeVungerade-stream-maker-helper (+ n 1) ungeradestm (stream-cdr geradestm)))
(stream-cons (stream-car ungeradestm) (geradeVungerade-stream-maker-helper (+ n 1) (stream-cdr ungeradestm) geradestm))))))
(geradeVungerade-stream-maker-helper n ungerade gerade))))
(define mergeStream (geradeVungerade-stream-maker ungeraderStream geraderStream))
</code>
<run id="51646c4d8077b">
(display "gerade Zahlen\n")
(print-stream geraderStream 30)
(display "ungerade Zahlen\n")
(print-stream ungeraderStream 30)
(display "Vereinigungsmenge\n")
(print-stream mergeStream 30)
</run>