BuK/IIm10/BuK-Übung03 G1

Wiki-Quelltext dieser Seite.

=Beweis=
==Aufgabenstellung==
Zeigen Sie, dass <math>\wp(A^*)</math> für ein beliebiges Alphabet <math>A</math> eine überabzählbar unendliche Menge ist.

==Lösung==
Um nachzuweisen, dass eine Menge abzählbar unendlich ist, muss eine bijektive Abbildung auf die natürlichen Zahlen möglich sein.

Für die Wortmenge <math>A^*</math> wurde in der [[BuK/IIm10/BuK-Übung02 G1#Aufgabe 2| letzten Übung nachgewiesen]], dass eine Abbildung möglich ist, die Wortmenge <math>A^*</math> über einem Alphabet <math>A</math> also abzählbar unendlich ist.

Um nachzuweisen, dass <math>\wp(A^*)</math> abzählbar unendlich ist, müsste man also auch <math>\wp(A^*)</math> auf die natürlichen Zahlen abbilden können. Da diese Abbildung bei der Wortmenge <math>A^*</math> schon funktioniert hat, kann man auch eine Abbildung von <math>\wp(A^*)</math> auf <math>A^*</math> erzeugen um eine Abzählbarkeit nachzuweisen.

Bei <math>\wp(A^*)</math> handelt es sich jedoch um die Potenzmenge von <math>A^*</math>. Laut dem [http://de.wikipedia.org/wiki/Satz_von_Cantor Satz von Cantor] gilt für unendliche Mengen: <math>|X|<|\wp(X)|</math>.

(vgl.[http://de.wikipedia.org/wiki/Potenzmenge#Die_Gr.C3.B6.C3.9Fe_der_Potenzmenge_.28Kardinalit.C3.A4t.29 Die Größe der Potenzmenge (Kardinalität)])


Da also in der Wortmenge <math>A^*</math> weniger Elemente vorhanden sind als in der Potenzmenge <math>\wp(A^*)</math> ist keine bijektive Abbildung möglich.

=Entscheidbarkeit endlicher Mengen=

==Aufgabenstellung==
Implementieren Sie eine Scheme-Prozedur <math>chi-endlich</math>, die eine natürliche Zahl n und eine Liste L nimmt und entweder <math>\#t</math> oder <math>\#f</math> zurück gibt, je nachdem ob <math>n \in L</math> oder <math>n \notin L</math> gilt. Stellen Sie für den Entwurf von <math>chi-endlich</math> die erforderlichen Hilfsprozeduren bereit.

<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
==Lösung==
<code id="4d943895a932c">(define chi-endlich
  (lambda (n l)
    (if (null? l) 
        #f
        (if (= (car l) n)
            #t
            (chi-endlich n (cdr l))))))
</code>
<run id="4d943895a93a7">(chi-endlich 5 '(7 2 8 2 1 9 5))</run>
<run id="4d943895a9408">(chi-endlich 5 '(7 2 8 2 1 9 0))</run>

=Aufzählbarkeit=

<language>Scheme</language>
==Aufgabenstellung==
Schreiben Sie eine Scheme-Prozedur, die die Menge der Quadratzahlen aufzählt.

==Lösung==
<code id="4d91dff4f1eff" hidden>
;;; STREAMS - Implementation mit verzoegerter Evaluation (delay, force)
;;  als cons aus einem Kopfglied und einem verz�gerten Reststream

;; Selektoren

(define stream-car car)

(define stream-cdr
  (lambda (stm)
    (force (cdr stm))))


;; Konstruktoren

(define-syntax stream-cons
  (syntax-rules ()
    ((_ head tail) (cons head (delay tail)))))


;; Praedikat

(define stream?
  (lambda (stm)
    (and (pair? stm)(promise? (cdr stm)))))


;; Operationen mit streams

(define make-stream 
  (lambda (seed proc)
    (letrec 
      ((stream-builder
         (lambda (n)
           (stream-cons n (stream-builder (proc n))))))
      (stream-builder seed))))

(define *the-end-of-stream-tag*
  (make-stream
   "eos"
   (lambda (str) str)))
  
(define stream-item
  (lambda (str k)
    (if (= k 0)
      (stream-car str)
      (stream-item (stream-cdr str) (- k 1)))))

(define stream->list
  (lambda (str n)
    (if (<= n 0)
      '()
      (cons 
        (stream-car str) 
        (stream->list (stream-cdr str) (- n 1))))))

(define stream-map
  (lambda (f str)
    (stream-cons
     (f (stream-car str))
     (stream-map f (stream-cdr str)))))

(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 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+
  (lambda (stm1 stm2)
    (stream-cons
      (+ (stream-car stm1) (stream-car stm2))
      (stream+ (stream-cdr stm1) (stream-cdr stm2)))))


;;  Beispiele

(define nat-stream
  (lambda (start)
    (stream-cons start (nat-stream (+ start 1)))))

(define natzahlen (nat-stream 0))

(define random-stream
  (lambda ()
    (stream-cons (random 101) (random-stream))))

(define fib
    (lambda (n)
      (if (< n 2)
          1
          (+ (fib (- n 1)) (fib (- n 2))))))
(define fibstream (stream-map fib natzahlen))

</code>
<code id="4d91dff4f1f7b">
(define quadrat
  (lambda (n)
     (* n n)))

(define quadratstream (stream-map quadrat natzahlen))
</code>
<run id="4d91dff4f209a">
(print-stream quadratstream 20)
</run>

<language>Scheme</language>
=Semientscheidbarkeit=
==Aufgabenstellung==
Schreiben Sie eine Scheme-Prozedur, die die Menge der Quadratzahlen relativ zur Menge der natürlichen Zahlen semi-entscheidet.

Hinweis: Implementieren Sie eine Prozedur für die (allgemeingültige) <math>\chi'_{M}</math> und wenden Sie sie auf die Menge (stream) der natürlichen Zahlen an. Überlegen Sie sich vor dem Aufruf genau, welche Ausgabe Sie erwarten.




==Lösung==
<code id="4d943a5b666b3">
(define semi
  (lambda (n)
    (cond
      ((chi-endlich n (stream->list quadratstream (+ n 1)))#t)
      (else
       (semi n)))))
</code>
<run id="4d943abcb32f0">
(semi 5)
</run>
<code>
(define str (stream-map (lambda (x) (* x x)) natzahlen))

(define chi-strich
  (lambda (w)
    (letrec ((suche (lambda (menge)
    (if (= w (stream-car menge))
        #t
    (suche (stream-cdr menge))))))
    (suche str))))
</code>
<run>(chi-strich 25)</run>