# SYK 3

## Zadanie 1


$RD_{\circ}(1) = \{(x,?), (y,?), (z,?), (i,?), (t,?)\}$ - nie wiemy nic o niczym
$RD_{\bullet}(1) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$ - wiemy że w L=1 nadpisaliśmy x

$RD_{\circ}(2) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$ - to samo co poprzedni OUT
$RD_{\bullet}(2) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$ - wiemy że w L=2 nadpisaliśmy y

$RD_{\circ}(3) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$- to samo co poprzedni OUT
$RD_{\bullet}(3) = \{(x,1), (y,2), (z,?), (i,3), (t,?)\}$ - wiemy że w L=3 nadpisaliśmy i

$RD_{\circ}(4) = \{(x,1), (x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,?) (t,5)\}$ - x może pochodzić zarówno z 1 jak z 6 itd. dla reszty zmiennych
$RD_{\bullet}(4) = \{(x,1), (x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,?) (t,5)\}$ - nic się nie zmieniło

$RD_{\circ}(5) = RD_{\bullet}(4) = \{(x,1), (x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,?) (t,5)\}$
$RD_{\bullet}(5) = \{(x,1), (x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,5)\}$

$RD_{\circ}(6) = \{(x,1), (x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,5)\}$
$RD_{\bullet}(6) = \{(x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,5)\}$

$RD_{\circ}(7) = \{(x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,5)\}$
$RD_{\bullet}(7) = \{(x,6), (y,7), (z,?), (i,3), (i,8), (t,5)\}$

$RD_{\circ}(8) = \{(x,6), (y,7), (z,?), (i,3), (i,8), (t,5)\}$
$RD_{\bullet}(8) = \{(x,6), (y,7), (z,?), (i,8), (t,5)\}$

$RD_{\circ}(9) = RD_{\bullet}(4) = \{(x,1), (x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,?), (t,5)\}$
$RD_{\bullet}(9) = \{(x,1), (x,6), (y,9), (z,?), (i,3), (i,8), (t,?), (t,5)\}$ - wiemy że w L=9 nadpisaliśmy y

## Zadanie 2

$RD_{\circ}(1) = \{(x,?), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(1) = RD_{\circ}(1) \setminus \{(x,?)\} \bigcup \{(x,1)\} =\{(x,1), (y,?), (z,?), (i,?), (t,?)\}$

$RD_{\circ}(2) = RD_{\bullet}(1)$
$RD_{\bullet}(2) = RD_{\circ}(2) \setminus \{(y,?)\}\ \bigcup \{(y,2)\} = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$

$RD_{\circ}(3) = RD_{\bullet}(2)$
$RD_{\bullet}(3) = RD_{\circ}(3) \setminus \{(i,?)\}\ \bigcup \{(i,3)\} = \{(x,1), (y,2), (z,?), (i,3), (t,?)\}$

$RD_{\circ}(4) = RD_{\bullet}(3) \bigcup RD_{\bullet}(8) = \{(x,1), (x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,?) (t,5)\}$
$RD_{\bullet}(4) = RD_{\circ}(4)$

$RD_{\circ}(5) = RD_{\bullet}(4)$
$RD_{\bullet}(5) = RD_{\circ}(5) \setminus \{(t,?)\} \bigcup \{(t,5)\} = \{(x,1), (x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,5)\}$

$RD_{\circ}(6) = RD_{\bullet}(5)$
$RD_{\bullet}(6) = RD_{\circ}(6) \setminus \{(x,1), (x,6)\} \bigcup \{(x,6)\} = \{(x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,5)\}$

$RD_{\circ}(7) = RD_{\bullet}(6)$
$RD_{\bullet}(7) = RD_{\circ}(7) \setminus \{(y,7),(7,2)\} \bigcup \{(y,7)\} = \{(x,6), (y,7), (z,?), (i,3), (i,8), (t,5)\}$

$RD_{\circ}(8) = RD_{\bullet}(7)$
$RD_{\bullet}(8) = RD_{\circ}(8) \setminus \{(i,3),(i,8)\} \bigcup \{(i,8)\} = \{(x,6), (y,7), (z,?), (i,8), (t,5)\}$

$RD_{\circ}(9) = RD_{\bullet}(4)$
$RD_{\bullet}(9) = RD_{\circ}(9) \setminus \{(y,2),(y,7)\} \bigcup \{(y,9)\} = \{(x,1), (x,6), (y,9), (z,?), (i,3), (i,8), (t,?) (t,5)\}$

## Zadanie 3

---
### Etap 0:
$RD_{\circ}(1) = \emptyset$
$RD_{\bullet}(1) = \emptyset$
$RD_{\circ}(2) = \emptyset$
$RD_{\bullet}(2) = \emptyset$
$RD_{\circ}(3) = \emptyset$
$RD_{\bullet}(3) = \emptyset$
$RD_{\circ}(4) = \emptyset$
$RD_{\bullet}(4) = \emptyset$
$RD_{\circ}(5) = \emptyset$
$RD_{\bullet}(5) = \emptyset$
$RD_{\circ}(6) = \emptyset$
$RD_{\bullet}(6) = \emptyset$
$RD_{\circ}(7) = \emptyset$
$RD_{\bullet}(7) = \emptyset$
$RD_{\circ}(8) = \emptyset$
$RD_{\bullet}(8) = \emptyset$
$RD_{\circ}(9) = \emptyset$
$RD_{\bullet}(9) = \emptyset$

### Etap 1:
$RD_{\circ}(1) = \{(x,?), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(1) = \{(x,1)\}$
$RD_{\circ}(2) = \emptyset$
$RD_{\bullet}(2) = \{(y,2)\}$
$RD_{\circ}(3) = \emptyset$
$RD_{\bullet}(3) = \{(i,3)\}$
$RD_{\circ}(4) = \emptyset$
$RD_{\bullet}(4) = \emptyset$
$RD_{\circ}(5) = \emptyset$
$RD_{\bullet}(5) = \{(t,5)\}$$
$RD_{\circ}(6) = \emptyset$
$RD_{\bullet}(6) = \{(x,6)\}$
$RD_{\circ}(7) = \emptyset$
$RD_{\bullet}(7) = \{(y,7)\}$
$RD_{\circ}(8) = \emptyset$
$RD_{\bullet}(8) = \{(i,8)\}$
$RD_{\circ}(9) = \emptyset$
$RD_{\bullet}(9) = \{(y,9)\}$

### Etap 2:
$RD_{\circ}(1) = \{(x,?), (y,?), (z,?), (i,?), (t,?)\}$ // NIC
$RD_{\bullet}(1) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\circ}(2) = \{(x,1)\}$
$RD_{\bullet}(2) = \{(y,2)\}$
$RD_{\circ}(3) = \{(y,2)\}$
$RD_{\bullet}(3) = \{(i,3)\}$
$RD_{\circ}(4) = \{(i,3),(i,8)\}$
$RD_{\bullet}(4) = \emptyset$
$RD_{\circ}(5) = \emptyset$
$RD_{\bullet}(5) = \{(t,5)\}$
$RD_{\circ}(6) = \{(t,5)\}$
$RD_{\bullet}(6) = \{(x,6)\}$
$RD_{\circ}(7) = \{(x,6)\}$
$RD_{\bullet}(7) = \{(y,7)\}$
$RD_{\circ}(8) = \{(y,7)\}$
$RD_{\bullet}(8) = \{(i,8)\}$
$RD_{\circ}(9) = \emptyset$
$RD_{\bullet}(9) = \{(y,9)\}$

### Etap 3:
$RD_{\circ}(1) = \{(x,?), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(1) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\circ}(2) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(2) = \{(x,1),(y,2)\}$
$RD_{\circ}(3) = \{(y,2)\}$
$RD_{\bullet}(3) = \{(y,2),(i,3)\}$
$RD_{\circ}(4) = \{(i,3),(i,8)\}$
$RD_{\bullet}(4) = \{(i,3),(i,8)\}$
$RD_{\circ}(5) = \emptyset$
$RD_{\bullet}(5) = \{(t,5)\}$
$RD_{\circ}(6) = \{(t,5)\}$
$RD_{\bullet}(6) = \{(t,5)(x,6)\}$
$RD_{\circ}(7) = \{(x,6)\}$
$RD_{\bullet}(7) = \{(x,6),(y,7)\}$
$RD_{\circ}(8) = \{(y,7)\}$
$RD_{\bullet}(8) = \{(y,7),(i,8)\}$
$RD_{\circ}(9) = \emptyset$
$RD_{\bullet}(9) = \{(y,9)\}$

### Etap 4:
$RD_{\circ}(1) = \{(x,?), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(1) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\circ}(2) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(2) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$
$RD_{\circ}(3) = \{(x,1), (y,2)\}$
$RD_{\bullet}(3) = \{(y,2),(i,3)\}$
$RD_{\circ}(4) = \{(i,3),(i,8),(y,2),(y,7)\}$
$RD_{\bullet}(4) = \{(i,3),(i,8)\}$
$RD_{\circ}(5) = \{(i,3),(i,8)\}$
$RD_{\bullet}(5) = \{(t,5)\}$
$RD_{\circ}(6) = \{(t,5)\}$
$RD_{\bullet}(6) = \{(t,5)(x,6)\}$
$RD_{\circ}(7) = \{(t,5),(x,6)\}$
$RD_{\bullet}(7) = \{(x,6),(y,7)\}$
$RD_{\circ}(8) = \{(x,6),(y,7)\}$
$RD_{\bullet}(8) = \{(y,7),(i,8)\}$
$RD_{\circ}(9) = \{(i,3),(i,8)\}$
$RD_{\bullet}(9) = \{(y,9)\}$

### Etap 5:
$RD_{\circ}(1) = \{(x,?), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(1) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\circ}(2) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(2) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$
$RD_{\circ}(3) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(3) = \{(x,1),(y,2),(i,3)\}$
$RD_{\circ}(4) = \{(i,3),(i,8),(y,2),(y,7)\}$
$RD_{\bullet}(4) = \{(i,3),(i,8),(y,2),(y,7)\}$
$RD_{\circ}(5) = \{(i,3),(i,8)\}$
$RD_{\bullet}(5) = \{(i,3),(i,8),(t,5)\}$
$RD_{\circ}(6) = \{(t,5)\}$
$RD_{\bullet}(6) = \{(t,5)(x,6)\}$
$RD_{\circ}(7) = \{(t,5),(x,6)\}$
$RD_{\bullet}(7) = \{(t,5),(x,6),(y,7)\}$
$RD_{\circ}(8) = \{(x,6),(y,7)\}$
$RD_{\bullet}(8) = \{(x,6),(y,7),(i,8)\}$
$RD_{\circ}(9) = \{(i,3),(i,8)\}$
$RD_{\bullet}(9) = \{(i,3),(i,8),(y,9)\}$

### Etap 6:
$RD_{\circ}(1) = \{(x,?), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(1) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\circ}(2) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(2) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$
$RD_{\circ}(3) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(3) = \{(x,1), (y,2), (z,?), (i,3), (t,?)\}$
$RD_{\circ}(4) = \{(x,1),(x,6), (i,3),(i,8),(y,2),(y,7)\}$
$RD_{\bullet}(4) = \{(i,3),(i,8),(y,2),(y,7)\}$
$RD_{\circ}(5) = \{(i,3),(i,8),(y,2),(y,7)\}$
$RD_{\bullet}(5) = \{(i,3),(i,8),(t,5)\}$
$RD_{\circ}(6) = \{(i,3),(i,8),(t,5)\}$
$RD_{\bullet}(6) = \{(t,5)(x,6)\}$
$RD_{\circ}(7) = \{(t,5),(x,6)\}$
$RD_{\bullet}(7) = \{(t,5),(x,6),(y,7)\}$
$RD_{\circ}(8) = \{(t,5),(x,6),(y,7)\}$
$RD_{\bullet}(8) = \{(x,6),(y,7),(i,8)\}$
$RD_{\circ}(9) = \{(i,3),(i,8),(y,2),(y,7)\}$
$RD_{\bullet}(9) = \{(i,3),(i,8),(y,9)\}$

### Etap 7:
$RD_{\circ}(1) = \{(x,?), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(1) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\circ}(2) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(2) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$
$RD_{\circ}(3) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(3) = \{(x,1), (y,2), (z,?), (i,3), (t,?)\}$
$RD_{\circ}(4) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(y,2),(y,7)\}$
$RD_{\bullet}(4) = \{(x,1),(x,6), (i,3),(i,8),(y,2),(y,7)\}$
$RD_{\circ}(5) = \{(i,3),(i,8),(y,2),(y,7)\}$
$RD_{\bullet}(5) = \{(i,3),(i,8),(y,2),(y,7),(t,5)\}$
$RD_{\circ}(6) = \{(i,3),(i,8),(t,5)\}$
$RD_{\bullet}(6) = \{(i,3),(i,8),(t,5)(x,6)\}$
$RD_{\circ}(7) = \{(t,5),(x,6)\}$
$RD_{\bullet}(7) = \{(t,5),(x,6),(y,7)\}$
$RD_{\circ}(8) = \{(t,5),(x,6),(y,7)\}$
$RD_{\bullet}(8) = \{(t,5),(x,6),(y,7),(i,8)\}$
$RD_{\circ}(9) = \{(i,3),(i,8),(y,2),(y,7)\}$
$RD_{\bullet}(9) = \{(i,3),(i,8),(y,9)\}$

### Etap 8:
$RD_{\circ}(1) = \{(x,?), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(1) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\circ}(2) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(2) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$
$RD_{\circ}(3) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(3) = \{(x,1), (y,2), (z,?), (i,3), (t,?)\}$
$RD_{\circ}(4) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$
$RD_{\bullet}(4) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(y,2),(y,7)\}$
$RD_{\circ}(5) = \{(x,1),(x,6), (i,3),(i,8),(y,2),(y,7)\}$
$RD_{\bullet}(5) = \{(i,3),(i,8),(y,2),(y,7),(t,5)\}$
$RD_{\circ}(6) = \{(i,3),(i,8),(y,2),(y,7),(t,5)\}$
$RD_{\bullet}(6) = \{(i,3),(i,8),(t,5),(x,6)\}$
$RD_{\circ}(7) = \{(i,3),(i,8),(t,5)(x,6)\}$
$RD_{\bullet}(7) = \{(t,5),(x,6),(y,7)\}$
$RD_{\circ}(8) = \{(t,5),(x,6),(y,7)\}$
$RD_{\bullet}(8) = \{(t,5),(x,6),(y,7),(i,8)\}$
$RD_{\circ}(9) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(y,2),(y,7)\}$
$RD_{\bullet}(9) = \{(i,3),(i,8),(y,9)\}$

### Etap 9:
$RD_{\circ}(1) = \{(x,?), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(1) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\circ}(2) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(2) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$
$RD_{\circ}(3) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(3) = \{(x,1), (y,2), (z,?), (i,3), (t,?)\}$
$RD_{\circ}(4) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$
$RD_{\bullet}(4) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$
$RD_{\circ}(5) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(y,2),(y,7)\}$
$RD_{\bullet}(5) = \{(x,1),(x,6), (i,3),(i,8),(y,2),(y,7),(t,5)\}$
$RD_{\circ}(6) = \{(i,3),(i,8),(y,2),(y,7),(t,5)\}$
$RD_{\bullet}(6) = \{(i,3),(i,8),(t,5),(y,2),(y,7),(x,6)\}$
$RD_{\circ}(7) = = \{(i,3),(i,8),(t,5),(x,6)\}$
$RD_{\bullet}(7) = \{(i,3),(i,8),(t,5),(x,6),(y,7)\}$
$RD_{\circ}(8) = \{(t,5),(x,6),(y,7)\}$
$RD_{\bullet}(8) = \{(t,5),(x,6),(y,7),(i,8)\}$
$RD_{\circ}(9) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(y,2),(y,7)\}$
$RD_{\bullet}(9) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(y,9)\}$

### Etap 10:
$RD_{\circ}(1) = \{(x,?), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(1) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\circ}(2) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(2) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$
$RD_{\circ}(3) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(3) = \{(x,1), (y,2), (z,?), (i,3), (t,?)\}$
$RD_{\circ}(4) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$
$RD_{\bullet}(4) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$
$RD_{\circ}(5) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$
$RD_{\bullet}(5) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,5),(y,2),(y,7)\}$
$RD_{\circ}(6) = \{(x,1),(x,6), (i,3),(i,8),(y,2),(y,7),(t,5)\}$
$RD_{\bullet}(6) = \{(i,3),(i,8),(t,5),(y,2),(y,7),(x,6)\}$
$RD_{\circ}(7) = \{(i,3),(i,8),(t,5),(y,2),(y,7),(x,6)\}$
$RD_{\bullet}(7) = \{(i,3),(i,8),(t,5),(x,6),(y,7)\}$
$RD_{\circ}(8) = = \{(i,3),(i,8),(t,5),(x,6),(y,7)\}$
$RD_{\bullet}(8) = \{(t,5),(x,6),(y,7),(i,8)\}$
$RD_{\circ}(9) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$
$RD_{\bullet}(9) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(y,9)\}$

### Etap 11:
$RD_{\circ}(1) = \{(x,?), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(1) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\circ}(2) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(2) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$
$RD_{\circ}(3) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$
$RD_{\bullet}(3) = \{(x,1), (y,2), (z,?), (i,3), (t,?)\}$
$RD_{\circ}(4) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$
$RD_{\bullet}(4) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$
$RD_{\circ}(5) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$
$RD_{\bullet}(5) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,5),(y,2),(y,7)\}$
$RD_{\circ}(6) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,5),(y,2),(y,7)\}$
$RD_{\bullet}(6) = \{(x,6), (i,3),(i,8),(y,2),(y,7),(t,5)\}$
$RD_{\circ}(7) = \{(i,3),(i,8),(t,5),(y,2),(y,7),(x,6)\}$
$RD_{\bullet}(7) = \{(i,3),(i,8),(t,5),(y,7),(x,6)\}$
$RD_{\circ}(8) = \{(i,3),(i,8),(t,5),(x,6),(y,7)\}$
$RD_{\bullet}(8) = \{(t,5),(x,6),(y,7),(i,8)\}$
$RD_{\circ}(9) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$
$RD_{\bullet}(9) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,9)\}$

### Etap 12:
$RD_{\circ}(1) = \{(x,?), (y,?), (z,?), (i,?), (t,?)\}$ OK
$RD_{\bullet}(1) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$ OK
$RD_{\circ}(2) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$ OK
$RD_{\bullet}(2) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$ OK
$RD_{\circ}(3) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$ OK
$RD_{\bullet}(3) = \{(x,1), (y,2), (z,?), (i,3), (t,?)\}$ OK
$RD_{\circ}(4) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(4) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\circ}(5) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(5) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,5),(y,2),(y,7)\}$ OK
$RD_{\circ}(6) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(6) = \{(x,6),(z,?),(i,3),(i,8),(t,5),(y,2),(y,7)\}$ OK
$RD_{\circ}(7) = \{(i,3),(i,8),(t,5),(y,2),(y,7),(x,6)\}$
$RD_{\bullet}(7) = \{(i,3),(i,8),(t,5),(y,7),(x,6)\}$
$RD_{\circ}(8) = \{(i,3),(i,8),(t,5),(y,7),(x,6)\}$
$RD_{\bullet}(8) = \{(t,5),(x,6),(y,7),(i,8)\}$

$RD_{\circ}(9) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(9) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,9)\}$ OK

### Etap 13:
$RD_{\circ}(1) = \{(x,?), (y,?), (z,?), (i,?), (t,?)\}$ OK
$RD_{\bullet}(1) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$ OK
$RD_{\circ}(2) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$ OK
$RD_{\bullet}(2) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$ OK
$RD_{\circ}(3) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$ OK
$RD_{\bullet}(3) = \{(x,1), (y,2), (z,?), (i,3), (t,?)\}$ OK
$RD_{\circ}(4) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(4) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\circ}(5) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(5) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,5),(y,2),(y,7)\}$ OK
$RD_{\circ}(6) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(6) = \{(x,6),(z,?),(i,3),(i,8),(t,5),(y,2),(y,7)\}$ OK
$RD_{\circ}(7) = \{(i,3),(z,?),(i,8),(t,5),(y,2),(y,7),(x,6)\}$ OK
$RD_{\bullet}(7) = \{(i,3),(i,8),(t,5),(y,7),(x,6)\}$
$RD_{\circ}(8) = \{(i,3),(i,8),(t,5),(y,7),(x,6)\}$
$RD_{\bullet}(8) = \{(t,5),(x,6),(y,7),(i,8)\}$

$RD_{\circ}(9) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(9) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,9)\}$ OK

### Etap 14:
$RD_{\circ}(1) = \{(x,?), (y,?), (z,?), (i,?), (t,?)\}$ OK
$RD_{\bullet}(1) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$ OK
$RD_{\circ}(2) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$ OK
$RD_{\bullet}(2) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$ OK
$RD_{\circ}(3) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$ OK
$RD_{\bullet}(3) = \{(x,1), (y,2), (z,?), (i,3), (t,?)\}$ OK
$RD_{\circ}(4) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(4) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\circ}(5) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(5) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,5),(y,2),(y,7)\}$ OK
$RD_{\circ}(6) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(6) = \{(x,6),(z,?),(i,3),(i,8),(t,5),(y,2),(y,7)\}$ OK
$RD_{\circ}(7) = \{(i,3),(z,?),(i,8),(t,5),(y,2),(y,7),(x,6)\}$ OK
$RD_{\bullet}(7) = \{(i,3),(z,?),(i,8),(t,5),(y,7),(x,6)\}$ OK
$RD_{\circ}(8) = \{(i,3),(i,8),(t,5),(y,7),(x,6)\}$
$RD_{\bullet}(8) = \{(t,5),(x,6),(y,7),(i,8)\}$

$RD_{\circ}(9) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(9) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,9)\}$ OK

### Etap 15:
$RD_{\circ}(1) = \{(x,?), (y,?), (z,?), (i,?), (t,?)\}$ OK
$RD_{\bullet}(1) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$ OK
$RD_{\circ}(2) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$ OK
$RD_{\bullet}(2) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$ OK
$RD_{\circ}(3) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$ OK
$RD_{\bullet}(3) = \{(x,1), (y,2), (z,?), (i,3), (t,?)\}$ OK
$RD_{\circ}(4) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(4) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\circ}(5) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(5) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,5),(y,2),(y,7)\}$ OK
$RD_{\circ}(6) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(6) = \{(x,6),(z,?),(i,3),(i,8),(t,5),(y,2),(y,7)\}$ OK
$RD_{\circ}(7) = \{(i,3),(z,?),(i,8),(t,5),(y,2),(y,7),(x,6)\}$ OK
$RD_{\bullet}(7) = \{(i,3),(z,?),(i,8),(t,5),(y,7),(x,6)\}$ OK
$RD_{\circ}(8) = \{(i,3),(z,?),(i,8),(t,5),(y,7),(x,6)\}$ OK
$RD_{\bullet}(8) = \{(t,5),(x,6),(y,7),(i,8)\}$

$RD_{\circ}(9) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(9) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,9)\}$ OK

### Etap 16:
$RD_{\circ}(1) = \{(x,?), (y,?), (z,?), (i,?), (t,?)\}$ OK
$RD_{\bullet}(1) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$ OK
$RD_{\circ}(2) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$ OK
$RD_{\bullet}(2) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$ OK
$RD_{\circ}(3) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$ OK
$RD_{\bullet}(3) = \{(x,1), (y,2), (z,?), (i,3), (t,?)\}$ OK
$RD_{\circ}(4) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(4) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\circ}(5) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(5) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,5),(y,2),(y,7)\}$ OK
$RD_{\circ}(6) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(6) = \{(x,6),(z,?),(i,3),(i,8),(t,5),(y,2),(y,7)\}$ OK
$RD_{\circ}(7) = \{(i,3),(z,?),(i,8),(t,5),(y,2),(y,7),(x,6)\}$ OK
$RD_{\bullet}(7) = \{(i,3),(z,?),(i,8),(t,5),(y,7),(x,6)\}$ OK
$RD_{\circ}(8) = \{(i,3),(z,?),(i,8),(t,5),(y,7),(x,6)\}$ OK
$RD_{\bullet}(8) = \{(t,5),(z,?),(x,6),(y,7),(i,8)\}$ OK

$RD_{\circ}(9) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(9) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,9)\}$ OK

### Etap 17 (nic się nie zmieniło):
KONIEC
$RD_{\circ}(1) = \{(x,?), (y,?), (z,?), (i,?), (t,?)\}$ OK
$RD_{\bullet}(1) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$ OK
$RD_{\circ}(2) = \{(x,1), (y,?), (z,?), (i,?), (t,?)\}$ OK
$RD_{\bullet}(2) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$ OK
$RD_{\circ}(3) = \{(x,1), (y,2), (z,?), (i,?), (t,?)\}$ OK
$RD_{\bullet}(3) = \{(x,1), (y,2), (z,?), (i,3), (t,?)\}$ OK
$RD_{\circ}(4) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(4) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\circ}(5) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(5) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,5),(y,2),(y,7)\}$ OK
$RD_{\circ}(6) = \{(x,1),(x,6),(z,?),(i,3),(i,8),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(6) = \{(x,6),(z,?),(i,3),(i,8),(t,5),(y,2),(y,7)\}$ OK
$RD_{\circ}(7) = \{(i,3),(z,?),(i,8),(t,5),(y,2),(y,7),(x,6)\}$ OK
$RD_{\bullet}(7) = \{(i,3),(z,?),(i,8),(t,5),(y,7),(x,6)\}$ OK
$RD_{\circ}(8) = \{(i,3),(z,?),(i,8),(t,5),(y,7),(x,6)\}$ OK
$RD_{\bullet}(8) = \{(t,5),(z,?),(x,6),(y,7),(i,8)\}$ OK
$RD_{\circ}(9) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,2),(y,7)\}$ OK
$RD_{\bullet}(9) = \{(x,1),(x,6), (z,?),(i,3),(i,8),(t,?),(t,5),(y,9)\}$ OK

## Zadanie 4
1) Zaznaczyć w równaniach z zadania 1. kill - w miejscach \ {...}, gen w miejscach $\cup$

$kill_{RD}([x:=0]^{1}) = \{(x,?),(x,1),(x,6)\}$
$kill_{RD}([y:=1]^{2}) = \{(y,?),(y,2),(y,7),(y,9)\}$
$kill_{RD}([i:=1]^{3}) = \{(i,?),(i,3),(i,8)\}$
$kill_{RD}([i<z]^{4}) = \emptyset$
$kill_{RD}([t:=x+y]^{5}) = \{(t,?)\}$
$kill_{RD}([x:=y]^{6}) = \{(x,?),(x,1),(x,6)\}$
$kill_{RD}([y:=t]^{7}) = \{(y,?),(y,2),(y,7),(y,9)\}$
$kill_{RD}([i:=i+1]^{8}) = \{(i,?),(i,3),(i,8)\}$
$kill_{RD}([y:=x]^{9}) = \{(y,?),(y,2),(y,7),(y,9)\}$

$gen_{RD}([x:=0]^{1}) = \{(x,1)\}$
$gen_{RD}([y:=1]^{2}) = \{(y,2)\}$
$gen_{RD}([i:=1]^{3}) = \{(i,3)\}$
$gen_{RD}([i<z]^{4}) = \emptyset$
$gen_{RD}([t:=x+y]^{5}) = \{(t,5)\}$
$gen_{RD}([x:=y]^{6}) = \{(x,6)\}$
$gen_{RD}([y:=t]^{7}) = \{(y,7)\}$
$gen_{RD}([i:=i+1]^{8}) = \{(i,8)\}$
$gen_{RD}([y:=x]^{9}) = \{(y,9)\}$

2) Analogicznie jak przy wykonaniu przypisania do zmiennej x:
$kill_{RD}([read(x)]^{l}) = \{(x,?)\} \cup \{(x, l') \,|\, B' jest \, przypisaniem\, do \, x\}$
$gen_{RD}([read(x)]^{l}) = \{(x,l)\}$

3) Algorytm wyliczający zbiory RD(l).


1. Ustawiam $RD_{exit}$ dla każdego wierzchołka (bloczka z instrukcją) na zbiór pusty.
2. Dodaję wszystkie wierzchołki do zbioru $Changed$ (zbiór wierzchołków dla których zbiory RD mogły ulec zmianie).
3. Dopóki $!Changed.empty()$:
a) wybieram wierzchołek $x$ ze zbioru $Changed$ i usuwam go z $Changed$
b) Ustawiam $RD_{entry}(x)$ na zbiór pusty
c) Przechodzę po wszystkich "przodkach" $x$ (wierzchołkach posiadających krawędź wychodzącą kończącą się w $x$) i uaktualniam $RD_{entry}(x)$ licząc sumę zbiorów.
d) Zapisuję pomocniczo starą wartość $RD_{exit}(x)$, aby móc porównać ją z nową.
e) Obliczam nową wartość $RD_{entry}(x)$ przy użyciu funkcji $kill$ i $gen$.
f) Jeżeli nowa wartość $RD_{entry}(x)$ różni się od starej:
aa) Dodaję wszystkie "dzieci" $x$ do zbioru $Changed$

## Zadanie 5

$[𝑥 : = 1]^1$
𝑖𝑓 $[𝑥 > 0]^2$𝑡ℎ𝑒𝑛
$\qquad[𝑦 := 1]^3$
𝑒𝑙𝑠𝑒
$\qquad[𝑦 := −1]^4$
𝑒𝑛𝑑
$[𝑧 : = 𝑦]^5$

$RD_{\bullet}(1) = RD_{\circ}(1) \setminus \{(x, l) | l \in Lab\} \cup \{(x, 1)\}$
$RD_{\bullet}(2) = RD_{\circ}(2)$
$RD_{\bullet}(3) = RD_{\circ}(3) \setminus \{(y, l) | l \in Lab\} \cup \{(y, 3)\}$
$RD_{\bullet}(4) = RD_{\circ}(4) \setminus \{(y, l) | l \in Lab\} \cup \{(y, 4)\}$
$RD_{\bullet}(5) = RD_{\circ}(5) \setminus \{(z, l) | l \in Lab\} \cup \{(z, 5)\}$

$RD_{\circ}(1) = \{(x,?), (y,?), (z,?)\}$
$RD_{\circ}(2) = RD_{\bullet}(1)$
$RD_{\circ}(3) = RD_{\bullet}(2)$
$RD_{\circ}(4) = RD_{\bullet}(2)$
$RD_{\circ}(5) = RD_{\bullet}(3) \cup RD_{\bullet}(4)$

---
|Równania|początkowy stan||
|-|-|-|
$RD_{\circ}(1) = \{(x,?), (y,?), (z,?)\}$ | $\{(x,?), (y,?), (z,?)\}$ | $\{(x,?), (y,?), (z,?)\}$
$RD_{\bullet}(1) = RD_{\circ}(1) \setminus \{(x, l) \| l \in Lab\} \cup \{(x, 1)\}$ | $\emptyset$ | $\{(x,1), (y,?), (z,?)\}$
$RD_{\circ}(2) = RD_{\bullet}(1)$ | $\emptyset$ | $\{(x,1), (y,?), (z,?)\}$
$RD_{\bullet}(2) = RD_{\circ}(2)$ | $\emptyset$ | $\{(x,1), (y,?), (z,?)\}$
$RD_{\circ}(3) = RD_{\bullet}(2)$ | $\emptyset$ | $\{(x,1), (y,?), (z,?)\}$
$RD_{\bullet}(3) = RD_{\circ}(3) \setminus \{(y, l) \| l \in Lab\} \cup \{(y, 3)\}$ | $\emptyset$ | $\{(x,1), (y,3), (z,?)\}$
$RD_{\circ}(4) = RD_{\bullet}(2)$ | $\emptyset$ | $\{(x,1), (y,?), (z,?)\}$
$RD_{\bullet}(4) = RD_{\circ}(4) \setminus \{(y, l) \| l \in Lab\} \cup \{(y, 4)\}$ | $\emptyset$ | $\{(x,1), (y,4), (z,?)\}$
$RD_{\bullet}(5) = RD_{\circ}(5) \setminus \{(z, l) \| l \in Lab\} \cup \{(z, 5)\}$ | $\emptyset$ | $\{(x,1), (y,3), (y,4), (z,?)\}$
$RD_{\circ}(5) = RD_{\bullet}(3) \cup RD_{\bullet}(4)$ | $\emptyset$ | $\{(x,1), (y,3), (y,4), (z,?)\}$

$RD_{\circ}(1) = \{(x,?), (y,?), (z,?)\}$
$RD_{\bullet}(1) = \{(x,1), (y,?), (z,?)\}$
$RD_{\circ}(2) = \{(x,1), (y,?), (z,?)\}$
$RD_{\bullet}(2) = \{(x,1), (y,?), (z,?)\}$
$RD_{\circ}(3) = \{(x,1), (y,?), (z,?)\}$
$RD_{\bullet}(3) = \{(x,1), (y,3), (z,?)\}$
$RD_{\circ}(4) = \{(x,1), (y,?), (z,?)\}$
$RD_{\bullet}(4) = \{(x,1), (y,4), (z,?)\}$
$RD_{\circ}(5) = \{(x,1), (y,3), (y,4), (z,?)\}$
$RD_{\bullet}(5) = \{(x,1), (y,3), (y,4), (z,5)\}$

Użycie żadnego równania nie zmieni wartośći RD, więc algorytm stałopunktowy kończy działanie

W faktycznym wykonaniu warunek
$[x>0]^2$ będzie zawsze prawdziwy, bo x będzie równy 1, więc instrukcja
$[y := 1]^3$ wykona się zawsze
$[y := 1]^4$ nigdy się nie wykona
Więc na wejściu do instrukcji 5 y będzie miał na pewno ostatnie zmiany pochodzące z instrukcji 3

## Zadanie 6
Zmienna jest żywa przy wyjściu z danej etykiety jeżeli
znajduje się jakaś ścieżka z wyjścia tej etykiety do
użycia tej zmiennej (które nie jest zredefiniowaniem jej)

Celem analizy zmiennych żywych jest ustalenie dla każdego punktu programu, które zmienne mogą być żywe.
(Analizujemy w których momentach wykonania programu wartość danej zmiennej ma znaczenie dla dalszego przebiegu programu.)

---

---

Zasady gen/kill:

---
rozpatrywany program

$[x := 0]^1$
$[y := 1]^2$
$[i := 1]^3$
$𝑤ℎ𝑖𝑙𝑒 [i < z]^4$ 𝑑𝑜
$\qquad[t := x + y]^5$
$\qquad[x := y]^6$
$\qquad[y := t]^7$
$\qquad[i := i + 1]^8$
𝑜𝑑
$[y := x]^9$

---

Rozpisany układ 18 równań:
$LV_{entry}(1) = LV_{exit}(1) \setminus \{x\}$
$LV_{entry}(2) = LV_{exit}(2) \setminus \{y\}$
$LV_{entry}(3) = LV_{exit}(3) \setminus \{i\}$
$LV_{entry}(4) = LV_{exit}(4)\cup \{i,z\}$
$LV_{entry}(5) = (LV_{exit}(5) \setminus \{t\})\cup \{x,y\}$
$LV_{entry}(6) = (LV_{exit}(6) \setminus \{x\})\cup \{y\}$
$LV_{entry}(7) = (LV_{exit}(7) \setminus \{y\})\cup \{t\}$
$LV_{entry}(8) = (LV_{exit}(8) \setminus \{i\})\cup \{i\}$
$LV_{entry}(9) = LV_{exit}(9) \cup \{x\}$ tu trzeba to co w OUT9, ale również x

$LV_{exit}(1) = LV_{entry}(2)$
$LV_{exit}(2) = LV_{entry}(3)$
$LV_{exit}(3) = LV_{entry}(4)$
$LV_{exit}(4) = LV_{entry}(5) \cup LV_{entry}(9)$
$LV_{exit}(5) = LV_{entry}(6)$
$LV_{exit}(6) = LV_{entry}(7)$
$LV_{exit}(7) = LV_{entry}(8)$
$LV_{exit}(8) = LV_{entry}(4)$
$LV_{exit}(9) = \emptyset$ tu już nie potrzeba nic (od tego zaczynamy w rozwiązywaniu układu)

---
Rozwiązanie metodą stałopunktową

| | iteracja 1. alg | iteracja 2. alg |
|---|---|---|
$LV_{exit}(9)$ | $\emptyset$
$LV_{entry}(9)$ | $\{x\}$
$LV_{exit}(8)$ | $\emptyset$ | $\{\textbf{i},\textbf{x},\textbf{y},\textbf{z}\}$
$LV_{entry}(8)$ | $\{x,i\}$ | $\{i,x,\textbf{y},\textbf{z}\}$
$LV_{exit}(7)$ | $\{x,i\}$ | $\{i,x,\textbf{y},\textbf{z}\}$
$LV_{entry}(7)$ | $\{x,i,t\}$ | $\{i,x,t,\textbf{z}\}$
$LV_{exit}(6)$ | $\{x,i,t\}$ | $\{i,t,x,\textbf{z}\}$
$LV_{entry}(6)$ | $\{i,t,y\}$ | $\{i,y,y,\textbf{z}\}$
$LV_{exit}(5)$ | $\{i,t,y\}$ | $\{i,t,y,\textbf{z}\}$
$LV_{entry}(5)$ | $\{i,x,y\}$ | $\{i,x,y,\textbf{z}\}$
$LV_{exit}(4)$ | $\{i,x,y\}$ | $\{i,x,y,z\}$
$LV_{entry}(4)$ | $\{i,x,y,z\}$ | $\{i,x,y,z\}$
$LV_{exit}(3)$ | $\{i,x,y,z\}$
$LV_{entry}(3)$ | $\{x,y,z\}$
$LV_{exit}(2)$ | $\{x,y,z\}$
$LV_{entry}(2)$ | $\{x,z\}$
$LV_{exit}(1)$ | $\{x,z\}$
$LV_{entry}(1)$ | $\{z\}$

## Zadanie 7
"Use-Definition Chain" to struktura danych która dla każdego wystąpienia zmiennej w programie trzyma informację o miejscach, w których mogła być zdefiniowana bez jej późniejszej zmiany aż do rozważanego wystąpienia. Jest używana do statycznej analizy kodu - służyć może między innymi do pewnych optymalizacji w procesie kompilacji.

Opisywane analizy przedstawię w postaci:
$UD\texttt{-}chain(VAR,LABEL) = \{L1, L2, ...\}$

Przypomnijmy kod z zadania 1:

Nie rozpisujemy analiz typu $UD\texttt{-}chain(VAR,LAB)$ gdy wartość zmiennej $VAR$ nie jest istotna dla instrukcji oznaczonej $LAB$ (ich wartość można symbolicznie zapisać przez $\emptyset$)

Analizując więc instrukcje które korzystają z wartości jakichś zmiennych (tj. inne niż ... := b dla b będącą stałą):
$UD\texttt{-}chain(i,4) = ...$
$UD\texttt{-}chain(z,4) = ...$

$UD\texttt{-}chain(x,5) = ...$
$UD\texttt{-}chain(y,5) = ...$

$UD\texttt{-}chain(y,6) = ...$

$UD\texttt{-}chain(t,7) = ...$

$UD\texttt{-}chain(i,8) = ...$

$UD\texttt{-}chain(x,9) = ...$

Przypomnijmy wartości $RD_{\circ}(4)$, $RD_{\circ}(5)$, $RD_{\circ}(6)$, $RD_{\circ}(7)$, $RD_{\circ}(8)$, $RD_{\circ}(9)$ (bo tylko dla instrukcji 4, 5, 6, 7, 8, 9 mamy wyrażenia takiego typu jak opisałem wyżej):

$RD_{\circ}(4) = \{(x,1), (x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,?) (t,5)\}$
$RD_{\circ}(5) = \{(x,1), (x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,?) (t,5)\}$
$RD_{\circ}(6) = \{(x,1), (x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,5)\}$
$RD_{\circ}(7) = \{(x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,5)\}$
$RD_{\circ}(8) = \{(x,6), (y,7), (z,?), (i,3), (i,8), (t,5)\}$
$RD_{\circ}(9) = \{(x,1), (x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,?), (t,5)\}$

Mamy zatem:
$UD\texttt{-}chain(i,4) = \{3, 8\}$
$UD\texttt{-}chain(z,4) = \{?\}$
$UD\texttt{-}chain(x,5) = \{1, 6\}$
$UD\texttt{-}chain(y,5) = \{2, 7\}$
$UD\texttt{-}chain(y,6) = \{2, 7\}$
$UD\texttt{-}chain(t,7) = \{5\}$
$UD\texttt{-}chain(i,8) = \{3, 8\}$
$UD\texttt{-}chain(x,9) = \{1, 6\}$


## Zadanie 8



### Równania
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = AE_{exit}(1)$
$AE_{entry}(3) = AE_{exit}(2)$
$AE_{entry}(4) = AE_{exit}(3) \cap AE_{exit}(8)$- możemy być pewni tylko tego co jest wspólne
$AE_{entry}(5) = AE_{exit}(4)$
$AE_{entry}(6) = AE_{exit}(5)$
$AE_{entry}(7) = AE_{exit}(6)$
$AE_{entry}(8) = AE_{exit}(7)$
$AE_{entry}(9) = AE_{exit}(4)$

$AE_{exit}(1) = AE_{entry}(1)$
$AE_{exit}(2) = AE_{entry}(2)$
$AE_{exit}(3) = AE_{entry}(3)$
$AE_{exit}(4) = AE_{entry}(4)$
$AE_{exit}(5) = AE_{entry}(5) \cup \{x+y\}$
$AE_{exit}(6) = AE_{entry}(6) \setminus \{x+y\}$
$AE_{exit}(7) = AE_{entry}(7) \setminus \{x+y\}$
$AE_{exit}(8) = AE_{entry}(8) \setminus \{i+1\}$
$AE_{exit}(9) = AE_{entry}(9)$

### Algorytm stałopunktowy
Stan początkowy - wszystkie zbiory są puste

$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = AE_{exit}(1) = \emptyset$
$AE_{entry}(3) = AE_{exit}(2) = \emptyset$
$AE_{entry}(4) = AE_{exit}(3) \cap AE_{exit}(8) = \emptyset$
$AE_{entry}(5) = AE_{exit}(4) = \emptyset$
$AE_{entry}(6) = AE_{exit}(5) = \{x+y\}$
$AE_{entry}(7) = AE_{exit}(6) = \emptyset$
$AE_{entry}(8) = AE_{exit}(7) = \emptyset$
$AE_{entry}(9) = AE_{exit}(4) = \emptyset$

$AE_{exit}(1) = AE_{entry}(1) = \emptyset$
$AE_{exit}(2) = AE_{entry}(2) = \emptyset$
$AE_{exit}(3) = AE_{entry}(3) = \emptyset$
$AE_{exit}(4) = AE_{entry}(4) = \emptyset$
$AE_{exit}(5) = AE_{entry}(5) \cup \{x+y\} = \{x+y\}$
$AE_{exit}(6) = AE_{entry}(6) \backslash \{x+y\} = \emptyset$
$AE_{exit}(7) = AE_{entry}(7) \backslash \{x+y\} = \emptyset$
$AE_{exit}(8) = AE_{entry}(8) \backslash \{i+1\} = \emptyset$
$AE_{exit}(9) = AE_{entry}(9) \backslash \{x+y\} = \emptyset$