BuK/IIm11/Studenten/sirokrau
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
== Ü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 ==
=== Aufzählbarkeit und Entscheidbarkeit (Aufgabe 5) ===
<code id="4f8d655165fb0" 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 id="4f8d655166053">
(define fibonacci_zahlen (generiere_fib_menge g))
</code>
<run id="4f8d6551667c7">
(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 id="4f8d6551660dc">
(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 id="4f8d655166858">
(semi_chi_fib fibonacci_zahlen "5")
</run>
<run id="4f8d6551668d9">
(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};\\
1, & sonst.
\end{cases}$$
Die Auzählfunktion g2, welche die Menge der quadtratischen Zahlen zurückgibt ist folgende:
<code id="4f8d65516618e">
(define g2
(lambda (n)
(* n n)))
</code>
Erzeugen der Menge M an Quadratzahlen:
<code id="4f8d655166243" hidden>
(define quad_menge print-stream)
(define generiere_quad_menge
(lambda (f)
(stream-map f natzahlen)))
</code>
<code id="4f8d6551662e7">
(define quad_zahlen (generiere_quad_menge g2))
</code>
<run id="4f8d65516696e">
(quad_menge quad_zahlen 9)
</run>
Nachweis das die Funktion '''f''' semi-entscheidbar ist: Prozedur '''semi_chi_quad'''
<code id="4f8d655166369" hidden>
(define generiere_quad_menge_wortmenge
(lambda (f)
(stream-map number->string (stream-map f natzahlen))))
(define quad_zahlen_2 (generiere_quad_menge_wortmenge g2))
</code>
<code id="4f8d6551663ef">
(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 id="4f8d6551669f6">
(semi_chi_quad quad_zahlen_2 "9")
</run>
<run id="4f8d655166a76">
(semi_chi_quad quad_zahlen_2 "3"); user break
</run>
Nachweis das die Funktion ebenfalls entscheidbar ist:
<code id="4f8d655166477" hidden>
(define f_help
(lambda (n ls)
(cond
((null? ls) #f)
((= n (car ls)) #t)
(else (f_help n (cdr ls))))))
</code>
<code id="4f8d655166503">
(define f
(lambda (n)
(if (f_help (g2 n) (stream->list quad_zahlen (+ n 1)))
(g2 n)
1)))
</code>
<run id="4f8d655166b1d">
(f 10)
</run>
<run id="4f8d655166bdc">
(f 10.1)
</run>
== Übung 4 ==
=== Teilaufgabe 2 - Beweis Teil 2 <tt>(Tobias Salzmann, Ronald Krause)</tt> ===
[[Bild:Sitosalz_Entscheidbarkeit_aufzaehlbarkeit.png| miniatur | Abbildung]]
zu zeigen: Wenn M und $A^*$\M aufzählbare Mengen sind, dann ist M eine entscheidbare Menge.
Da M und $A^*$\M aufzählbare Mengen sind, gibt es total berechenbare surjektive Funktionen für diese.
Für M lautet die Auzählfunktion $f: \N \mapsto M$:
$$f(n) = \begin{cases}
f(n), & \text{wenn } f(n) \in M;\\
a, & sonst
\end{cases}$$
'''Hinweis:''' $a \in M$ .
Für $A^*$\M lautet die Auzählfunktion $g: \N \mapsto A^*$\M:
$$g(n) = \begin{cases}
g(n), & \text{wenn } g(n) \in A^*\text{ \M};\\
b, & sonst
\end{cases}$$
'''Hinweis:''' $b \in A^*$\M .
==== Beweis ====
Da zu zeigen ist, dass M entscheidbar sein soll, muss es eine total berechenbare Funktion $\chi_M$ geben.
$$\chi_M(w) = \begin{cases}
wahr, & \text{wenn } w \in M;\\
falsch, & \text{wenn } w \in A^*\text{ \ M}
\end{cases}$$
Es muss also eine Prozedur ''chi'' geben, welche für jedes Wort $w$ in endlicher Zeit für ein $i$ mit w = f(i) oder w = g(i) findet.
Da die Schnittmenge von M und $A^*$\M eine leere Menge ist, kann es kein ''w'' geben, welches in beiden Mengen vorkommt, sodass man genau sagen kann, ob w in der Menge M oder der Menge $A^*$\ M liegt.
$$M \cap (A^*\text{ \ M}) = \empty,\text{ gilt} f(i) = g(j) = w \text{ ausgeschlossen}$$
Da das Wort w aus der Wortmenge $A^*$ stammt und die Vereinigung der beiden Mengen die Wortmenge ist, muss das Wort in diesen beiden Mengen liegen. Um die Abzählbarkeit zu gewährleisten, wird abwechseln das $i$-te-Element aus $f$ und $g$ gesucht, sodass kein Wort vergessen wird.
$$\chi_M(w) = \begin{cases}
wahr, & \text{wenn } f(i) = w;\\
falsch, & \text{wenn } g(i) = w
\end{cases}$$
== RAM-Programm: <tt>(Tobias Salzmann und Ronald Krause)</tt> ==
<code>
introot(a):=
Module({x = a, y = 1},
WHILE( x > y)
x = Quotient(x + y, 2);
y = Quotient(a, x);
return x;
)
</code>
<br />
{|| border="1" cellpadding="5" cellspacing="0"
!Befehlszähler
!Befehl
!Bemerkung
|-
||<div align="right">1</div>||R0 = n||Berechnung Wurzel 25
|-
||<div align="right">2</div>||R1 = RO||X
|-
||<div align="right">3</div>||R2 = 1||Y
|-
||<div align="right">4</div>||R20 = R1||
|-
||<div align="right">5</div>||R21 = R2||
|-
||<div align="right">6</div>||GOTO 36|| Größer/KleinerVergleich
|-
||<div align="right">7</div>||IFZERO R23 GOTO 9||
|-
||<div align="right">8</div>||STOP||Ergebnis x in R1
|-
||<div align="right">9</div>||R3 = 0||
|-
||<div align="right">10</div>||R3 += R1|| 0 + x
|-
||<div align="right">11</div>||R3 += R2|| x + y
|-
||<div align="right">12</div>||R4 = 2||
|-
||<div align="right">13</div>||R10 = 0|| Wert zur Überprüfen des Rücksprunges
|-
||<div align="right">14</div>||GOTO 22|| Division
|-
||<div align="right">15</div>||R1 = R5|| neues x in R1
|-
||<div align="right">16</div>||R3 = R0|| n in R3
|-
||<div align="right">17</div>||R4 = R1|| x in R4
|-
||<div align="right">18</div>||R10 = 1|| Wert zur Überprüfung des Rücksprunges
|-
||<div align="right">19</div>||GOTO 22|| Division
|-
||<div align="right">20</div>||R2 = R5|| neues y in R2
|-
||<div align="right">21</div>||GOTO 36|| Größer/Kleinervergleich
|}
<br/>
=== Ganzzahlige Division ===
<code>
q = 0;
r = a;
while (r>=b)
{
q = q+1; //Ganzzahliger Wert
r = r-b; //Ganzzahliger Rest
}
</code><br />
{|| border="1" cellpadding="5" cellspacing="0"
!Befehlszähler
!Befehl
!Bemerkung
|-
||<div align="right">22</div>||R9 = 1||
|-
||<div align="right">23</div>||R5 = 0||
|-
||<div align="right">24</div>||R6 = R3|| Zähler für 1.Zahl
|-
||<div align="right">25</div>||R7 = R4|| Zähler für 2.Zahl
|-
||<div align="right">26</div>||IFZERO R7 GOTO 31|| Größer/Kleinervergleich
|-
||<div align="right">27</div>||R7 -= R9|| 1 mal subtrahieren
|-
||<div align="right">28</div>||IFZERO R6 GOTO 34||
|-
||<div align="right">29</div>||R6 -= R9|| 1 mal subtrahieren
|-
||<div align="right">30</div>||GOTO 26||
|-
||<div align="right">31</div>||R5 += R9|| 1 mal addieren
|-
||<div align="right">32</div>||R6 -= R7||
|-
||<div align="right">33</div>||GOTO 24||
|}
<br/>
=== Größer/Kleinervergleich ===
<br/>
{|| border="1" cellpadding="5" cellspacing="0"
!Befehlszähler
!Befehl
!Bemerkung
|-
||<div align="right">34</div>||IFZERO R10 GOTO 15||
|-
||<div align="right">35</div>||GOTO 20||
|}
<br />
{|| border="1" cellpadding="5" cellspacing="0"
!Befehlszähler
!Befehl
!Bemerkung
|-
||<div align="right">36</div>||IFZERO R20 GOTO 41|| x
|-
||<div align="right">37</div>||R20 -= R9||
|-
||<div align="right">38</div>||IFZERO R21 GOTO 42|| y
|-
||<div align="right">39</div>||R21 -= R9||
|-
||<div align="right">40</div>||GOTO 36||
|-
||<div align="right">41</div>||R23 = 1||
|-
||<div align="right">42</div>||GOTO 7|| Wenn R23 = 1; dann ist x <= y und wenn R23 = 0, dann x > y
|}