KA

Aus ProgrammingWiki

Archivierte Version vom 2012-04-10T20:04:19+00:00. Aktuelle Version

Kreativaufgaben

Schnittmengen-Aufgabe

Satz:

Die Durchschnittsmenge M_1 \cap M_2 zweier aufzählbar unendlicher Mengen M_1, M_2 \subseteq A^* ist eine aufzählbare Menge.

Diagramm Durchschnittsmenge

Beweis:

Gegeben sind die Aufzählprozeduren f und g für die surjektiven Funktionen f: N \mapsto M_1 und g: N \mapsto M_2.

Hierfür kann eine Aufzählfunktion definiert werden: h: \N \mapsto M_1 \subseteq M_2 mit

h(i) = \begin{cases} f(\frac{i}{2}), & \text{wenn } i \text{ gerade };\\ g(\frac{i - 1}{2}), & \text{sonst}. \end{cases}

h ist berechenbar, da f und g fur alle natürlichzahligen Argumente berechenbar sind.

Problem: Es kann nicht geprüft werden, ob ein Element aus M1 auch in M2 enthalten ist, da die Funktion nie terminieren würde bevor alle Elemente aufgezählt sind.

Idee: Falls die Schnittmenge nicht leer ist, gibt es zwei Pools, welche nachschauen ob das jeweilige Element f(n), bzw. g(n) in dem anderen Pool enthalten ist.

Prozedur:

(define nat-stream
  (make-stream 0 (lambda (i) (+ i 1))))

(define fibstream (stream-map fib nat-stream))

(define stream-intersection2
  (lambda (m1 m2)
    (letrec 
        ((intersec-f
          (lambda (m1 m2 list1 list2)
            (let ((x (stream-car m1)))
              (if (member x list2)
                  (stream-cons x (intersec-g (stream-cdr m1) m2 list1 list2))
                  (intersec-g (stream-cdr m1) m2 (cons x list1) list2)))))
         (intersec-g
          (lambda (m1 m2 list1 list2)
            (let ((x (stream-car m2)))
              (if (member x list2) 
                  (stream-cons x (intersec-f m1 (stream-cdr m2) list1 list2))
                  (intersec-f m1 (stream-cdr m2) list1 (cons x list2)))))))
      (intersec-f m1 m2 '()'()))))

(print-stream nat-stream 10)

(print-stream fibstream 10)

(print-stream (stream-intersection2 nat-stream fibstream) 5)

KA

Kreativaufgaben

Schnittmengen-Aufgabe

Suche