BuK/IIm10/BuK-Übung10 G2

Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
=Primitiv rekursive zahlentheoretische Funktionen=
==Aufgabe==
Weisen Sie nach, dass die folgenden zahlentheoretischen Funktionen primitiv rekursiv
sind. Dabei dürfen Sie bereits auf das Ergebnis der folgenden Aufgabe zurückgreifen.<br/>

• Vorgängerfunktion:
<math>P(n) =\begin{cases}
0, &\text{wenn }n = 0;\\
n-1, &\text{sonst}
\end{cases}</math><br/>

• Potenzfunktion: 
<math>pot(x,a) =a^x</math><br/>

• Fakultät: 
<math>fak(n) = n!</math><br/>

• Monus-Operation: 
<math>monus(x,y) = x\ \dot{-}\ y = \begin{cases}
0, &\text{wenn }x\leq{}y;\\
x-y, &\text{sonst}
\end{cases} </math><br/>

• Abstandsfunktion: 
<math>dist(x,y) = |x - y|</math><br/>

• Signum-Funktion: 
<math>signum(n) =\begin{cases}
0, &\text{wenn }n = 0;\\
1, &\text{sonst}
\end{cases}</math><br/>

==Lösung==

<math>P(0)=C_0^0 = 0</math>

<math>P(S(n))=g(n,P(n)) = U_1^2(n,P(n)) = n</math>

Potenzfunktion:

<math>pot(0,a) = C_1^1(a) = 1</math>

<math>pot(S(x),a) = g(x,pot(x,a),a) = mul(U_2^3(x,pot(x,a),a), U_3^3(x,pot(x,a),a)) = mul(pot(x,a),a)</math>

Fakultät:

<math>fak(0) = C_1^0 = 1</math>

<math>fak(S(n))= g(n, fak(n)) = mul(S(n), U_2^2(n,fak(n)) = mul(S(n),fak(n))</math>

Monus-Operation:

<math>monus(0,x)=U_1^1(x)=x</math>

<math>monus(S(y),x)=P(U_2^3(y,monus(y,x),x))</math>

Abstandsfunktion:

<math>dist(x,y) = add(monus(U_1^2(x,y),U_2^2(x,y)),monus(U_2^2(x,y),U_1^2(x,y))) = add(monus(x,y),monus(y,x))</math>

Signum-Funktion:

<math>signum(0) = C_0^0=0</math>

<math>signum(S(n)) = U_2^2(n, signum(n))</math>

=Konstante Funktionen=
==Aufgabe==
Unsere Deﬁnition der Menge der primitiv rekursiven Funktionen verwendet die Nullfunktionen als Basisfunktionen. Manche Quellen nehmen alternativ die konstanten Funktionen als Basisfunktionen auf.
Zeigen Sie mit unserer Deﬁnitionsform, dass die konstanten Funktionen <math>C_q^r : \mathbb{N}_0^r \rightarrow \mathbb{N}_0</math> ,
mit <math>C_q^r(n_1 , n_2 , \dots , n_r ) = q</math>, primitiv rekursiv sind.

==Lösung==
<math>C_q^r(n_1,n_2,...,n_r)=S_a^2(a,C_0^r(n_1,n_2,...,n_r))</math> <br/>
Die Nachfolgerfunktion S wird a mal auf <math>C_0^r</math> ausgeführt<br/>
<math>S_a^2(0,m)=m</math><br/>
<math>S_a^2(S(a),m)=S_a^2(a,S(m))</math>

=Polynom-Funktionen=
==Aufgabe==
Begründen Sie, weshalb Polynome mit natürlichen Koeﬃzienten primitiv rekursiv sind.
Beispiel: <math>p(n) = a*n^2 + b*n + c</math>.

==Lösung==
Die Polynome enthalten die Operationen Addition, Multiplikation und Potenz. Da die Operationen primitiv rekursiv sind, sind auch Polynome primitiv rekursiv.

<language>Scheme</language>
=Rechenoperationen=
==Aufgabe==
Folgen Sie dem Schema der rekursiven Deﬁnitionen der elementaren binären Rechenoperrationen (Addition (1), Multiplikation (2), Potenzieren (3), ...) und entwickeln Sie eine
entsprechende Scheme-Prozedur '''op'''. Verwenden Sie '''add1''' für die Nachfolger- und '''sub1'''
für die Vorgängerfunktion. Aufrufbeispiel: (op 3 10 2) liefert 1024.

==Lösung==
<code id="4dfdf93231861">
(define add1
  (lambda (n) (+ n 1)))

(define sub1
  (lambda (n)
    (if (= n 0)
        0
        (- n 1))))

(define op
  (lambda (nr m n)
    (cond ((= nr 0) (add1 m))
          ((and (= nr 1) (= m 0)) n)
          ((and (= nr 2) (= m 0)) 0)
          ((= m 0) 1)
          (else (op (sub1 nr) (op nr (sub1 m) n) n)))))
</code>
<run id="4dfdf932318ca">(op 3 10 2)</run>

<language>Scheme</language>
=Ackermann-Peter-Funktion=
==Aufgabe==
Die AP -Funktion ist eine total berechenbare Funktion, die jedoch nicht primitiv rekursiv
ist. Sie ist wie folgt deﬁniert.<br/>
<math>AP(0, m) = m + 1</math><br/>
<math>AP(nr, 0) = AP(nr - 1, 1)</math><br/>
<math>AP(nr, m) = AP(nr - 1, AP(nr, m - 1))</math>

Füllen Sie die folgende Tabelle aus, soweit es eben geht.
<br/>
Geben Sie eine eﬃzientere Implementation für AP an, indem Sie herausﬁnden, wie sich
die Tabelleneinträge in Zeile i aus denen in Zeile i−1 gewinnen (ablesen) lassen. Benutzen
Sie außerdem memoizing.

==Lösung==
Eine halbwegs ausgefüllte Tabelle kann unter [http://de.wikipedia.org/wiki/Ackermannfunktion#Wertetabelle] gefunden werden.
<code id="4dfdff98baa03" hidden>
(define add1  (lambda (n) (+ n 1)))
(define sub1  (lambda (n)    (if (= n 0)        0        (- n 1))))</code>
<code id="4dfdff98baa7f">
(define AP
  (lambda (nr m)
    (cond ((= nr 0) (+ m 1))
          ((= m 0) (AP (sub1 nr) 1))
          (else (AP (sub1 nr) (AP nr (sub1 m)))))))
</code>
<run id="4dfdff98bab51">(AP 3 3)</run>
Die Funktionswerte für nr = 1 werden immer vom Feld rechts oberhalb AP(0,m+1) verwendet. Es ergibt sich:<br/>
<math>AP(1, m) = m + 2</math><br/>
Für nr = 2 werden die Funktionswerte AP(1,2*m+1) verwendet. Eingesetzt ergibt sich:<br/>
<math>AP(2, m) = 2*m + 3</math><br/>
<code id="4dfdff98baae0">
(define AP#
  (lambda (nr m)
    (cond ((= nr 0) (+ m 1))
          ((= nr 1) (+ m 2))
          ((= nr 2) (- (* m 2) 3))
          ((= m 0) (AP (sub1 nr) 1))
          (else (AP (sub1 nr) (AP nr (sub1 m)))))))
</code>
<run id="4dfdff98babaa">(AP# 3 3)</run>

<language>Scheme</language>
=Sudan-Funktion=
==Aufgabe==
Der rumänische Mathematiker Gabriel Sudan (14.04.1899 - 22.06.1977) – wie Ackermann
ebenfalls ein Schüler von David Hilbert – hat 1927 eine total berechenbare jedoch nicht
primitiv rekursive Funktion publiziert. Sie ist folgendermaßen deﬁniert.<br/>
<math>F_0 (x, y) = x + y</math><br/>
<math>F_{n+1} (x, 0) = x, n \geq{} 0</math><br/>
<math>F_{n+1} (x, y + 1) = F_n (F_{n+1} (x, y), F_{n+1} (x, y) + y + 1), n \geq{} 0</math><br/>
Berechnen Sie <math>F_1</math> und <math>F_2</math> für selbstgewählte Argumente.

==Lösung==
Um die Funktion besser in Scheme umzusetzten wird das Indice als erster Parameter der Funktion festgelegt.
<code id="4dfe02e6e7c9f" hidden>
(define add1  (lambda (n) (+ n 1)))
(define sub1  (lambda (n)    (if (= n 0)        0        (- n 1))))
</code>
<code id="4dfe02e6e7d0b">
(define sudan
  (lambda (n x y)
    (cond ((= n 0) (+ x y))
          ((= y 0) x)          
          (else (sudan (sub1 n) (sudan n x (sub1 y)) (+ (sudan n x (sub1 y)) y))))))
</code>
Der Funktionswert von <math>F_2(1,2)</math> ist 10228.
<run id="4dfe02e6e7d81">(sudan 2 1 2)</run>
BuK/IIm10/BuK-Übung10 G2

Suche
