BuK/IIm12/Studenten/sidahorb/uebung3

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== Aufgabe 1 ==
Wie viele berechenbare charakteristische Funktionen gibt es?

Lösung:

Die Wortmenge $A^*$ ist abzählbar unendlich. Für jede Teilmenge M (entspricht einem Wort) gibt es eine charakteristische Funktion (chi) die $true$ oder $false$ zurückgibt. Von der Wortmenge $A^*$ wird nun die Potenzmenge $P(A^*)$ erzeugt, welche überabzählbar unendlich ist. Für Jedes Element von $P$ kann man nun ebenfalls eine eine Funktion chi erzeugen, was dazu führt das es ebenfalls überabzähbar unendlich viele Funktionen chi gibt, trotzdem nicht jede dieser Funktionen berechenbar ist.


<language>Scheme</language>
== Aufgabe 2 == 
Zeigen Sie, dass die beiden folgenden Mengen entscheidbar sind. Schreiben Sie je eine entsprechende Prozedur für die jeweilige charakteristische Funktion

'''Beispiel 1:'''

M ist die Menge aller Wörter aus $A^*$, die die Länge 3 besitzen, d.h.:

$A^* = \{a, b\}^* \text{ und } M \subset A^* = \{w \mid w \in A^*\text{ und } |w| = 3\}$

Lösung:

Mengen sind (absolut) entscheidbar, wenn es eine charakteristische Funktion gibt, die "wahr" zurückgibt, wenn das Element in der Menge enthalten ist und "falsch", wenn es nicht enthalten ist. Da es sich um eine endliche Menge handelt, kann eine Iteration über die Elemente der Menge erfolgen, wobei das jeweilige Element mit dem gesuchten verglichen wird. Bei Übereinstimmung wird "true" zurückgegeben, sonst "false".

<code id="516bfaf7354e4">
(define 
    Liste (list 'aaa 'aab 'aba 'abb 'baa 'bab 'bba 'bbb))

(define inList
    (lambda (wrd lst)
        (cond
            [(eq? (car lst) wrd) #t]
            [(not (null? (cdr lst))) (inList wrd (cdr lst))]
            [else #f]))
)
</code>
<run id="516bfaf73560c">(inList 'aaa Liste)</run>


'''Beispiel 2''' abzählbar unendliche Menge

$ M $ ist die Menge aller Wörter, die aus beliebeig vielen $ a $'s und $ b $'s bestehen und mit $ a $ beginnen: $ A^* = \{a,b\}^* $ und $ M \subset A^* = \{w = aw' | w' \in A^* \} $ .

Lösung:

Hier muss lediglich überprüft werden, ob das Eingabewort mit einem "a" beginnt. 

<code id="516bfaf73556d">
(define istWortInAlphabet
    (lambda (wrd)
        (cond
            [(string=? (string (car (string->list wrd))) "a") #t]
            [else #f])))
</code>
<run id="516bfaf73568d">(istWortInAlphabet "aaabb")</run>

== Aufgabe 3 ==
Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.

Lösung:

Aufzählbar = abzählbar + berechenbar

<u>abzählbar:</u> Für die Menge der geraden Zahlen $G$ gilt: $G\subset\Z$, $\Z$ ist abzählbar unendlich[[BuK/IIm12/Studenten/sifedeut/uebung2#Aufgabe_2_.28Deutschmann.2C_Horbach.29 | Beweis]]

<u>berechenbar:</u> Es existiert ein Algorithmus, der für die Funktion $f(x)$ für jedes $x \in D_f$ den zugehörigen Funktionswert $f(x)$ ermittelt


$f(x)=\begin{cases}-i & \text{, wenn i gerade}\\i+1 & \text{, wenn i ungerade}\end{cases}$


<code id="516bfbca98eb3">
(define gibGeradeZahl
    (lambda (x)
        (cond
            [(= (modulo x 2) 0) (* -1 x)]
            [else (+ x 1)])))
</code>
<run id="516bfbca98f66">(gibGeradeZahl 4)</run>

<language>Scheme</language>
<code id="516c613471494" hidden>
(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)))))
  
(define stream-item
  (lambda (str k)
    (if (= k 0)
      (stream-car str)
      (stream-item (stream-cdr str) (- k 1)))))


(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 nat-stream-maker
  (lambda ()
      (letrec ((n 0)
            (nat-stream-maker-helper   
             (lambda (start)
               (stream-cons start (nat-stream-maker-helper (+ start 1))))))
        (nat-stream-maker-helper 0))))

(define natstream (nat-stream-maker ))
</code>


== Aufgabe 4 ==
Zeigen Sie, dass die Menge der Primzahlen P aufzählbar ist.

Lösung:

aufzählbar = abzählbar + berechenbar

Primzahlen sind abzählbar unendlich [[BuK/IIm12/Studenten/sifedeut/uebung2#Aufgabe_2_.28Deutschmann.2C_Horbach.29|Beweis]].

Primzahlen sind berechenbar, da eine Prozedur dafür angegeben werden kann. 

Algorithmus:

<code id="516bfdd965f03">
(define kleinster−teiler
  (lambda (n) 
    ;finde a, sodass gilt: a^n mod n = a
    (finde−teiler 2 n)
  )
)
(define finde−teiler
  (lambda (a n)
    ;teile n durch a, wobei 2 < a < sqrt(n)
    (cond ((> (sqrt a) n) n)
          ((teilt? a n) a)
          (else (finde−teiler (+ a 1) n))
    )
  )
)
(define teilt?
  (lambda (a b)
    (= (modulo b a) 0 )
  )
)
(define prime?
  (lambda (n)
    (= (kleinster−teiler n) n)
  )
)


(define f
    (lambda (x) 
        (cond 
            [(prime? x) x]
            [else 2])))


(define primeStream (stream-map natstream f))
</code>
<run id="516c613471650">(print-stream primeStream 30)</run>

== Aufgabe 5 ==
Wir wissen, dass A* eine abzählbar unendliche Menge ist. Zeigen Sie, dass A* auch aufzählbar ist. Hinweis: Hierzu ist es notwendig ein Aufbauschema für A* zu entwerfen und anschließend eine Prozedur dafür zu implementieren.

Lösung:

aufzählbar = abzählbar + berechenbar

Da wir wissen das A* abzählbar unendlich ist, muss nur noch eine Prozedur angegeben werden.

OFFEN

== Aufgabe 6 ==
Zeigen Sie, dass jede endliche Menge $M$ aufzählbar ist.

Lösung:

Aufzählbar = abzählbar + berechenbar

Laut Definition heißt eine Menge $M$ endlich, wenn es eine natürliche Zahl $n$ gibt, sodass eine Bijektion zwischen $M$ und der Menge aller natürlichen Zahlen kleiner als $n$ existiert, d.h. jede endliche Menge ist abzählbar.

Eine Menge $M$ heißt (rekursiv) aufzählbar wenn es entweder eine total berechenbare surjektive Funktion $f:N \mapsto M$ gibt, oder es gilt $M = \emptyset$. Man nennt $f$ eine Aufzählprozedur oder ein Aufzählverfahren von M.

Es gibt eine Funktion $f$, die als Eingabe die natürlichen Zahlen $\N$ nimmt und auf jedes Element der endlichen Menge $M$ abbildet. $f$ ist berechenbar, da es eine total berechenbare surjektive Funktion $f : \N \mapsto M$ gibt. Es wird der Reihe nach jedes Element aus $\N$ einem Element aus $M$ zugeordnet. Ist $f$ surjektiv, können die restlichen Elemente aus $\N$ auf ein beliebiges Element von $M$ abgebildet werden. Somit ist $f$ surjektiv, total und berechenbar.

== Aufgabe 7 ==
Die Menge G der Gitterpunkte (0, 0),(0, 1), ... einer x-y-Ebene ist aufzählbar.

1. Geben Sie eine Funktion f an, die $\N_0$ bijektiv auf G abbildet.

Lösung:

$f(x) = (x,y)$ mit $x = \ldots$ und $y = \ldots$

2. Definieren Sie eine Ordnungsrelation $p_<$ in G.

Lösung:

3. Geben Sie eine Funktion k zur Berechnung der Platznummer k(x, y) des betrachteten Gitterpunktes (x, y) an.

Lösung:

4. Geben Sie eine Aufzählprozedur für G an und begründen Sie deren Berechenbarkeit.

Lösung:

== Aufgabe 8 ==
Das Halteproblem ist semi-entscheidbar. Beweisen Sie diese Aussage.

Lösung:

== Aufgabe 9 ==
Geben Sie fur die Menge FIBS der Fibonacci-Zahlwörter eine Aufzählfunktion an und begründen Sie deren Berechenbarkeit.
Weisen Sie nach, dass FIBS eine semi-entscheidbare Menge ist. Zeigen Sie, dass FIBS sogar entscheidbar ist.

Lösung:

== Aufgabe 10 ==
Übertragen Sie die vorhergehende Übungsaufgabe sinngemäß auf die Menge der Quadratzahlen $QZ = \{n^2 |n \in \N\}.$

Lösung:

== Aufgabe 11 ==
Weisen Sie nach, dass die Menge $M$ aller "Wörter" aus $\{a,b\}^*$, die mit a beginnen, semi-entscheidbar ist.

Lösung:

== Aufgabe 12 ==
Definieren Sie die Menge der geraden Zahlen (Zahlwörter) und die der ungeraden Zahlen (Zahlwörter) und veranlassen Sie das ProgrammingWiki die 30 ersten Elemente der Vereinigungsmenge (in aufsteigender Sortierung) auszugeben.

Lösung: