BuK-Übung03 G1

Aus ProgrammingWiki

Inhaltsverzeichnis

1 Beweis
- 1.1 Aufgabenstellung
- 1.2 Lösung
2 Entscheidbarkeit endlicher Mengen
- 2.1 Aufgabenstellung
- 2.2 Lösung
3 Aufzählbarkeit
- 3.1 Aufgabenstellung
- 3.2 Lösung
4 Semientscheidbarkeit
- 4.1 Aufgabenstellung
- 4.2 Lösung

Beweis

Aufgabenstellung

Zeigen Sie, dass \wp(A^*) für ein beliebiges Alphabet A 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 A^* wurde in der letzten Übung nachgewiesen, dass eine Abbildung möglich ist, die Wortmenge A^* über einem Alphabet A also abzählbar unendlich ist.

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

Bei \wp(A^*) handelt es sich jedoch um die Potenzmenge von A^*. Laut dem Satz von Cantor gilt für unendliche Mengen: |X|<|\wp(X)|.

(vgl.Die Größe der Potenzmenge (Kardinalität))

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

Entscheidbarkeit endlicher Mengen

Aufgabenstellung

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

Lösung

(define chi-endlich
  (lambda (n l)
    (if (null? l) 
        #f
        (if (= (car l) n)
            #t
            (chi-endlich n (cdr l))))))

(chi-endlich 5 '(7 2 8 2 1 9 5))

(chi-endlich 5 '(7 2 8 2 1 9 0))

Aufzählbarkeit

Aufgabenstellung

Schreiben Sie eine Scheme-Prozedur, die die Menge der Quadratzahlen aufzählt.

Lösung

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

(define quadrat
  (lambda (n)
     (* n n)))

(define quadratstream (stream-map quadrat natzahlen))

(print-stream quadratstream 20)

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) \chi'_{M} 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

(define semi
  (lambda (n)
    (cond
      ((chi-endlich n (stream->list quadratstream (+ n 1)))#t)
      (else
       (semi n)))))

(semi 5)

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

(chi-strich 25)

BuK-Übung03 G1

Inhaltsverzeichnis

Beweis

Aufgabenstellung

Lösung

Entscheidbarkeit endlicher Mengen

Aufgabenstellung

Lösung

Aufzählbarkeit

Aufgabenstellung

Lösung

Semientscheidbarkeit

Aufgabenstellung

Lösung

Suche