Übungsaufgaben: Registermaschine

Inhaltsverzeichnis Verbergen
Aufgabe 1
Aufgabe 2
Aufgabe 3
Aufgabe 4
Aufgabe 5
Aufgabe 6
Aufgabe 7 (Bubblesort)
Aufgabe 8 (Liste)

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,
  9. die Quersumme einer Zahl.

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

Implementieren 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.

Aufgabe 7 (Bubblesort)

Implementieren Sie ein RM-Programm, welches die in den Registern 1 bis 10 stehenden Werte mittels des Bubblesort-Verfahres aufsteigend sortiert.

Aufgabe 8 (Liste)

Im Folgenden soll mithilfe einer RM eine einfach verkettete sortierte Liste implementiert werden und auf dieser einige grundlegende Operationen.

Dafür benötigen wir einige Vereinbarungen:

  • Zeiger auf root-Knoten in Register 1
  • Zeiger auf current-Knoten in Register 2
  • Register 3 verwenden wir für z.B. größter Wert in der Liste, zu suchenden Wert, einzufügenden Wert, zu löschenden Wert, …
  • Listenelemente werden ab Register 5 gespeichert, pro Knoten benötigt man 2 Register (Inhalt + Zeiger auf Folgeknoten)
  • das letzte Element der Liste hat als Zeiger auf den Folgeknoten den Wert „0“ gespeichert
  • die Knoten einer Liste müssen nicht nacheinander gespeichert werden (ist in einem realen Speicher ja auch nicht so), daher könnte eine Liste, die nacheinander mit den Werten 2 – 8 – 5 – 20 – 4 gefüllt wurde, wie folgt gespeichert sein (root- und current-Zeiger zeigen auf ersten Knoten):
5500213811572004900
R01R02R03R04R05R06R07R08R09R10R11R12R13R14R15R16

Mit diesen Vereinbarungen sind nun folgende Operationen zu implementieren (jeweils ein eigenes Programm):

  • Suche nach dem letzten (größten) Wert in der Liste (Ergebnis in R3)
  • Suche nach einem bestimmten Wert in der Liste (R3: Wert; vorhanden – Akku:1; nicht vorhanden – Akku:0)
  • Bestimmen der Anzahl der Knoten (Ergebnis in R3)
  • Berechnen der Summe der Werte aller Knoten (Ergebnis in R3)
  • Einfügen eines Elements in die sortierte Liste (z. B. Wert 3 in die oben angegebene Liste). Um freie Speicherplätze zu finden nehmen wir hier vereinfacht an, dass ein Knoten nicht den Wert 0 haben darf – damit bedeutet 0 einen freien Platz.
  • Löschen eines Wertes aus der Liste (zu löschender Wert in R3)
Schlagwörter: