Probeklausur

Hinweis: Verwenden Sie keine Hilfsmittel (Bücher, Skripte, Vorlesungsmitschriften, Taschenrechner). Sie haben 120 Minuten Zeit. Fangen Sie mit den einfachsten Aufgaben an. Geben Sie zu allen Funktionen die Signatur an und kommentieren Sie die Funktionen ausreichend!

Aufgabe 1 (1 Punkt) [5 min]

Schreiben Sie in Haskell eine Quicksort-Variante, die eine Liste von Listen nach der Länge der Teillisten sortiert. Beispiel:

qs [[1,2,3],[1],[1,2]] = [[1],[1,2],[1,2,3]]

Aufgabe 2 (3 Punkte) [15 min]

Wir möchten mit Daten vom Typ Nom arbeiten, wobei wir auch PlusUnendlich, MinusUnendlich und Undefiniert verwenden wollen. Definieren Sie einen passenden algebraischen Datentyp und die Funktionen add, sub, mul und div, die mit diesem Datentyp operieren. Für alle n>0 soll 0/0 undefiniert, n/0 unendlich und -n/0 negativ unendlich sein. (Es gibt noch weitere Fälle, in denen das Ergebnis undefiniert sein kann.)

Aufgabe 3 (2 Punkte) [10 min]

Definieren Sie die Multiplikation Natürlicher Zahlen (inklusive Null) als primitiv rekursive Funktion. Verwenden Sie nur die Grundfunktionen der primitiv rekursiven Funktionen.

Aufgabe 4 (2 Punkte) [5 min]

Beweisen Sie durch Induktion take n l ++ drop n l = l, wobei l auch eine leere Liste sein kann. Die Funktionen sind wie folgt definiert:

[] ++ xs	= xs	(++.1)
(a:as) ++ xs	= a:(as++xs)	(++.2)
drop 0 as	= as	(drop.1)
drop (n+1) []	= []	(drop.2)
drop (n+1) (a:as)	= drop n as	(drop.3)
take 0 as	= []	(take.1)
take (n+1) []	= []	(take.2)
take (n+1) (a:as)	= a:(take n as)	(take.3)

Geben Sie für alle Beweisschritte die verwendeten Beziehungen oder Gesetze an.

Aufgabe 5 (3 Punkte) [20 min]

Definieren Sie eine Turing-Maschine, die eine Binäre Zahl in eine Zahl zur Basis 4 überführt. Die Initialisierung des Bandes ist beliebig (unvorhersehbar). Beispiel:

...|B|0|1|1|1|A|...

^

...|C|1|3|B|0|1|1|1|A|...

^

Aufgabe 6 (3 Punkte) [20 min]

Definieren Sie in Haskell einen abstrakten Datentyp für Binärbäume von Zahlen.

1. Definieren Sie eine Funktion, um ein neues Element in den Baum einzufügen. Dabei sollen immer die links stehenden Kinder kleiner gleich, die rechts stehenden Kinder größer als die Eltern sein. Wenn der Wert schon im Baum vorhanden ist, dann soll der Baum selbst zurückgegeben werden.
2. Definieren Sie eine Funktion, um ein Element in einem solchen Binärbaum zu suchen. Die Funktion soll mit einem Wahrheitswert anzeigen, ob der Wert im Baum vorhanden ist oder nicht.
3. Definieren Sie eine Funktion, die das kleinste Element im Baum findet.
4. Definieren Sie eine Funktion, die die im Baum vorhandenen Zahlen sortiert ausgibt.