Algorithmen-Analyse

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?