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

Implementierung der Funktion '''f''':

<code>
(define f
  (lambda (n)
    (if ((g n) (fib_menge fibonacci_zahlen n))
        (g n)
        4)))
</code>

<run>
(f 10)
</run>
ÜA: Übertragen Sie die vorhergehende Übungsaufgabe sinngemäß auf die Menge der Quadratzahlen $QZ = \{n^2 |n \in \N\}.$