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 (string->number (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))))
</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>
==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]].
Für die Aufzählbarkeit fehlt noch ein Algorithmus für eine Funktion, welche die Primzahlen berechnen kann.
<b>Problem beim Erstellen von Streams hier im Wiki</b> (z.B. make-stream nicht bekannt ...)
==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.
==Aufgabe 6==
Zeigen Sie, dass jede endliche Menge aufzählbar ist.
==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.
==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.
==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)
(number->string(* 2 i))))
; Die Funktion, die die Menge der ungeraden Zahlen berechnet
(define funktionUngeradeZahlen
(lambda (i)
(number->string(+ (* 2 i) 1))))
;einen Mengengenerator erstellen
(define generiere_aufzaehlbare_menge
(lambda (f)
(stream-map natzahlstream f)))
(define M1 (generiere_aufzaehlbare_menge f1))
(define M2 (generiere_aufzaehlbare_menge f2))
</code>
<run id="51646c4d8077b">
(f1 1)
</run>