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: P (n) = • Potenzfunktion: pot(x, a) = ax • Fakultät: f ak(n) = n! • Monus-Operation: x−y = • Abstandsfunktion: |x − y| • Signum-Funktion: signum(n) ==Lösung== =Konstante Funktionen= ==Aufgabe== Unsere Definition der Menge der primitiv rekursiven Funktionen verwendet die Nullfunk- tionen als Basisfunktionen. Manche Quellen nehmen alternativ die konstanten Funktio- nen als Basisfunktionen auf. Zeigen Sie mit unserer Definitionsform, dass die konstanten Funktionen Cq : N0 r → N0 , mit Cq (n1 , n2 , . . . , nr ) = q, primitiv rekursiv sind. ==Lösung== =Polynom-Funktionen= ==Aufgabe== Begründen Sie, weshalb Polynome mit natürlichen Koeffizienten primitiv rekursiv sind. Beispiel: p(n) = an2 + bn + c. ==Lösung== =Rechenoperationen= ==Aufgabe== Folgen Sie dem Schema der rekursiven Definitionen 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== =Ackermann-Peter-Funktion= ==Aufgabe== Die AP -Funktion ist eine total berechenbare Funktion, die jedoch nicht primitiv rekursiv ist. Sie ist wie folgt definiert. AP (0, m) = m + 1 AP (nr, 0) = AP (nr − 1, 1) AP (nr, m) = AP (nr − 1, AP (nr, m − 1)) Füllen Sie die folgende Tabelle aus, soweit es eben geht. <br/> Geben Sie eine effizientere Implementation für AP an, indem Sie herausfinden, wie sich die Tabelleneinträge in Zeile i aus denen in Zeile i−1 gewinnen (ablesen) lassen. Benutzen Sie außerdem memoizing. ==Lösung== =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 definiert. F0 (x, y) = x + y Fn+1 (x, 0) = x, n ≥ 0 Fn+1 (x, y + 1) = Fn (Fn+1 (x, y), Fn+1 (x, y) + y + 1), n ≥ 0 Berechnen Sie F1 und F2 für selbstgewählte Argumente. ==Lösung==