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

Aufgabe 1 (10 Punkte)

Sei A(x, y) die Ackermann-Funktion aus der Vorlesung. Zeigen Sie, daß

A(x, 1) = 2x
A(x, 2) = 2^{x}
A(x, 3) = 2^{2^{·^{·^{·^{2}}}}} (ein “Stapel” von x zweien)

Aufgabe 2 (10 Punkte)

Füllen Sie die folgende Wertetabelle aus.

x\y 1 2 3 4 5

1 2 3

4  • •

Schalten Sie die Statistik-Ausgabe im Hugs ein (:s +s) und beobachten Sie wie sich die Zahl der Reduktionen bei A(x, 2) mit wachsendem x verändert. Wieviele Reduktionen schätzen Sie für A(14, 2)? Wieviele Reduktionen schätzen Sie für A(4, 3)?

Aufgabe 3 (10 Punkte)

g ∈ O(f) gdw. es gibt r > 0 und für alle bis auf endlich viele n gilt g(n) < r ∗ f(n)
g ∈ o(f)  gdw. für alle r > 0 und für alle bis auf endlich viele n gilt g(n) < r ∗ f(n)
g ∈ Ω_{∞}(f) gdw. es gibt r > 0 und für unendlich viele n gilt g(n) > r ∗ f(n)
g ∈ ω(f)  gdw. für alle r > 0 und für unendlich viele n gilt g(n) > r ∗ f(n)
g ∈ Θ(f) gdw. es gibt r_{1}, r_{2} > 0 und für alle bis auf endlich viele n gilt r_{1} ∗ f(n) ≤ g(n) ≤ r_{2} ∗ f(n)

Zeigen Sie

1. g ∈ o(f) ⟺ lim_{n→∞} \frac{g(n)}{f(n)} = 0

2. g ∈ Θ(f) ⟺ g ∈ O(f) und f ∈ O(g)

3. g ∈ O(log_{2} n) ⟺ für alle k ≥ 2 : g ∈ O(log_{k} n)

4. Es ist log^{∗} n = min\{i| \underbrace{log(log(…}_{i} n) …) ≤ 1\}. Zeigen Sie \frac{n}{log^{∗} n} ∈ o(n).

Aufgabe 4 (10 Punkte)

Angenommen Sie haben Programme, deren Resourcenbedarf in Abhängigkeit von der Eingabelänge n sich wie unten angegeben verhält. Wie groß kann die Eingabe sein, die Sie mit doppelter Rechnerkapazität bearbeiten können?

Resourcenbedarf

neue Eingabegröße

log_{2} n

n
n^{k}
2^{n}

Aufgabe 5 (10 Punkte)

Die Binomialkoeffizienten kann man auf viele verschiedene Weisen berechnen. Unter anderem als \binom{n}{k} = \frac{n!}{k!(n−k)!} und als \binom{n}{k} = \binom{n−1}{k} + \binom{n−1}{k−1}. Wobei \binom{n}{0} = 1, \binom{n}{1} = n und \binom{n}{n} = 1. Programmieren Sie beide Berechnungen in Hugs und beobachten Sie, wie sich die Zahl der Reduktionen in Abhängigkeit von der Eingabe verhält. Erklären Sie Ihre Beobachtung.