Prof. Dr. Manfred Schmidt-Schauß Fachbereich Informatik (20) Künstliche Intelligenz/Softwaretechnologie Johann Wolfgang Goethe-Universität Frankfurt am Main

Praktische Informatik 1:

Wintersemester 1997/98

Übungsblatt Nr. 4

Aufgabe 1 (10 Punkte)

• Für welche Konstanten a, b > 1 gilt a^{b^{n}} = O(b^{a^{n}})?

• Für welche Konstanten k, i > 0 gilt n^{1/k} ∗ (log_{2} n)^{k} = O(n^{i})?

• Welche Größenordnung hat 2^{a} ∗ n^{2} ∗ log_{2}((2^{b}) ∗ n) + \sqrt{n} ∗ e^{n} für Konstanten a, b > 0?

Aufgabe 2 (10 Punkte)

Geben Sie eine Haskellfunktion f an, die als Argument eine Zahl hat, und für deren Anzahl an Reduktionen gilt red_{f}(n) = O(3^{3^{n}}), aber nicht red_{f}(n) = O(2^{n}).

1. mit arithmetischen Operationen

2. nur mit den eingebauten arithmetischen Fuktionen +, -, ==.

Aufgabe 3 (10 Punkte)

In der Vorlesung wurde die Funktion potenz_log angegeben. Bestimmen Sie die Zahl der Reduktionen bei normaler Auswertungsordnung in Abhängigkeit von den Eingaben b und n. Wieviele Multiplikationen, Subtraktionen, ganzzahligen Divisionen und Restbildungen nach Division werden in Abhängigkeit von den Eingaben b und n durchgeführt. Zeigen Sie von welcher Größenordnung die Zahl der Reduktionen ist.

Aufgabe 4 (10 Punkte)

Reduzieren Sie

  1. (\x, y -> x*y) (y + 2) 3
  2. (let y = z*z in \f -> f y) (\x -> x*y)
  3. let y = x*x, x = a*b in a*b*x*y
  4. let z = a*b, b = b in let z = b*a in z

Aufgabe 5 (10 Punkte)

Geben Sie zu jedem Unterausdruck der Ausdrücke in Aufgabe 4 die Menge der frei vorkommenden Variablen und die Menge der gebundenen Variablen an.