BuK-Übung03 G2

Aus ProgrammingWiki

< BuK < IIm10

Archivierte Version vom 2011-03-31T07:47:53+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Aufzählbarkeit und Entscheidbarkeit

Aufzählbarkeit und Entscheidbarkeit

Aufgabe

Zeigen Sie, dass \wp(A^*) für ein beliebiges Alphabet A eine überabzählbar unendliche Menge ist.

Lösung

TODO

Aufgabe

Implementieren Sie eine Scheme-Prozedur chi-endlich, die eine natürliche Zahl n und eine Liste L nimmt und entweder #t oder #f zurückgibt, 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 n ls) 
  (cond
    [(null? ls) #f]
    [(= n (car ls)) #t]
    [else (chi-endlich n (cdr ls))]))

(chi-endlich 5 '(1 19 7 23 6 12))

(chi-endlich 5 '(1 19 7 23 5 6 12))

Aufgabe

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

Lösung

Man sagt f zählt M auf, wenn gilt:

M \subseteq A^*
f ist eine totale Funktion der Form f: N \mapsto M
f ist surjektiv und berechnbar und deren Wertebereich ist M = {f(0), f(1), \dots}

Dabei ist M die Menge der Quadratzahlen. Die Funktion f muss also eine surjektive Abbildung der natürlichen Zahlen N auf die Menge M vornehmen und berechenbar sein. Dazu benötigen wir die sogenannte Aufzählfunktion g für die Menge der Quadratzahlen.

(define g
  (lambda (n)
    (* n n)))

f(n) = \begin{cases}g(n), & \text{wenn } g(n) \in M \\4, & \text{sonst}\end{cases}

Die Menge M erzeugen wir mit Hilfe von Streams.

(define quad-stream (stream-map g natzahlen))

Damit können wir f wie folgt implementieren:

(define f
  (lambda (n)
    (if (chi-endlich (g n) (stream->list quad-stream (+ n 1)))
        (g n)
        4)))

(f 5)

(f 3.789)

Aufgabe

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

\chi^'_M

(define chi-strich
  (lambda (w m)
    (if (string=? w (stream-car m))
        #t
        (chi-strich w (stream-cdr m)))))

(define quad-stream2 
  (stream-map (lambda (i) (number->string i)) quad-stream))

(define natzahlen2
  (stream-map (lambda (i) (number->string i)) natzahlen))

(define quadRelZuNat
  (lambda (i)
    (if (chi-strich (number->string i) quad-stream2)
        #t
        (if (chi-strich (number->string i) natzahlen2)
            #f
            'fehler))))

(quadRelZuNat 4)

Vorsich: Der folgende Aufruf stoppt nicht!

(quadRelZuNat 5)

Um \text{quadRelZuNat} stoppen zu lassen verwenden wir weiter oben definierte Prozeduren.

(define quadRelZuNat2
  (lambda (i)
    (if (chi-endlich i (stream->list quad-stream (+ i 1)))
        #t
        (if (chi-strich (number->string i) natzahlen2)
            #f
            'fehler))))

(quadRelZuNat2 5)

BuK-Übung03 G2

Inhaltsverzeichnis

Aufzählbarkeit und Entscheidbarkeit

Aufgabe

Lösung

Aufgabe

Lösung

Aufgabe

Lösung

Aufgabe

Lösung

Suche