Teil (a)
Gegeben sei der folgende Algorithmus in Pseudo-Code:
# Gegeben: Eine reelle Zahl x
int algo(x):
if x <= 1:
return 0
else:
return 1 + algo(x/3)
- Ist der Algorithmus deterministisch?
- Ist der Algorithmus determiniert?
- Für welche Eingaben $x \in \mathbb{R}$ terminiert er?
- Welche Funktion berechnet der Algorithmus? Wie lautet z.B. algo(1.000.000)?
Teil (b)
Gegeben sei der folgende Algorithmus in Pseudo-Code:
# Gegeben: zwei Strings der Länge n, indexiert mit s[0]...s[n-1].
boolean foo(s1, s2):
r = eine Zufallszahl zwischen 0 und n-1
Wiederhole 1000 mal:
count = -n
for j = 0,...,n-1:
if s1[(r+j) mod n] == s2[j]:
count += 1
if count >= 0:
return true
return false
- Ist der Algortihmus deterministisch?
- Ist der Algorithmus determiniert?
- Versuchen Sie die Funktion $f^{Alg}$ zu beschreiben. Was liefert der Algorithmus zurück?