BuK/IIm11/Studenten/sirokrau

Wiki-Quelltext dieser Seite.

== Übung 2 ==

=== Aufgabe 1 ===

$$ \sum\limits_{k=1}^{n} F_{k} =  F_{n+2} - 1$$

Induktionsanfang (IA):

z.z. Für n = 1 gilt:

$F_{1}$ = $F_{1+2}-1$

$F_{1}$ = $F_{3}-1$ ($F_{3}$ = 2)

1 = 2-1

1 = 1 $\Rightarrow$ OK

Induktionsschritt (IS):

Wenn $ \sum\limits_{k=1}^{i} F_{k} =  F_{i+2} - 1$ (Induktionsvoraussetzung, kurz IV),

dann gilt auch: $ \sum\limits_{k=1}^{i+1} F_{k} =  F_{i+3} - 1$ (Induktionsbehauptung, kurz IB).

$ \sum\limits_{k=1}^{i+1} F_{k} =  \sum\limits_{k=1}^{i} F_{k} + F_{i+1}$ $\quad \stackrel{IV}{=}$ $ F_{i+2} -1 +  F_{i+1}$ $ = F_{i+3} - 1$ (Ergebnis = IB)

<div align="right">$\square $</div>

== Übung 3 ==

<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
=== Aufzählbarkeit und Entscheidbarkeit (Aufgabe 5) ===

<code hidden>
(define stream-car car)

(define stream-cdr
  (lambda (s)
    (force (cdr s))))

(define-syntax stream-cons
  (syntax-rules ()
    ((_ head tail) (cons head (delay tail)))))

(define stream-map
  (lambda (f s)
    (stream-cons
     (f (stream-car s))
     (stream-map f (stream-cdr s)))))

(define nat-stream
  (lambda (start)
    (stream-cons start (nat-stream (+ start 1)))))

(define stream->list
  (lambda (str n)
    (if (<= n 0)
      '()
      (cons 
        (stream-car str) 
        (stream->list (stream-cdr str) (- n 1))))))

(define print-stream
  (lambda (str items)
    (if (<= items 0)
        (begin
          (display "...")(newline))
        (begin
          (write (stream-car str))
          (display ", ")
          (print-stream (stream-cdr str)(- items 1))))))

(define natzahlen (nat-stream 0))

(define fib_menge print-stream)  ; angepasster Prozedurnamen

(define generiere_fib_menge 
  (lambda (f)
    (stream-map number->string (stream-map f natzahlen))))
</code>


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

Laut der Definition aus der Vorlesung Berechenbarkeitstheorie und Kreativität ist eine Menge aufzählbar, wenn es eine totale berechenbare Funktion '''f''' gibt, welche die Menge $\N$ auf eine Menge '''M''' abbildet.

In diesem Beispiel handelt es sich bei der Menge '''M''' um die Fibonacci-Zahlwörter. Die Aufzählprozedur '''f''' lautet wie folgt:

$$f(n) = \begin{cases}
g(n), & \text{wenn } g(n) \in \text{ M};\\
0, & sonst.
\end{cases}$$

Damit die Funktion '''f''' eine surjektiv Abbildung der natürlichen Zahlen auf die Menge der Fibonacci-Zahlwörter und berechenbar ist, wird die Aufzählfunktion '''g''' benötigt.

$$g(n) = \begin{cases}
0, & \text{wenn } n=0;\\
1, & \text{wenn } n=1;\\
(n-1) + (n-2), & sonst.
\end{cases}$$

Scheme-Prozedur für die Aufzählfunktion '''g''':

<code id="4f7a9eb44d422">
(define g
  (lambda (n)
    (cond
      ((= n 0) 0)
      ((= n 1) 1)
      (else (+ (g(- n 1)) (g(- n 2)))))))
</code>

<run id="4f7a9ddac7082">
(g 10)
</run>

Erzeugen der Menge M an Fibonacci-Zahlwörter:

<code>
(define fibonacci_zahlen (generiere_fib_menge g))
</code>

<run>
(fib_menge fibonacci_zahlen 5)
</run>

Um nachweisen zu können, dass die Funktion '''f''' semi-entscheidbar ist, muss es wie oben definiert folgende Funktion geben

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

welche berechenbar ist. Mit Hilfe der Prozedur '''semi_chi_fib''' ist dies nachweisbar.

<code>
(define semi_chi_fib
  (lambda (m w)
    (letrec
        (( helfer
           ( lambda ( stm )
              (if (string=? w (stream-car stm ))
                  #t
                  (helfer (stream-cdr stm ))))))
      (helfer m ))))
</code>

<run>
(semi_chi_fib fibonacci_zahlen "5")
</run>

<run>
(semi_chi_fib fibonacci_zahlen "-1") ;user break
</run>

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

Analog zur vorhergehenden Übungsaufgabe lässt sich folgende Aufzählprozedur '''f''' aufstellen:

$$f(n) = \begin{cases}
g(n), & \text{wenn } g(n) \in \text{ M};\\
0, & sonst.
\end{cases}$$

Die Auzählfunktion g2, welche die Menge der quadtratischen Zahlen zurückgibt ist folgende:

<code>
(define g2
 (lambda (n)
  (* n n)))
</code>

Erzeugen der Menge M an Quadratzahlen:

<code hidden>
(define quad_menge print-stream) 

(define generiere_quad_menge
  (lambda (f)
    (stream-map f natzahlen)))

</code>

<code>
(define quad_zahlen (generiere_quad_menge g2))
</code>

<run>
(quad_menge quad_zahlen 9)
</run>

Nachweis das die Funktion '''f''' semi-entscheidbar ist: Prozedur '''semi_chi_quad'''

<code hidden>
(define generiere_quad_menge_wortmenge
  (lambda (f)
    (stream-map number->string (stream-map f natzahlen))))

(define quad_zahlen_woerter (generiere_quad_menge_wortmenge g2))
</code>

<code>
(define semi_chi_quad
  (lambda (m w)
    (letrec
        (( helfer
           ( lambda ( stm )
              (if (string=? w (stream-car stm ))
                  #t
                  (helfer (stream-cdr stm ))))))
      (helfer m ))))
</code>

<run>
(semi_chi_quad quad_zahlen 9)
</run>

<run>
(semi_chi_quad quad_zahlen 3); user break
</run>

Nachweis das die Funktion ebenfalls entscheidbar ist:

<code>
(define f_help
  (lambda (n ls) 
    (cond
    ((null? ls) #f)
    ((= n (car ls)) #t)
    (else (f_help n (cdr ls))))))
  
(define f
  (lambda (n)
    (if (f_help (g2 n) (stream->list quad_zahlen (+ n 1)))
        (g2 n)
        0)))
</code>

<run>
(f 10)
</run>

<run>
(f 10.1)
</run>