BuK/IIm11/Studenten/sistsche/Kreativaufgabe3

Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
Gegeben:
$ M_{1},M_{2} \subseteq A^{*} \text{ mit }
f: \N \rightarrow M_{1} \text{ und } g: \N \rightarrow  M_{2} $

Gesucht:

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

aufzählbare = abzählbar und berechenbar
Lösung:

(1) $ M_{1} \cap M_{2}  = \emptyset $
Bsp.:
$ M_{1} = \text{ungeraden Zahlen} $ \\
$ M_{2} = \text{geraden Zahlen} $ \\
$ M_{1} \cap M_{2}  = \emptyset \square $ 

(2)

Lösungsansatz: Konstruieren einer Semi-Entscheidbaren Methode die Wahr zurück gibt wenn $ w \in M_{1} \cap M_{2}$\\
Frage: Darf man eine Semi entscheidbare Funktion anstatt einer Aufzählprozedur benutzen???
Antwort: 

Wir konstruieren eine semi-entscheidbare Methode die Schritt für Schritt mithilfe der Aufzählungsfunktion $f(n)$ ein Element aus der aufzählbaren Menge $M$ erzeugt und mit den übergebenen $w$ vergleicht. Dabei liefert sie $wahr$ wenn $w = f(n)$ und ist sonst nicht definiert.

$$\chi M(w)=\begin{cases}
wahr, \text{ wenn } f(n) = w \text{ für alle } n \in \N \\
\perp, \text{ wenn } f(n) \neq w \text{ für alle } n \in \N
\end{cases}$$ 

Satz: Wenn $ M \subseteq \N$ aufzählbar ist, so ist M semi-entscheidbar.

Wie könnte die Methode aussehen??

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

Mithilfe der semi-entscheidbaren Funktion kann man nun überprüfen ob ein w in der Schnittmenge liegt

$$h(w)=\begin{cases}
wahr, \text{ wenn } w = g(i) \text{ und } w = f(j) \\
\perp, \text{sonst}
\end{cases}$$
BuK/IIm11/Studenten/sistsche/Kreativaufgabe3

Suche
