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>
=== Aufzählbarkeit und Entscheidbarkeit (Aufgabe 5) ===

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

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

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

<code id="4f7a9d2772c0a">
(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>

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