BuK-KA-Durchschnittsmenge

Aus ProgrammingWiki

Archivierte Version vom 2014-04-24T23:13:23+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Aufgabenstellung
2 Satz
3 Beweis
4 Implementierung

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

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}} \text{ und } \chi_{M_{2}} berechenbar sind. \square

Implementierung

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

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

BuK-KA-Durchschnittsmenge

Inhaltsverzeichnis

Aufgabenstellung

Satz

Beweis

Implementierung

Suche