Aufgabe 1

Berechnen Sie mithilfe der Registermaschine:

  1. die Summe der Zahlen von 1 bis n,
  2. das Produkt zweier Zahlen (durch Addition),
  3. die Fakultät von n,
  4. die Summe der Werte in den Registern 3 bis n (n steht in Register 1, Summe in Register 2),
  5. die Summe der Werte in den Registern 2 bis n (nullterminiert, Summe steht in Register 1),
  6. das Maximum zweier Zahlen,
  7. n mod m,
  8. die Summe zweier Brüche.

Die Ausführung eines RM-Programms benötigt Zeit und Speicherplatz. Beim Einheitskostenmaß ist die benötigte Zeit die Zahl der ausgeführten RM-Befehle und der benötigte Speicherplatz die Zahl der verwendeten Register.
Ermitteln Sie für (einige) RM-Programme von oben die benötigte Zeit und den benötigten Speicherplatz im Einheitskostenmaß.


Aufgabe 2

Ein paar komplexere Problemstellungen

  1. In Register 1 steht eine Zahl, von der festgestellt werden soll, ob diese eine Primzahl ist.
  2. Das kgV zweier Zahlen soll berechnet werden.
  3. Das ggT (nach Euklid) zweier Zahlen soll berechnet werden.
  4. Ist die in Register 1 stehende Zahl wundersam?

Aufgabe 3

Implementieren Sie eine Registermaschine, die ein Wort w \in \{ 1,2 \}* kopiert: f(w) = ww.


Aufgabe 4

Skizzieren Sie RM-Befehle, mit denen sich der Effekt der folgenden do-Schleife erreichen lässt: (c(2) > 0)

do {
    c(1) = 2* c(1) + 1; 
    c(2) = c(2) – 1; 
} while (c(2) >= c(1));

Aufgabe 5

Skizzieren Sie RM-Befehle, mit denen sich der Effekt der folgenden bedingten Anweisung erreichen lässt:

if (c(1) > c(2) + 17) {
    c(2) = 2*c(2) + 1
} else {
    c(2) = c(2) * c(3) 
}

Aufgabe 6

Erstellen Sie ein RM-Programm zur Berechnung der rekursiv definierten Funktion:

f(n)= \begin{cases} 0 & \text{ falls } n=0 \\ f(n-1)+n² & \text { sonst } \end{cases}

Hinweis: Speichern Sie die bei jedem Funktionsaufruf erzeugten lokalen Variablen auf einem selbst verwalteten Stack und verwenden Sie zur Berechnung der Zwischenwerte ein Register bzw. den Stack.

Schlagwörter: