Vorlesung ALP I - Übung 419500 V Algorithmen und Programmieren I
Wintersemester 2003/2004
Rojas
Gloye



Übung 4
17. November 2003 (Abgabe 26. November 2003)

Aufgabe 1 (6 Punkte)
Implementieren Sie die Funktion mergesort, die eine Liste von Zahlen mit dem 
Merge-Sort-Algorithmus absteigend sortiert. 

Aufgabe 2 (4 Punkte)
Welche Variablen der folgenden Lambda-Ausdrücke sind gebunden und welche sind 
frei. Wenn Sie gebunden sind: Zu welchem Lambda sind sie
gebunden? Beschten Sie, dass die Ausdrücke nicht ausgewertet
werden sollen. Das Lambda-Zeichen ist hier ein "slash".

a.  ((/z.zxx)z x) 
b.  ((/x.(/x.(/x.x)x)x)x) 
c.  (/x.y(/y.x(/x.xz(/y.yx)))) 
d.  (/x.(xy(/y.((xy)(/x.wxyz))(/z.wyz))))
 
Aufgabe 3 (5 Punkte)
Reduzieren Sie die folgenden Lambda-Ausdrücke. Manche
Klammern sind nicht notwendig, andere, die nicht notwendig 
erscheinen, aber schon. Das Lambda-Zeichen ist hier ein "slash".

a.  (((/x./y.(yx))(/p./q.p))(/i.i)) 
b.  ((((((/x./y./z.(xy))z))(/f./a.(fa)))(/i.i))(/j.j)) 
c.  (/h.(((/a./f.(fa))h)h)(/f.(ff))) 
d.  ((((/f./g./x.(f(gx)))(/s.(s s)))(/a./b.b))(/x./y.x)) 
e.  ((/p.((/q.(pq))((/x.x)(/a./b.a))))(/k.k)) 

Aufgabe 4 (2 Punkte)
Definieren Sie die XOR-Funktion zweier Argumente im Lambda-Kalkül und zeigen 
Sie, dass die Definition korrekt ist. 
 XOR F F = F
 XOR F T = T
 XOR T F = T
 XOR T T = F


letzte Änderung am 20. November 2003 (Alexander Gloye)