BuK/IIm11/BuK-Übung03

Wiki-Quelltext dieser Seite.

==== Aufgabe 1 <tt>(Felix Nitsche, Stefan Lüttke)</tt> ====
ÜA: Wie viele berechenbare charakteristische Funktionen gibt es?
Hinweis: Potenzmenge unendlicher Mengen


==== Aufgabe 2 <tt>(Jens Heider, Daniel Tasche)</tt> ====
Ü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).


<language>Scheme</language>
==== Aufgabe 3 <tt>(Max Wielsch, Raik Bieniek)</tt> ====

'''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.
$
<div align="right">$\square$</div>

Ü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)
<div align="right">$\square$</div>

↦ 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:

[[Bild:Sirabien_A_oben_Stern.png]]

([http://www.inf.hs-zigr.de/~sirabien/A_oben_Stern.svg als SVG])

<code id="4f7b4499759eb">
(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)))))
</code>

<run id="4f7b449975a61">
(define testSet
  '(#\a #\b #\c))

(f testSet 30)
</run>

==== Aufgabe 4 <tt>(Ingo Körner, Christof Ochmann)</tt> ====
Ü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 <tt>(Tobias Salzmann, Ronald Krause)</tt> ====
ÜA: Das Halteproblem ist semi-entscheidbar. Beweisen Sie diese
Aussage.

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

Ü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 <tt>(Robert Rosenberger, Stefan Scheumann)</tt> ====
Ü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.