Prog:Klausur 2004-07-26 Vogler

Aus Tudwiki
Wechseln zu: Navigation, Suche

geschrieben von Tudor, Aufgabe 2 von Mabü, Aufgabe 3 von EnjoyTheChris, Aufgabe 8 Tippfehler beseitigt t3rr0r

1.

  (a) SI = (z=3*y*(x-x1)) ^ (x1 >= 0)
  (b) A = SI
      B = SI ^ (x1<=0)
      C = SI
      D = SI ^ (x1>0)

2.

  (a)
  void insert(node* baum, int s);
  void insert2(node* baum, int s, int pos)
  {
    if ((*baum) == NULL)
    {
      node neu;
      neu = malloc(sizeof(b_node_type));
      neu->key = s;
      neu->pos = pos;
      neu->left = NULL;
      neu->right = NULL;
      (*baum) = neu;
    } else
      {
        if (s < (*baum)->key)
          insert2(&((*baum)->left), s, -1);
        else
          insert2(&((*baum)->right), s, 1);
      }
  }
  void insert(node* baum, int s)
  {
    insert2(baum, s, 0);
  }
  Aufruf:
  node baum;
  baum = NULL;
  insert(&baum, 3061340);
  insert(&baum, 0xAFFE);


  (b)
  int linke(node baum)
  {
    if (baum)
    {
      if (baum->left)
        return 1 + linke(baum->left) + linke(baum->right);
      else
        return linke(baum->right);
    } else
      return 0;
  }

3.

  (a) data Term = Wert Int | Add Term Term | Mul Term Term
  (b) eval :: Term->Term
      eval (Wert x) = Wert x
      eval (Add t1 t2) = Wert ((termzahl t1) + (termzahl t2))
      eval (Mul t1 t2) = Wert ((termzahl t1) * (termzahl t2))
      termzahl :: Term -> Int
      termzahl (Wert x) = x
      termzahl (Add t1 t2) = termzahl (eval t1) + termzahl (eval t2)
      termzahl (Mul t1 t2) = termzahl (eval t1) * termzahl (eval t2)
  (c) transform :: [Term] -> [Term]
      transform [] = []
      transform (x:r) 
         |  (termzahl (eval x)>=0) = ([(eval x)] ++ transform r)
         |  otherwise  = (transform r)



4.

  IV: prodTree t = prod(collapse t))
  IA: prodTree (Leaf x) = x
                        = x * 1
                        = x * prod([])
                        = prod(x:[])
                        = prod([x])
                        = prod(collapse(Leaf x))
  IS: prod(collapse(Branch x li re))
                        = prod( (collapse li) ++ [x] ++ (collapse re) )
      da prod(x++y) = (prod x) * (prod y) gegeben folgt
                        = (prod(collapse li)) * (prod [x]) * (prod(collapse re))
                        = (prod [x]) * (prod(collapse li)) * (prod(collapse re))
                        = (prod(collapse(Leaf x))) * (prod(collapse li)) * (prod(collapse re))
        nach Induktionsvoraussetzung folgt
                        = (prodTree (Leaf x)) * (prodTree re) * (prodTree li)
                        = x * (prodTree re) * (prodTree li)
                        = prodTree (Branch x re li)



5.

  (a) (lx.(ly.xy(lx.x))) (lx.y) GV={y,x}, FV={y}
      =>a (lx.(ly1.xy1(lx.x))) (lx.y)
      =>b (ly1.(lx.y)y1(lx.x)) GV={/}, FV={y1}
      =>b (ly1.y(lx.x))
  (b) <F> = lfx.<if-then-else> (<iszero> x)
                                <1>
                               (<if-then-else> (<iszero>(<mod> x <2>))
                                               (<mult> x (f (<pred> x)))
                                               (<mult> (<mult> x x)(f (<pred> x))))
      Hinweis: Auf eine Probe von (x>0) wird aufgrund des Wertebereiches N verzichtet.

6.

  a...alpha
  g...gamma
  pi...phii
  R1: op(y, a, y)<-
  R2: op(a, y, y)<-
  R3: op(g(x), g(y), z) <- op(x, y, z)
  <- op(g^4(a), w, g^2(a))
  R3:
  p(x)=x1, p(y)=y1, p(z)=z1,
  p(x1)=g^3(a), p(w)=g(y1), p(z1)=g^2(a)
  <- op(g^3(a),y1,g^2(a))
  R3:
  p1(x)=x2, p1(y)=y2, p1(z)=z2,
  p1(x2)=g^2(a), p1(y1)=g(y2), p1(z2)=g^2(a)
  erste Möglichkeit:
  <- op(g^2(a),y2,g^2(a))
  R1:
  p2(y)=y3,
  p2(y3)=g^2(a), p2(y2)=a
  p:
  w->g(y1)
  w->g(g(y2))
  w->g(g(a))
  w->g^2(a)


  Zweite Möglichkeit:
  <- op(g^2(a),y2,g^2(a))
  R3:
  p2(x)=x3, p2(y)=y3, p2(z)=z3,
  p2(x3)=g(a), p2(y2)=g(y3), p2(z3)=g^2(a)
  <- op(g(a),y3,g^2(a))
  R3:
  p3(x)=x4, p3(y)=y4, p3(z)=z4,
  p3(x4)=a, p3(y3)=g(y4), p3(z4)=g^2(a)
  <- op(a,y4,g^2(a))
  R2: 
  p4(y)=y5,
  p4(y5)=y4, p4(y5)=g^2(a)
  p:
  w->g(y1)
  w->g(g(y2))
  w->g(g(g(y3)))
  w->g(g(g(g(y4))))
  w->g(g(g(g(g^2(a)))))
  w->g^6(a)

7.

  es muss gelten
  für W(E2) = {a^m b^n c^i d^n| n,m,i >= 0}
  für W(E3) = {a^m b^n c^n d^i| n,m,i >= 0}
  (Hinweis: Auch andere Kombinationen sind möglich. Bedingung: Inklusive W(E1) müssen
  in jeder Sprache 2 Buchstaben gleichoft vorkommen. Das Buchstabenpaar einer Sprache
  muss sich von dem der anderen beiden Sprachen unterscheiden)
  E2 = (V2, Sigma, S2, R2) mit
  V2 = {S2, A2}
  R2 = { S2 ::= {a} A2
         A2 ::= ( b A2 d | {c} ) }
  E3 = (V3, Sigma, S3, R3) mit
  V3 = {S3, A3}
  R3 = { S3 ::= {a} [A3] {d}
         A2 ::= ( b A3 c | b c ) }
  Sigma = {a,b,c,d}

8.

  (a) x -> 1
      y -> 2
      z -> 3
      1: LIT 1;
      2: STORE 3;
      3: READ 1;
      4: READ 2;
      5: LOAD 1;
      6: LOAD 2;
      7: GT;
      8: JMC 18;
      9: LOAD 2;
     10: LOAD 3;
     11: MULT;
     12: STORE 3;
     13: LOAD 1;
     14: LIT 1;
     15: SUB;
     16: STORE 1;
     17: JMP 5;
     18: WRITE 3;
  (b) ( 10,    e,  [1/2, 2/3, 3/0],  e,  e)
      ( 11,    2,  [1/2, 2/3, 3/0],  e,  e)
      ( 12,  3:2,  [1/2, 2/3, 3/0],  e,  e)
      ( 13,    1,  [1/2, 2/3, 3/0],  e,  e)
      ( 14,    e,  [1/2, 2/3, 3/0],  e,  e)
      ( 15,    3,  [1/2, 2/3, 3/0],  e,  e)
      ( 16,  2:3,  [1/2, 2/3, 3/0],  e,  e)
      ( 17,    1,  [1/2, 2/3, 3/0],  e,  e)
      ( 18,    e,  [1/1, 2/3, 3/0],  e,  e)
      ( 21,    e,  [1/1, 2/3, 3/0],  e,  e)
  (c) if (x1<x2) {x1=x2-x1;}
          else x1=x2;

9.

  d...delta
  g...gamma
  a...alpha
  o...Omega
  M0 = { d( d( g(x1), x2), g( g(a))), d( d( g(a), g( g(x1))), g(x3) }
  Dekomposition
  =>o  M1 = { ( d( g(x1),x2), d( g(a), g( g(x1)))),
              ( g( g(a)), g(x3) }
  Dekomposition
  =>*o M2 = { ( g(x1), g(a)),
              ( x2, g( g(x1))),
              ( g(a), x3) }
  Dekomposition
  =>o  M3 = { ( x1, a),
              ( x2, g( g(x1))),
              ( g(a), x3) }
  Substitution
  =>o  M4 = { ( x1, a),
              ( x2, g( g(a))),
              ( g(a), x3) }
  Vertauschung
  =>o  M5 = { ( x1, a),
              ( x2, g( g(a))),
              ( x3, g(a)) }
  -> allgemeinster Unifikator:
     p: x1 -> a
        x2 -> g^2(a)
        x3 -> g(a)