Übungen: Reduktion von Ausdrücken

Aufgabe 1: Boolesche Ausdrücke

Hinweis: Nutze für diese Aufgabe die Racket-Version Intermediate Student with lambda.

Mithilfe von Racket lassen sich auch komplexere boolesche Ausdrücke auswerten. Im Folgenden wollen wir hierfür die drei aussagenlogischen Operatoren $\neg$, $\land$ und $\lor$ nutzen:

Aussagenlogischer Operator	Racket
$\neg$	not
$\land$	and
$\lor$	or

(a)-(e) Schreibe für die nachfolgenden booleschen Ausdrücke jeweils einen Racket-Ausdruck in dein Definitionsfenster, der den Wahrheitswert des entsprechenden Ausdrucks bestimmt.

(a) $(3 = 3) \land (2 < 4)$

(b) $((3 = 4) \lor (6 > 5)) \land (2 < 3)$

(c) $(4 = 3) \land (2 < 3)$

(d) $\lnot ( (1 < 3) \lor (2 > 9) )$

(e) $\lnot ( ((3 = 3) \lor (4 > 10)) \land \lnot(2 < 5) )$

(f) Führe den Stepper für die Ausdrücke (a)-(e) aus. Achte dabei darauf, ob alle Teilausdrücke ausgewertet werden.

(g) Anhand deiner Beobachtung in Aufgabenteil (f): Welche Optimierungen nimmt die Auswertungsstrategie von Racket vor?

Aufgabe 2: Endliche Liste der Fibonacci-Folge

Hinweis: Nutze für diese Aufgabe die Racket-Version Schreibe dein Programm!.

Im Kapitel der Strukturierung haben wir gesehen, dass die unten stehenden Definition der Fibonacci-Folge bei der von den meisten Racket-Versionen genutzten Eager Evaluation nicht möglich ist, da diese in eine Endlosschleife hineinläuft. Um die Definition dennoch erfolgreich umzusetzen, haben wir daher auf Lazy Evaluation zurückgegriffen.

(define naechste-fibonacci-zahl
  (lambda (a b)
    (cons a (naechste-fibonacci-zahl b (+ a b)))))

(define fibonacci-folge
  (naechste-fibonacci-zahl 0 1))

Natürlich lässt sich die Fibonacci-Folge auch mit Eager Evaluation berechnen. Allerdings müssen wir dafür einen klaren Endpunkt festlegen, um eine unendliche Rekursion zu vermeiden.

(a) Schreibe eine Funktion erste-n-fibonacci, die bei Übergabe einer Zahl $n$ eine Liste mit den ersten $n$ Fibonacci-Zahlen zurückgibt. Die Funktion soll unter Eager Evaluation terminieren.

(b) Definiere dir eine Liste der ersten 10 sowie der ersten 50 Fibonacci-Zahlen.