BuK/IIm11/BuK-KA-Durchschnittsmenge
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
== Aufgabenstellung ==
Weisen Sie nach, dass die Durchschittsmenge (Schnittmenge) zweier aufzählbarer Mengen $ M_{1},M_{2} \subseteq A^{*} $ eine aufzählbare Menge ist. Implementieren Sie eine zugehörige Aufzählfunktion.
== Satz ==
Die Durchschnittsmenge $ M_{1} \cap M_{2} $ zweier aufzählbarer Mengen $ M_{1},M_{2} \subseteq A^{*} $ ist eine aufzählbare Menge.
== Beweis ==
Gegeben sind die Aufzählprozeduren für die surjektiven Funktionen $ f: \N \rightarrow M_{1} \text{ und } g: \N \rightarrow M_{2} $. Gesucht ist eine Aufzählfunktion $ h: \N \rightarrow M_{1} \cap M_{2} $ mit
$$h(i)=\begin{cases}
f(i), \text{ wenn } \chi_{M_{1} \cap M_{2}}(f(i))\\
h(i+1), \text{ sonst}\\
\end{cases}$$
Die Schnittmenge $ M_{1} \cap M_{2} $ ist aufzählbar, wenn $ h $ berechenbar ist. $ f(i) $ ist für alle $ i \in \N $ berechenbar, da $ M_{1} $ eine aufzählbare Menge ist.
Außerdem ist $ \chi_{M_{1} \cap M_{2}}(w), w \in A^{*} $ mit
$$\chi_{M_{1} \cap M_{2}}(w)=\begin{cases}
wahr, \text{ wenn } \chi_{M_{1}}(w) \wedge \chi_{M_{2}}(w)\\
\perp, \text{ sonst}\\
\end{cases} $$
berechenbar, da die partiellen semi-chrakteristischen Funktionen $ \chi_{M_{1}} und \chi_{M_{2}} $ berechenbar sind.$ \square $
Gesucht:
$ M_{1} \cap M_{2} $ zweier aufzählbar unendliche Mengen $M_{1},M_{2}\subseteq A^{*}$ ist eine aufzählbare Menge.
aufzählbar = abzählbare und berechenbare Lösung:
(1) $ M_{1} \cap M_{2} = \emptyset $
Beispiel.:
$ M_{1} = \text{ungeraden Zahlen} $
$ M_{2} = \text{geraden Zahlen} $
$ M_{1} \cap M_{2} = \emptyset \square $
(2)
Lösungsansatz: Konstruieren einer Methode, die alle Elemente der Schnittmenge geordnet liefert.Dazu notwendig ist eine semi-entscheidbare Funktion, die w als Ergebnis liefert, wenn $ w \in M_{1} \cap M_{2}$, , wobei $w = f(i) = g(j)$.
Wir konstruieren eine semi-entscheidbare Methode, die Schritt für Schritt mithilfe der Aufzählungsfunktionen $f(n)$ und $g(n), n \in \N$ eine Teilmenge aus den aufzählbaren Mengen $M_{1}$ bzw. $M_{2}$ erzeugt. Anschließend kann überprüft werden, ob $w$ in diesen (endlichen) Teilmengen vorhanden ist oder nicht.
$$\chi M(w)=\begin{cases}
wahr, \text{ wenn } f(i) = g(j) = w \text{ für alle } i,j \in \N\\
\perp, \text{ wenn } f(i) \neq g(j) \neq w \text{ für alle } i,j \in \N\\
\end{cases}$$
Aus der Tatsache, dass die Schnittmenge zweier Mengen höchstens die Vereinigung der beiden Mengen darstellt, folgt der Schluss, dass die Schnittmenge selbst auch abzählbar ist. Die Teilmenge einer abzählbaren (unendlichen) Menge ist höchstens abzählbar (unendlich).
Die Berechnung der Schnittmenge und der damit verbundene Nachweis der Berechenbarkeit zweier aufzählbarer Mengen wird mittels Turing-Maschinen realisiert.
Benötigt wird folglich eine Funktion, die ein Ergebnis liefert, wenn $ w \in M_{1}$ und $ w \in M_{2}$. Die jeweilige Überprüfung, ob das Wort zur gegebenen Menge $M_{1}$ gehört, kann mittels Funktion realisiert werden, da in der Behauptung die Aufzählbarkeit gegeben ist. Es existiert also eine semi-entscheidbare Funktion, welche die Existenz von w in $M_{1}$ bestätigt (oder nicht endet). Gleiches gilt auch für $M_{2}$. Die Akzeptanz, ob $ w \in M_{1}$ bzw. $ w \in M_{2}$ kann mittels einer Turing-Maschine realisiert werden.
Wie bereits in der Lehrveranstaltung formale Sprachen und abstrakte Automaten erläutert wurde, ist eine Turing-Maschine in der Lage, das Verhalten anderer Turing-Maschinen zu simulieren. Wir können folglich durch die Verwendung der bereits existenten Turing-Maschinen bestimmen, ob das Wort zu beiden Menge gehört.
In der uten abgebildeten Scheme-Prozedur werden die ersten n Elemente der Schnittmenge als Resultat geliefert. Um gewährleisten zu können, dass die Funktion nach endlich vielen Schritten entscheidet, ob ein Wort w auch in der anderen (Teil-) Menge vorhanden ist, werden die von den Turing-Maschinen akzeptierten Mengen an Wörtern schrittweise und abwechselnd erweitert. Durch die Schaffung der endlichen Teilmengen kann zumindest in den Zwischenschritten das Terminieren nach $n = |M|$ Schritten gewährleistet werden.
<code id="4f7af9c9e5e0b" hidden>
(define stream-car car)
(define stream-cdr
(lambda (stm)
(force (cdr stm))))
(define-syntax stream-cons
(syntax-rules ()
((_ head tail) (cons head (delay tail)))))
(define stream?
(lambda (stm)
(and (pair? stm)(promise? (cdr stm)))))
(define stream-item
(lambda (str nr)
(if(<= nr 0)
(stream-car str)
(stream-item (stream-cdr str) (- nr 1)))))
(define nat-stream-maker
(lambda (start)
(stream-cons start (nat-stream-maker (+ start 1)))))
(define prim?
(lambda (n)
(letrec
((helfer
(lambda (t)
(cond
((> t (sqrt n)) #t)
((= (remainder n t) 0) #f)
(else
(helfer (+ t 2)))))))
(cond
((= n 1) #f)
((= n 2) #t)
((even? n) #f)
(else
(helfer 3))))))
(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 stream-filter
(lambda (stm test)
(cond
((test (stream-car stm)) (stream-cons (stream-car stm) (stream-filter (stream-cdr stm) test)))
(else
(stream-filter (stream-cdr stm) test)))))
(define fib-maker
(lambda (a b)
(stream-cons a (fib-maker b (+ a b)))))
</code>
<code id="4f797f955cc29">
(define make-stream-intersect
(lambda (stm1 stm2)
(letrec ((n 0)
(stm1org stm1)
(stm2org stm2)
(stream-intersect-helper
(lambda (stm1 stm2 n)
(cond
((even? n)
(if(stream-contains? (stream-car stm1) stm2org (/ n 2))
(stream-cons (stream-car stm1) (stream-intersect-helper (stream-cdr stm1) stm2 (+ n 1)))
(stream-intersect-helper (stream-cdr stm1) stm2 (+ n 1))))
(else
(if(stream-contains? (stream-car stm2) stm1org (/ (- n 1) 2) )
(stream-cons (stream-car stm2) (stream-intersect-helper stm1 (stream-cdr stm2) (+ n 1)))
(stream-intersect-helper stm1 (stream-cdr stm2) (+ n 1))))))))
(stream-intersect-helper stm1 stm2 n))))
(define stream-contains?
(lambda (item stm n)
(cond
((equal? item (stream-car stm)) #t)
((= n 0 ) #f)
(else (stream-contains? item (stream-cdr stm) (- n 1))))))
(define natstream (nat-stream-maker 0))
(define oddstream (stream-map natstream(lambda (x) (+ 1 (* 2 x)))))
(define primstream (stream-filter natstream prim?))
(define fibstream (fib-maker 0 1))
</code>
<run id="4f797f955cc93">
(display "fibanocci Zahlen\n")
(print-stream fibstream 10)
(display "geraden Zahlen\n")
(print-stream oddstream 10)
(define intersectstream (make-stream-intersect fibstream oddstream))
(display "Schnittmenge Fibanocci und gerade Zahlen\n")
(print-stream intersectstream 10)
</run>