BuK-Übung10 G1

Aus ProgrammingWiki
< BuK < IIm10
Archivierte Version vom 2011-06-17T07:58:08+00:00. Aktuelle Version

Inhaltsverzeichnis

Primitiv rekursive zahlentheoretische Funktionen

Aufgabenstellung

Weisen Sie nach, dass die folgenden zahlentheoretischen Funktionen primitiv rekursiv sind. Dabei dürfen Sie bereits auf das Ergebnis der folgenden Aufgabe zurückgreifen.

  • Vorgängerfunktion P(n)= \begin{cases} 0 & ,\text{wenn } n=0\\ n-1 & sonst \end{cases}
  • Potenzfunktion pot(x,a)=a^x
  • Fakultät fak(n)=n!
  • Monus-Operation x-y=\begin{cases} 0 & ,\text{wenn } x \leq y\\ x-y & sonst \end{cases}
  • Abstandsfunktion |x-y|
  • Signume-Funktion signum(n)

Lösung

Vorgängerfunktion:

P(0)=C_0^1=0 P(n+1)=P(S(n))=U_1^2(n,P(n))=n

Potenzfunktion:

pot(0,a) = C_1^1=1 pot(S(x),a) = g(x,pot(x,a),a) = mult(U_3^3(x,pot(x,a),a), U_2^3(x,pot(x,a),a))

Fakultät:

fak(0) = C_1^1=1 fak(S(n))= g(n, fak(n)) = mult(U_1^2(n,fak(n)), U_2^2(n,fak(n))

Monus-Operation:

mon(0,x)=U_1^1(x)=x mon(S(y),x)=U_2^3(y,mon(y,x),x)

Abstandsfunktion:

ab(x,y) = add(U_2^2(mon(y,x),mon(x,y)), U_1^2(mon(y,x),mon(x,y)))

Signum-Funktion:

signum(0) = C_0^0=0 signum(S(n)) = U_2^2(n, signum(n))

Konstante Funktionen

Aufgabenstellung

Unsere Definition 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 Definitionsform, dass die konstanten Funktionen C_q^r : \mathbb{N}_0^r \mapsto \mathbb{N}_0^r, mit C_q^r(n_1,n_2,....,n_r)=q, primitiv rekursiv sind.

Lösung

C_q^r(n_1,n_2,....,n_r) = f(g(n_1),g(n_2),....,g(n_r)) = f(U_1^r(n_1,n_2,...,n_r),U_2^r(n_1,n_2,...,n_r),.....,U_q^r(n_1,n_2,...,n_r))

Polynom-Funktionen

Aufgabenstellung

Begründen Sie, weshalb Polynome mit natürlichen Koeffizienten primitiv rekursiv sind.

Beispiel:p(n)=an^2+bn+c

Lösung

Es kann gezeigt werden, dass die Addition, die Multiplikation und die Potenzfunktion primitiv-rekursiv sind. Die Polynom-Funktion kann durch Verwendung dieser drei Funktionen durch Substitution und Rekursin gebildet werden. Da dies möglich ist und die Funktionen wie bereits erwähnt primitiv-rekursiv sind, ist auch die Polynom-Funktion primitiv-rekursiv.

Rechenoperationen

Aufgabenstellung

Folgen Sie dem Schema der rekursiven Definitionen der elementaren binären Rechenoperationen (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