BuK-Übung03

Aus ProgrammingWiki

Archivierte Version vom 2012-04-03T19:22:24+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Aufgabe 1 (Felix Nitsche, Stefan Lüttke)
2 Aufgabe 2 (Jens Heider, Daniel Tasche)
3 Aufgabe 3 (Max Wielsch, Raik Bieniek)
4 Aufgabe 4 (Ingo Körner, Christof Ochmann)
5 Aufgabe 5 (Tobias Salzmann, Ronald Krause)
6 Aufgabe 6 (Robert Rosenberger, Stefan Scheumann)

Aufgabe 1 `(Felix Nitsche, Stefan Lüttke)`

ÜA: Wie viele berechenbare charakteristische Funktionen gibt es? Hinweis: Potenzmenge unendlicher Mengen

Aufgabe 2 `(Jens Heider, Daniel Tasche)`

ÜA: Zeigen Sie, dass die beiden Mengen aus den Beispielen entscheidbar sind. Schreiben Sie je eine entsprechende Prozedur für die jeweilige charakteristische Funktion (ProgrammingWiki).

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:

Die 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 definitiv 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 "wahr" zurückgegeben. Wird die Iteration erfolglos beendet, wird "falsch" zurückgegeben.

\chi_M(w) = \begin{cases} wahr, & \text{wenn } w \in M;\\ falsch, & \text{sonst} \end{cases}

(define M (list "aaa" "aba" "aab" "baa" "bab" "abb" "bba" "bbb"))
(define chi
  (lambda (w)
    (letrec
      ((suche
        (lambda (menge)
          (cond
            [(null? menge) #f]
            [(string=? (car menge) w) #t]
            [else 
              (suche (cdr menge))
            ]
          )
        )
      ))
      (suche M)
    )
  )
)

(chi "aab")

Eine alternatie Möglichkeit besteht in der Überprüfung, ob das Wort den Regeln entspricht (Wortlänge von 3, Alphabet enthält nur 'a' und 'b'):

(define chi2
  (lambda (w)
    (letrec
      ((suche
        (lambda (liste index)
          (cond
            [(and (null? liste) (<= index 3)) #f]
            [(null? liste) #t]
            [(> index 3) #f]
            [(not (or (char=? #\a (car liste)) (char=? #\b (car liste)))) #f]
            [else 
              (suche (cdr liste) (+ index 1))
            ]
          )
        )
      ))
      (suche (string->list w) 1)
    )
  )
)

(chi2 "aaaa")

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

Die Menge M ist entscheidbar, da folgende charakteristische Funktion existiert:

\chi_M(w) = \begin{cases} wahr, & \text{wenn das erste Zeichen von } w \text{ ein '}a\text{' ist und } w \in A^*\text{, mit } A^* = \{a,b\}^*;\\ falsch, & \text{sonst}; \end{cases}

Die Funktion liefert wahr, wenn das erste Zeichen des Wortes w ein 'a' ist und der Rest des Wortes aus dem Alphabet A^* ist. Falsch, wenn nicht.

(define b2
  (lambda (w)
    (let ((l (string->list w)))
      (letrec 
           ((helper
             (lambda (a)
               (if (or (char=? #\a (car a)) (char=? #\b (car a)))
                 (if (not (null? (cdr a)))
                     (helper (cdr a))
                     #t
                  )
                 #f
               )
             )
           ))
        (if (and (not (null? l)) (char=? #\a (car l)))
         (helper (cdr l))
         #f
        )
      )
    )
  )
)

(b2 "ababbababab")

Aufgabe 3 `(Max Wielsch, Raik Bieniek)`

TODO Scheme Funktionen für die ersten beiden Teilaufgaben von Max rüberkopieren

ÜA: Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.

Gesucht: f: ℕ ↦ G; berechenbar, surjektiv

$f(x) = \left\{\begin{array}{cc} x; wenn\ 2|x\\ (-1) \cdot x + 1; sonst\\ \end{array}\right. $

\square

Algorithmus:

(define g
  (lambda (n)
    (if (= (modulo n 2) 0)
      n
      (* (+ n 1) -1)
    )
  )
)

(g 1)

ÜA: Zeigen Sie, dass die Menge der Primzahlen P aufzählbar ist

Gesucht: f: ℕ ↦ P; berechenbar, surjektiv

$f(x) = \left\{\begin{array}{cc} x; wenn\ prime?(x)\\ 2; sonst\\ \end{array}\right. $

Existiert ein Algorithmus für f? wenn/sonst durch if/else implementierbar prime? Funktion existiert (siehe Folien)

\square

↦ f ist berechenbar

ÜA: 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.

Gesucht: f: ℕ ↦ A^*; berechenbar, surjektiv

Für endliches Alphabet:

Bsp:

(als SVG)

(define pow
  (lambda (number exp)
    (if (= exp 0)
      1
      (* number (pow number (- exp 1))))))

(define getElement
  (lambda (set index)
    (if (= index 1)
      (car set)
      (getElement (cdr set) (- index 1)))))
      
(define cardinalNumber
  (lambda (set)
    (if (null? set)
      0
      (+ 1 (cardinalNumber (cdr set))))))


      
(define calculateWordSize
  (lambda (set index)
    (letrec ((calculateWordSizeReal
      (lambda (cardinalNumber index sum exp)
        (if (>= sum index)
          0
          (+ 1 
            (calculateWordSizeReal
              cardinalNumber
              index
              (+ sum (pow cardinalNumber exp))
              (+ 1 exp)))))))
  (calculateWordSizeReal (cardinalNumber set) index 0 1))))

;Berechnet die Anzahl der Wörter mit Länge <= letterCount
(define numberOfWords
  (lambda (cardinalNumber letterCount)
    (if (= letterCount 0)
      0
      (+
        (pow cardinalNumber letterCount)
        (numberOfWords cardinalNumber (- letterCount 1))))))
    
(define createWord
  (lambda (set wordnumber cardinalNumber lettersRemaining)
    (if (= 0 lettersRemaining)
      ""
      (let ((sectionSize (pow cardinalNumber (- lettersRemaining 1))))
        (let ((rest (modulo wordnumber sectionSize))
            (result (quotient wordnumber sectionSize)))
          (if (= 0 rest)
            (string-append
              (string (getElement set result))
              (createWord set sectionSize cardinalNumber (- lettersRemaining 1)))
            (string-append
              (string (getElement set (+ result 1)))
              (createWord set rest cardinalNumber (- lettersRemaining 1)))))))))
                
(define f
  (lambda (set index)
    (if (= index 0)
      ""
      (let((cardinalNumber (cardinalNumber testSet))
          (lettersRemaining (calculateWordSize testSet index)))
        (createWord testSet (- index (numberOfWords cardinalNumber (- lettersRemaining 1))) cardinalNumber lettersRemaining)))))

(define testSet
  '(#\a #\b #\c))

(f testSet 30)

Aufgabe 4 `(Ingo Körner, Christof Ochmann)`

ÜA: Zeigen Sie, dass jede endliche Menge aufzählbar ist.

ÜA: 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.

2 Definieren Sie eine Ordnungsrelation p_< in G.

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

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

Aufgabe 5 `(Tobias Salzmann, Ronald Krause)`

Übersicht: Mengenklassen

Eine Menge M \subseteq A^* ist semi-entscheidbar, wenn die partielle (semi-charakteristische) Funktion \chi'_M : A^* \mapsto \{wahr\} mit

\chi'_M(w) = \begin{cases} wahr, & \text{wenn } w \in M;\\ \bot, & sonst. \end{cases}

berechenbar ist.

ÜA: Das Halteproblem ist semi-entscheidbar. Beweisen Sie diese Aussage.

Man kann eine Prozedur haelt? angeben, welche angewand auf eine Prozedur f true zurück gibt falls f terminiert und ansosnten ewig weiter läuft, für diesen Fall also nicht definiert ist.
Das Halteproblem ist somit semi-entscheidbar, weil eine partielle Funktion hierfür angegeben werden kann.

(define (haelt? f n)
  (f n) #t)

(define eternity
  (lambda (n) 
    (eternity n)))

(define (square n)
  (* n n))

(haelt? square 4)

(haelt? eternity 4)

ÜA: Weisen Sie nach, dass die Menge M aller "Wörter aus {a, b}*, die mit a beginnen, semi-entscheidbar ist.

Wie in der Übersicht zu den Mengenklassen ersichtlich, ist eine Menge auch semi-entscheidbar, wenn Sie entscheidbar ist.
In Aufgabe 2 wurde die Entscheidbarkeit dieser Menge gezeigt, daraus folgt das Sie auch semi-entscheidbar sein muss.

Weiterhin kann auch eine partielle semi-charakteristische Funktion angegeben werden:

(define chi-a
  (lambda (w)
    (if (char=? (string-ref w 0) #\a)
    #t
    (chi-a w))))

(chi-a "abbbbaaabbbb")

(chi-a "babbbaaabbbb")

ÜA: 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.

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

Aufgabe 6 `(Robert Rosenberger, Stefan Scheumann)`

ÜA: 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.

BuK-Übung03

Inhaltsverzeichnis

Aufgabe 1 (Felix Nitsche, Stefan Lüttke)

Aufgabe 2 (Jens Heider, Daniel Tasche)

Aufgabe 3 (Max Wielsch, Raik Bieniek)

Aufgabe 4 (Ingo Körner, Christof Ochmann)

Aufgabe 5 (Tobias Salzmann, Ronald Krause)

Aufgabe 6 (Robert Rosenberger, Stefan Scheumann)

Suche

Aufgabe 1 `(Felix Nitsche, Stefan Lüttke)`

Aufgabe 2 `(Jens Heider, Daniel Tasche)`

Aufgabe 3 `(Max Wielsch, Raik Bieniek)`

Aufgabe 4 `(Ingo Körner, Christof Ochmann)`

Aufgabe 5 `(Tobias Salzmann, Ronald Krause)`

Aufgabe 6 `(Robert Rosenberger, Stefan Scheumann)`