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

  1. ((λz.zxx)z x)
  2. ((λx.(λx.(λx.x)x)x)x)
  3. (λx.y(λy.x(λx.xz(λy.yx))))
  4. (λx.(xy(λy.((xy)(λx.wxyz))(λz.wyz))))

Aufgabe 3 (5 Punkte)

Reduzieren Sie die folgenden Lambda-Ausdrücke. Hinweise: Manche Klammern sind nicht notwendig, andere, die nicht notwendig erscheinen, aber schon.

  1. (((λx.λy.(yx))(λp.λq.p))(λi.i))
  2. ((((((λx.λy.λz.(xy))z))(λf.λa.(fa)))(λi.i))(λj.j))
  3. (λh.(((λa.λf.(fa))h)h)(λf.(ff)))
  4. ((((λf.λg.λx.(f(gx)))(λs.(ss)))(λa.λb.b))(λx.λy.x))
  5. ((λ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)