BuK/IIm11/BuK-KA-Durchschnittsmenge

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 Scheme-Repräsentation.


== Satz ==

Die Durchschnittsmenge $ M_{1} \cap M_{2} $ zweier aufzählbarer Mengen $ M_{1},M_{2} \subseteq A^{*} $ ist eine aufzählbare Menge.


== Beweis 1 ==

Gegeben sind die surjektiven, berechenbaren Funktionen $ f: \N \rightarrow M_{1} \text{ und } g: \N \rightarrow  M_{2} $. Gesucht ist eine surjektive, berechenbare Aufzählfunktion $ h: \N \rightarrow M_{1} \cap M_{2} $.


Es werden folgende zwei Fälle unterschieden:

# $ M_{1} \cap M_{2} = \emptyset $
# $ M_{1} \cap M_{2} \neq \emptyset $

Da $ M_{1} \cap M_{2} $ nur eine leere oder eine nichtleere Menge sein kann, ist diese Fallunterscheidung vollständig.


;Fall 1
: $ M_{1} \cap M_{2} $ ist aufzählbar.
;Fall 2
: Wir definieren die Aufzählfunktion $ h: \N \rightarrow M_{1} \cap M_{2} $ mit 

$$h(i)=\begin{cases}
f(x), \text{ wenn } f(x) = g(y) \text{ mit } \pi_{i}(x,y)\\
a, \text{ sonst}\\
\end{cases} \text{ und }\;a \in M_{1} \cap M_{2}\text{ . }$$ 

: $ h $ ist berechenbar, da $ f $ und $ g $ für alle natürlichzahligen Argumente berechenbar sind. Auch ist die Umkehrung der cantorschen Paarungsfunktion $ \pi_{i}(x,y) $ für alle $ i \in \N $ berechenbar. $ \square $ 


== Beweis 2 ==

Gegeben sind die surjektiven, berechenbaren Funktionen $ f: \N \rightarrow M_{1} \text{ und } g: \N \rightarrow  M_{2} $. Gesucht ist eine surjektive, berechenbare Aufzählfunktion $ h: \N \rightarrow M_{1} \cap M_{2} $.


Analog zum ersten Beweis werden die folgenden zwei Fälle unterschieden:

# $ M_{1} \cap M_{2} = \emptyset $
# $ M_{1} \cap M_{2} \neq \emptyset $

Da $ M_{1} \cap M_{2} $ nur eine leere oder eine nichtleere Menge sein kann, ist diese Fallunterscheidung vollständig.


;Fall 1
: $ M_{1} \cap M_{2} $ ist aufzählbar.
;Fall 2
: Wir definieren zwei nichtleere, endliche Mengen $ F = \big\{f(j),\:j = 0,1,\dotsc,i \big\} \text{ und } G = \big\{g(j),\:j = 0,1,\dotsc,i \big\} $.
:
:
: Die Aufzählfunktion $ h $ definert sich nun aus 

$$h(i)=\begin{cases}
f(i), \text{ wenn } f(i) \in G\\
k(i), \text{ sonst}\\
\end{cases}$$ 


$$\text{ mit } k(i)=\begin{cases}
g(i), \text{ wenn } g(i) \in F\\
a, \text{ sonst}\\
\end{cases} \text{ und }\;a \in M_{1} \cap M_{2}\text{ . }$$ 

: $ h $ ist berechenbar, da $ f $ und $ g $ für alle natürlichzahligen Argumente berechenbar sind. Außerdem sind $ F $ und $ G $ endliche Mengen und daher entscheidbar. $ \square $ 


== Implementierung ==

Die Herausforderung bei der Implemtierung der Aufzählungsfunktion $ h $ ergibt sich aus den Vergleichen, da die Reihenfolgen der Mengen $ M_{1} \text{ und } M_{2} $ verschieden seien können. Dem kann durch zwei Pools entgegengewirkt werden, welche je Menge die Elemente aufbehalten, welche noch zu keinem erfolgreichen Vergleich führten.

<code id="4f7af8c9e4e0b" 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 print-stream
  (lambda (stm n)
    (cond
      ((<= n 0) (display "...\n"))
      (else
       (display (stream-car stm))
       (display ", ")
       (print-stream (stream-cdr stm) (- n 1))))))
(define stream-item
  (lambda (str k)
    (if (= k 0)
      (stream-car str)
      (stream-item (stream-cdr str) (- k 1)))))


  (define contains?
  (lambda(element ls)
    (cond
      [(not (list? ls)) #f]
      [(null? ls) #f]
      [(= (car ls) element) #t]
      [else (contains? element (cdr ls))]
    )
  )
)
</code>
<code id="4f793f957cc30">

(define intersection
  (lambda (f g)
    (letrec(
      (next-element
        (lambda (pool-f pool-g i)
          (let (
                (f-element (f i))
                (g-element (g i))
            )
            (begin
              (if (contains? f-element pool-g)
                  (stream-cons f-element (next-element pool-f (append pool-g (list g-element)) (+ i 1)))
                  (if (contains? g-element (append pool-f (list f-element)))
                    (stream-cons g-element (next-element (append pool-f (list f-element)) pool-g (+ i 1)))
                    (next-element (append pool-f (list f-element)) (append pool-g (list g-element)) (+ i 1))
                  )
              )
            )
          )
        )
       ))
      (next-element '() '() 1)
    )
  )
)
</code>
<run id="4f797f955cc94">
(define f (lambda (x) (* 2 x)))
(define g (lambda (x) (* 3 x)))
(print-stream (intersection f g) 20)
</run>