Theoretische Informatik

1. Übungsblatt

Aufgabe 1:

30
Eigenschaften von Funktionen
Geben Sie jeweils eine Funktion mit den geforderten Eigenschaften an, oder begründen Sie, dass eine solche Funktion nicht existiert. Geben Sie zu jeder Funktion auch ihren Graph als Menge an.
  1. totales f1 : {0, 1} → {0, 1}, das nicht injektiv ist
  2. totales f2 : {0, 1, 2} → {1}, das nicht surjektiv ist
  3. f3 : {0} → {0}, das nicht total ist
  4. bijektives f4 : {0, 1} → {0, 1, 2}
  5. totales f5 : ∅ → {0, 1}
  6. surjektives f6 : {0, 1, 2} → {0, 1, 2}, das nicht injektiv ist
90%
  1. f(x) = 1
    - total
    - nicht injektiv
    Gf= { (0,1) , (1,1) }
  2. Geht nicht, weil |D| > |W|
    Wenn die Mächtigkeit des Def' größer ist als die Mächrigkeit des Wertebereiches, dann kann es keine totale, nicht-surjektive Funktion geben.
  3. f(x) = 1/x
    Nicht-total, da f(0) mit 1/0 nicht definiert ist
    Gf = {}
  4. Geht nicht, da |D| ≠ |W|
    Bei Bijektivität muss die Möglichkeit identisch sein.
  5. Geht, f(x)=0
  6. Geht nicht, da |D| ≥ |W| ist nicht erfüllt
    Weil ein Wert im Wertebereich zweimal abgebildet und alle Anderen einmal abgebildet werden sollen.

Aufgabe 2:

30
Der unten stehende fehlerhafte Quelltext ist ein Versuch, ein While-Programm zu schreiben, das folgende Funktion f : Z → Z berechnet:

Finden und begründen Sie alle Fehler des Quelltexts. Berichtigen Sie die Fehler, sodass ein gülti- ges While-Programm entsteht, das die Funktion f berechnet.
def  g(f):
    return f*2

def f(x):
  if x<0
      return 0
  else if x=0
         return 1
    else {
        d = g(f(x-1));
        return d
    }
100%
Fehler in Aufgabe 2 (Originalquelltext):
  • (1): Variable f darf nicht f heißen, da f bereits reserviert ist
  • (2) Falsch eingerückt. Zwei Leerzeichen entsprechen einer Ebene im Code
  • (2): Multiplikation ist bei While-Programmen nicht erlaubt
  • (2), (7), (10): Berechnungen müssen in runden Klammern stehen
  • (5): Bedingungen müssen in Klammern stehen
  • (5): Bei if muss ein Doppelpunkt am Zeilenende stehen
  • (6), (8), (11): Es darf nur einen return am Programmende geben!
  • (7): Elseif gibt es nicht in Python. Es muss in else-if-else aufgeteilt werden
  • (8), (9), (10), (11), (12): Entsprechend gibt es dann hier falsche Einrückungen
  • (9), (12): Es gibt keine geschweiften Klammern in Python (zumindest nicht in der Funktion wie in Java und Co)
  • (10): Es gibt keine Semikolons zum Zeilenabschluss
Verbessertes Programm: 
def g(x):
  return (x+x)

def f(x):
  r = 0
  if (x<0):
    r = 0
  else:
    if (x==0):
      r = 1
    else:
      d = g(f((x-1)))
      r = d
  return r

Aufgabe 3:

40
While-Programm für Binärdarstellung
Gesucht ist ein While-Programm (mit Syntaxprüfer testen!), das die Binärdarstellung einer natürlichen Zahl n auf dem Bildschirm ausgibt. Gehen Sie dazu wie folgt vor.
  1. Schreiben Sie ein While-Programm für die Funktion divtwo(x) = { [x/2] falls x≥0, 0 sonst
  2. Verwenden Sie die Funktion divtwo und schreiben Sie ein While-Programm, das für Eingaben n ≥ 0 die Ziffern der Binärdarstellung von n nacheinander auf dem Bildschirm ausgibt. Ist n < 0, so soll 0 ausgegeben werden.
100%
def divtwo(x):
  half = 0
  while ((half + half) <= x):
    half = (half + 1)
  return (half - 1)

#Binaerziffern von rechts (oben) nach links (unten)
def bin(n):
  half = 0
  if (n <= 0):
    print(0)
  else:
    while (n > 0):
      half = divtwo(n)
      if ((half + half) < n):
        print(1)
      else:
        print(0)
      n = half
  return -1