Theoretische Informatik

2. Übungsblatt

Aufgabe 1: (RAM zur Berechnung des größten gemeinsamen Teilers)

20
Schreiben Sie ein kommentiertes RAM-Programm, das die folgende Funktion ggT : N × N → N berechnet.
ggT(x, y) = { größter gemeinsamer Teiler von x und y, falls x ≠ 0 und y ≠ 0 - max(x, y) , sonst
100%
0 R2<-R1 - R0 // R2 wird der Wert R1-R0 zugewiesen
1 IF R2 > 0 GOTO 3 // Falls R2 > 0 ist die Rechnung richtig und man geht zu 3
2 R2<-R0-R1 // falls nicht (R2 <= r): Minuend und Subtrahend vertauschen
3 R0<-R1 
4 R1<-R2
5 IF R1 > 0 GOTO 0 // Falls R1 > 0 ist der GGT noch nicht gefunden -> Iteriere so lange bis GGT gefunden.
6 STOP

Aufgabe 2: (Bestimmen der berechneten Funktion)

20
Bestimmen Sie die von dem folgenden While-Programm berechnete Funktion und geben Sie diese mathematisch exakt an. Begründen Sie Ihre Aussage! 
def f6(x):
  i = 0
  y = 1
  z = 1
  while (z< x):
    i = (i+1)
    z = (z+y)
    y = (y+y)
  return i
50%
Abgabe v. Aufgabe 2
1. Die Begründung hat dem Korrektor nicht ausgereicht
2. Alternativ lässt sich die Funktion auch aufgerundet darstellen, jedoch dann ohne '+1'

Aufgabe 3: (Listencodierung)

60
Verwenden Sie die im Skript auf den Seiten 9–10 beschriebene Listencodierung und schreiben Sie ein kommentiertes While-Programm (mit Syntaxprüfer testen!), das folgende Funktionen zum Erstellen und Abfragen von codierten Listen zur Verfügung stellt.
  1. ListCreate(): Liefert den Code der leeren Liste ⟨⟩.
  2. ListGetLength(l): Falls l der Code einer Liste ist, so wird die Anzahl der Elemente der Liste zurückgegeben. Andernfalls darf sich die Funktion beliebig verhalten.
  3. ListGetElement(l,i): Falls i ≥ 1 und l der Code einer Liste mit mindestens i Elementen ist, so wird das i-te Listenelement von links zurückgegeben. Andernfalls darf sich die Funktion beliebig verhalten.
  4. ListAppendElement(l,e): Falls l der Code einer Liste ist und e ≥ 0, so wird das Elemente rechts an die Liste angehängt und der Code der neu entstandenen Liste zurückgegeben. Andernfalls darf sich die Funktion beliebig verhalten.
40%
Teilaufgabe a 
def ListCreate():
  return 2
Teilaufgabe b 
def ListGetLength(l):
  r = 0
  b = bin(l)
  length = binLength(b)
  while (length > 0):
    bit = getbit(b,length)
    if (bit == 2):
      r = (r+1)
    b = removeNbit(b,length)
    b = removeNbit(b,(length-1))
    length = (length-2)
  return (r-1)
Der restliche Code war nicht sehr "schön".
Daher hab ich die 200 verbliebenden Zeilen hier nicht hochgeladen.

Zusatzaufgabe 1: (schnelle Paritätsbestimmung)

20
Gesucht ist ein “schnelles” While-Programm, das testet, ob die Eingabe eine ungerade ganze Zahl ist. Bis zu welchen Eingabegrößen (104, 106, 108, 1010, 10100, 101000) liefert Ihr Programm das Ergebnis innerhalb einer Minute? Schätzen Sie die ungefähre Anzahl der Rechenschritte in Abhängigkeit der Eingabelänge n ab. (Die Länge einer Eingabe x ≥ 0 sei hier die Anzahl der Ziffern von bin(x).)
100%
# gerade(zahl) kann bis zahl<10**997 berechnen

def remove(zahl,step,vorstepergebnis):
  i = 1
  faktor = vorstepergebnis
  while (i<10):
    faktor = (faktor + vorstepergebnis)
    i = (i+1)
  if (faktor <= zahl):
    zahl = remove(zahl,(step+1),faktor)
    while (faktor <= zahl):
      zahl = (zahl - faktor)
  else:
    zahl = zahl
  return zahl

def gerade(zahl):
  r = 2
  zahl = remove(zahl,1,1)
  if ((zahl == 0) or (((zahl == 2) or (zahl == 4)) or ((zahl == 6) or (zahl == 8)))):
    r = 1
  else:
    r = 0
  return r

Zusatzaufgabe 2:

40
schnelle Listencodierung
Gesucht ist ein While-Programm, das die Funktionen zur Listencodierung aus Aufgabe 3 “schnell” berechnet. Bis zu welchem n können sie innerhalb einer Minute die Liste ⟨1, 2, . . . , n⟩ mittels ListAppendElement erzeugen und danach mittels ListGetElement vollständig auslesen? Schätzen Sie die ungefähre Anzahl der Rechenschritte in Abhängigkeit der Listengröße n ab. (Ist l Code einer Liste, so sei die Listengröße die Anzahl der Ziffern von bin(l).)
0%
Keine Loesung bekannt