Sören Balko, Ilona Blümel, Dr. Martina Engelke, Markus Feldbach, Bert Freudenberg, Niels Grabe, Dr. Reinhard Köppe, Uwe Scholz, Nadine Schulze, Dr. Fritz Zbrog

Aufgabe 1

Skizzieren Sie verschiedene nicht-deterministische Möglichkeiten (unter Beachtung der Vorrangregeln), die folgende Formel schrittweise auszuwerten:

Aufgabe 2

Ein Bonbonglas ist mit mit vielen Lakritzeschnecken und Gummibärchen gefüllt. Außerdem liegt neben dem Glas eine "Wundertüte", die unerschöpflich viele Lakritzeschnecken enthält. Der folgende Vorgang soll nun solange ausgeführt werden, bis er sich nicht mehr wiederholen läßt:

• Entnehmen Sie zwei beliebige Süßigkeiten aus dem Glas.
• Falls beide die gleiche Geschmacksrichtung haben, essen Sie sie auf und füllen eine Lakritzeschnecke aus der nebenstehenden Tüte in das Glas.
• Haben Sie eine Lakritzeschnecke und ein Gummibärchen gezogen, dürfen Sie nur die Lakritzeschnecke naschen. Das Gummibärchen müssen Sie wieder in das Glas zurücklegen.

1. Terminiert dieser Vorgang?
2. Wieviel Süßigkeiten verbleiben im Glas?
3. Ist der Vorgang determiniert oder deterministisch?

Aufgabe 3

Formulieren Sie einen (intuitiven) terminierenden, deterministischen Algorithmus für die Rechenoperation Addition über den natürlichen Zahlen  = {0, 1, 2, 3, ...}. Die natürlichen Zahlen sollen als Dezimalzahlen dargestellt werden.

Bei der Addition zweier natürlicher Zahlen x, y  mit dem Ergebnis z  (z = x + y)  dürfen nur die elementaren Operationen Erhöhung und Verminderung einer natürlichen Zahl um Eins (Inkrement und Dekrement) und die Vergleichsoperation '=' verwendet werden.

Machen Sie plausibel, daß Ihr Algorithmus für alle erlaubten Werte terminiert. Erläutern Sie den Algorithmus am Beispiel Ihrer Wahl.

Aufgabe 4

Formulieren Sie einen weiteren (intuitiven) terminierenden, deterministischen Algorithmus für die  Rechenoperation Division über den natürlichen Zahlen  = {0, 1, 2, 3, ...}. Die natürlichen Zahlen sollen als Dezimalzahlen dargestellt werden.

Die Division zweier natürlicher Zahlen x, y , y  0 liefert das ganzzahlige Ergebnis z und den ganzzahligen Rest r , so daß gilt  x = z * y + r mit 0  r < y. Zulässige Elementaroperationen sind die Addition und Subtraktion zweier beliebiger natürlicher Zahlen, sowie die Vergleichsoperation "".

Machen Sie plausibel, daß Ihr Algorithmus für alle erlaubten Werte terminiert. Erläutern Sie den Algorithmus am Beispiel Ihrer Wahl.