Theoretische Informatik

4. Übungsblatt

Aufgabe 1:

O-Notation
Ordnen Sie folgende Mengen von Funktionen bezüglich Inklusion und stellen Sie Gleichheiten fest! Dabei steht log für den abgerundeten Logarithmus zur Basis 2 mit log(0) =def 0. Eine Begründung der Inklusionen und Gleichheiten ist hier nicht gefordert.
  1. Unteraufgabe
90%

log(n) fehlt

Aufgabe 2:

While-Programm für prodZ mit Laufzeit O(n3)
Gesucht ist ein While-Programm (mit Syntaxprüfer testen!), das die Funktion prodZ : Z × Z → Z mit prodZ(x, y) = x·y in der Zeit O(n3) berechnet. Geben Sie eine nachvollziehbare Abschätzung der Laufzeit Ihres Programms in Abhängigkeit der Eingabelänge n = |x| + |y| an, wobei Sie die O-Notation verwenden dürfen.
84%
def prodZ(x,y):
  r = 0
  
  # Vorzeichen ermitteln
  negativ = 1
  if (x < 0):
    x = (0 - x)
    negativ = (0 - negativ)
  if (y < 0):
    y = (0 - y)
    negativ = (0 - negativ)
  # Gross/Klein-Zahl vertauschen
  if (y > x):
    r = x
    x = y
    y = r
    r = 0
  
  # Rekursiven Prozess anschieben
  r = prodZrek1(x,y,1)
  
  # Vorzeichen korrigieren
  if (negativ == -1):
    r = (0 - r)
  return r

def prodZrek1(zahl1,zahl2,faktor):
  r = 0
  
  zehnerpotenz = faktor
  i = 1
  while (i<10):
    zehnerpotenz = (zehnerpotenz + faktor)
    i = (i+1)
  if (zehnerpotenz <= zahl2):
    #print('Rekursion bei ',zehnerpotenz)
    r = prodZrek1(zahl1, zahl2, zehnerpotenz)
  
  n = 0
  muliplikationsFaktor = prodZrek2(zahl1,1,faktor)
  zahl2 = remove(zahl2,zehnerpotenz)
  #print('Debug ',r,' bekommt man vom faktor ',faktor,', zahl2=',zahl2)
  while (faktor <= zahl2):
    r = (r + muliplikationsFaktor)
    zahl2 = (zahl2 - faktor)
    n = (n+1)
  #print('Rekursion bei ',faktor,' mit n=',n,' und r=',r)
  return r

def prodZrek2(zahl,potenz,limit):
  r = zahl
  i = 1
  if (limit > potenz):
    while (i < 10):
      r = (r + zahl)
      i = (i+1)
    potenzneu = potenz
    i = 1
    while (i < 10):
      potenzneu = (potenzneu+potenz)
      i = (i+1)
    if (potenzneu < limit):
      r = prodZrek2(r,potenzneu,limit)
  return r

def remove(zahl, potenz):
  r = zahl
  potenzneu = potenz
  i = 1
  while (i<10):
    potenzneu = (potenzneu + potenz)
    i = (i+1)
  if (zahl >= potenzneu):
    r = remove(zahl,potenzneu)
  while (potenz <= r):
    r = (r - potenz)
  return r

#print(prodZ(9**550, 8**550))
Dem Korrektor fehlte eine Begründung, wie wir auf die oben genannte Laufzeit gekommen sind. Das gab marginal Punkteabzug. Sonst war alles richtig.

Aufgabe 3:

Vereinigung von Wertebereichen
Seien f : N → N und g : N → N berechenbare Funktionen.
  1. Geben Sie explizit eine berechenbare Funktion h : N → N mit Wh = Wf ∪ Wg an!
  2. Zeigen Sie Wh⊆Wf ∪ Wg!
  3. Zeigen Sie Wh⊇Wf ∪ Wg!
(gefordert: präzise Definition von h + Argumentation für die Inklusionen)
100%
Loesung von Aufgabe 3

Aufgabe 4:

RE ist abgeschlossen unter ∩
Beweisen Sie folgende Implikation für alle A, B ⊆ N.
A,B ∈ RE =⇒ A ∩ B ∈ RE
0%
Loesung
  1. Loesung wird noch gesucht!

Zusatzaufgabe 1:

Programmieren ohne Schleifen
Schreiben Sie ein While-Programm ohne While-Schleifen und ohne For-Schleifen, das die im Beispiel 2.7 definierte Funktion prim berechnet.
0%
Loesung
  1. Loesung wird noch gesucht!

Zusatzaufgabe 2:

Effiziente While-Programme für prodZ und divZ
Gesucht sind While-Programme (mit Syntaxprüfer testen!) mit Laufzeit O(n) für die folgenden Funktionen.
  1. prodZ: Z×Z → Z mit prodZ(x,y) = x·y
  2. divZ:Z×Z→Z mit divZ(x,y)= 􏰁⌊x/y⌋ falls y≠0 ; n.d. sonst
0%
Loesung
  1. Loesung wird noch gesucht!

Zusatzaufgabe 3:

While-Programm zum Sortieren
Gesucht ist ein While-Programm (mit Syntaxprüfer testen!) mit Laufzeit O(nlogn), das eine Liste von ganzen Zahlen sortiert. Die Ein- und Ausgaben sind mit der Listencodierung (Seite 68) codiert. Erklären Sie das von Ihnen verwendete Verfahren und begründen Sie die Laufzeit O(n log n) Ihres Programms.
0%
Loesung
  1. Loesung wird noch gesucht!