Prog:Klausur 2004-07-26 Vogler
Aus Tudwiki
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)
