Übung 4

8. November 2001 (Abgabe 19. November 2001)

Aufgabe 1 (9 Punkte)

In einem Kiste sind n Geschenke von unterschiedlichem Wert. Sie dürfen ein Geschenk aus der Kiste nehmen und es entweder annehmen oder ablehnen. Wenn Sie es ablehnen dürfen Sie ein weiteres Geschenk aus der Kiste nehmen usw.. Wenn Sie ein Geschenk annehmen, ist das Spiel zu Ende. Die beste Strategie ist es, erst m Geschenke abzulehnen und sich den Wert des wertvollsten Geschenks dieser m Geschenke zu merken. Dann wählt man das erste Geschenk der letzten n-m Geschenke, das einen größeren Wert als das bisher beste Geschenk hat. Wenn dies nicht vorkommt, dann wählt man das letzte Geschenk aus.

Zur Vereinfachung sollen die Geschenke alle Werte von 1 bis n haben. Schreiben Sie ein Programm in Haskell, das zu gegebenen n und m den prozentualen Anteil der Permutationen ausgibt, mit denen man das optimale Geschenk bekommt.

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?

1. ((ly.yxx)y x)
2. ((lx.(lx.(lx.x)x)x)x)
3. (lx.(xy(ly.((xy)(lx.wxyz))(lz.wyz))))
4. (lx.y(ly.x(lx.xz(ly.yx))))

Aufgabe 3 (5 Punkte)

Reduzieren Sie die folgenden Lambda-Ausdrücke.

1. (((lx.ly.(y x)) lp.lq.p) li.i)
2. (((((lx.ly.lz.(x y) z)) lf.la.(f a)) li.i) lj.j)
3. (lh.(((la.lf.(f a)) h) h) lf.(f f))
4. ((lp.((lq.(p q))((lx.x) la.lb.a))) lk.k)
5. ((((lf.lg.lx.(f (g x))) ls.(s s)) la.lb.b) lx.ly.x)

Aufgabe 4 (2 Punkte)

Definieren Sie die XOR-Funktion zweier Argumente im Lambda-Kalkül.

 XOR(F F) = F
 XOR(F T) = T
 XOR(T F) = T
 XOR(T T) = F