Übung Klausuraufgaben

Hinweis: Verwenden Sie keine Hilfsmittel (Bücher, Skripte, Vorlesungsmitschriften, Taschenrechner), denn diese dürfen Sie in der Klausur auch nicht benutzen. Geben Sie zu allen Funktionen die Signatur an und kommentieren Sie die Funktionen ausreichend!

Aufgabe 1 (5 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 (10 Punkte) [15 min]

1. Schreiben Sie eine Haskell-Funktion, die eine nicht negative Zahl (Typ Integer) in eine Liste von Nullen und Einsen umwandelt, wobei die Liste die Binärdarstellung der Zahl repräsentieren soll. Eine Fehlerbehandlung für falsch eingegebene Zahlen ist nicht notwendig. Tip: Bauen Sie die Zahl von rechts nach links auf.
2. Verallgemeinern Sie die Funktion, sodaß die Zahl bezüglich einer beliebigen Basis dargestellt werden kann.

Aufgabe 3 (15 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 4 (15 Punkte) [20 min]

1. Definieren Sie einen neuen Datentyp Bruch, der entweder aus zwei Integern besteht (mit dem Konstruktor F), oder aus einem Integer (mit dem Konstruktor G). Die Zahl 0,5 wird dann als F 1 2 geschrieben und die Zahl -3 als G -3.
2. Schreiben Sie in Haskell die Funktionen add, sub, mul und div, die auf diesem Datentyp arbeiten.
3. Schreiben Sie eine Funktion norm, die die Brüche so weit wie möglich vereinfacht, d. h.
   1. den Bruch kürzt, wenn dies möglich ist (z.B. F 2 4 Þ F 1 2),
   2. den Bruch in eine ganze Zahl umwandelt, wenn dies möglich ist (z.B. F 4 2 Þ G 2), und
   3. negative Zahlen nur im Zähler stehen (z.B. F 2 -4 Þ F -1 2).
   Sie dürfen die Haskell-Funktion gcd benutzen.

Aufgabe 5 (15 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.

Aufgabe 6 (10 Punkte) [25 min]

Ein Algorithmus zum schnellen Berechnen der n-ten Fibonaccizahl (aus der Folge 0,1,1,2,3,5,8,...):

• Man starte mit dem Paar f₀=(1,0) für n=0.
• Das nächste Paar f_n erhalten wir, indem wir die linke Zahl nach rechts schreiben und die Summe der beiden Zahlen nach links schreiben, aus f₂ = (2,1) folgt also f₃ = (2+1,2) = (3,2).
• die linke Zahl ist die n-te Fibonaccizahl, also fibo(4) = 5, denn f₄ = (5,3).

1. Schreiben Sie eine Funktion in Haskell, die Fibonacci-Zahlen nach dem oben angegebenen Verfahren schnell (und endrekursiv) berechnet.
2. Schreiben Sie diese Funktion im λ-Kalkül. Sie dürfen alle Makros aus der Vorlesung verwenden ohne sie zu definieren (zum Beispiel T (True), F (False), S (Nachfolger), P (Vorgänger), PHI , Zahlen, Z (Test auf 0), Vergleichsoperatoren, Boolsche Operatoren, MUL (Multiplikation), Y (Rekursionsoperator)).

Aufgabe 7 (15 Punkte) [20 min]

1. Schreiben Sie eine Funktion in Haskell, die die syntaktische Gleichheit von Lambda-Ausdrücken testet, ohne derive Eq zu benutzen. Die Ausdrücke sollen in dem aus der Vorlesung bekannten Datentyp Expr vorliegen. Zwei Lambda-Ausdrücke sollen genau dann gleich sein, wenn die Syntaxbäume gleich und wenn alle Variablennamen in den jeweils korrespondierenden Blättern gleich sind.

   Die Lambda-Ausdrücke (Lam "x" (Var "x")) und (Lam "y" (Var "y")) sind somit nicht syntaktisch gleich.

2. Schreiben Sie eine Funktion isInTable, die zu einem gegebenen String a und einer gegebenen Liste von 2-Tupeln von Strings True zurückgibt, wenn der String a das erste Element in irgendeinem 2-Tupel in der Liste ist.
3. Schreiben Sie eine Funktion getFromTable, die zu einem gegebenen String a und einer gegebenen Liste von 2-Tupeln von Strings den String b zurückgibt, wenn das 2-Tupel (a,b) in der Liste vorkommt. Sie können davon ausgehen, daß das Vorhandensein von a als erstem Element eines 2-Tupels in der Liste gewährleistet ist.

Aufgabe 8 (10 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 9 (10 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 10 (15 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|...

^