# Ćwiczenia 4, grupa cz. 16-18, 21 marca 2024

###### tags: `SYK24` `ćwiczenia` `pwit`

## Deklaracje

Gotowość rozwiązania zadania należy wyrazić poprzez postawienie X w odpowiedniej kolumnie! Jeśli pożądasz zreferować dane zadanie (co najwyżej jedno!) w trakcie dyskusji oznacz je znakiem ==X== na żółtym tle.

**UWAGA: Tabelkę wolno edytować tylko wtedy, gdy jest na zielonym tle!**

:::danger
| | 1 | 2 | 3 | 4 | 5 |
| ----------------------:| -----| --- | --- | --- | --- |
Marcin Banak | X | | | X |X |
Bartosz Borecki | X | X | X | X | |
Karol Burczyk | X | X | | X | X |
Yelyzaveta Ilman | X | | | X | X |
Antoni Kamiński | | | | | |
Jan Kamyk | X | X | X | X | X |
Bartosz Kruszewski | X | X | X | X |==X==|
Hanna Laszkiewicz | X | X | X | X | X |
Kaja Matuszewska | | | | | |
Dominik Muc | | | | | |
Krzysztof Ostrowski | ==X== | | | X | X |
Franciszek Przeliorz | | | | | |
Yaryna Rachkevych | X | X | | X | X |
Mikołaj Kalitka | X | | | X | X |
Piotr Thamm | X | X | X | ==X== | X |
Taras Tsehenko | X | | X | X | X |
:::

Tu można zadeklarować zadania **3**, **4** i **5** z **listy 3**:

:::danger
| | 3.3 | 3.4 | 3.5 |
| ----------------------:| -----| -----| -----|
Marcin Banak | | | |
Bartosz Borecki | | | |
Karol Burczyk | | | |
Yelyzaveta Ilman | | | |
Antoni Kamiński | | | |
Jan Kamyk | | | ==X==|
Bartosz Kruszewski | | | |
Hanna Laszkiewicz | | | |
Kaja Matuszewska | | | |
Dominik Muc | | | |
Krzysztof Ostrowski | | | |
Franciszek Przeliorz | | | |
Yaryna Rachkevych | | | |
Piotr Thamm | | | |
Taras Tsehenko | | | |
:::

:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::

## Zadanie 1
:::success
Autor: Krzysztof Ostrowski
:::




Równania definiujące zbiory $RD_{∘}(l)$ i $RD_{⦁}(l)$, dla $l∈$ {1,...,9}:

$RD_{⦁}(1)$ = $RD_{∘}(1)$ \ {(x, l) : $l∈$ **Lab**} ∪ {(x, 1)}
$RD_{⦁}(2)$ = $RD_{∘}(2)$ \ {(y, l) : $l∈$ **Lab**} ∪ {(y, 2)}
$RD_{⦁}(3)$ = $RD_{∘}(3)$ \ {(i, l) : $l∈$ **Lab**} ∪ {(i, 3)}
$RD_{⦁}(4)$ = $RD_{∘}(4)$
$RD_{⦁}(5)$ = $RD_{∘}(5)$ \ {(t, l) : $l∈$ **Lab**} ∪ {(t, 5)}
$RD_{⦁}(6)$ = $RD_{∘}(6)$ \ {(x, l) : $l∈$ **Lab**} ∪ {(x, 6)}
$RD_{⦁}(7)$ = $RD_{∘}(7)$ \ {(y, l) : $l∈$ **Lab**} ∪ {(y, 7)}
$RD_{⦁}(8)$ = $RD_{∘}(8)$ \ {(i, l) : $l∈$ **Lab**} ∪ {(i, 8)}
$RD_{⦁}(9)$ = $RD_{∘}(9)$ \ {(y, l) : $l∈$ **Lab**} ∪ {(y, 9)}

$RD_{∘}(1)$ = {(x, ?), (y, ?), (i, ?), (t, ?)}
$RD_{∘}(2)$ = $RD_{⦁}(1)$
$RD_{∘}(3)$ = $RD_{⦁}(2)$
$RD_{∘}(4)$ = $RD_{⦁}(3)$ ∪ $RD_{⦁}(8)$
$RD_{∘}(5)$ = $RD_{⦁}(4)$
$RD_{∘}(6)$ = $RD_{⦁}(5)$
$RD_{∘}(7)$ = $RD_{⦁}(6)$
$RD_{∘}(8)$ = $RD_{⦁}(7)$
$RD_{∘}(9)$ = $RD_{⦁}(8)$

## Zadanie 2
:::success
Autor: Karol Burczyk
:::

$Algorytm:$

Iteracja 1:
{

$RD_{∘}(1)$ = {(x, ?), (y, ?), (z, ?), (i, ?), (t, ?)}
$RD_{⦁}(1)$ = {(x, 1), (y, ?), (z, ?), (i, ?), (t, ?)}
$RD_{∘}(2)$ = {(x, 1), (y, ?), (z, ?), (i, ?), (t, ?)}
$RD_{⦁}(2)$ = {(x, 1), (y, 2), (z, ?), (i, ?), (t, ?)}
$RD_{∘}(3)$ = {(x, 1), (y, 2), (z, ?), (i, ?), (t, ?)}
$RD_{⦁}(3)$ = {(x, 1), (y, 2), (z, ?), (i, 3), (t, ?)}
-> Wejście do pętli
$RD_{∘}(4)$ = {(x, 1), (y, 2), (z, ?), (i, 3), (t, ?)} ∪ ∅ tutaj nie znamy jeszcze $RD_{⦁}(8)$ dlatego oznaczamy jako zbiór pusty
$RD_{⦁}(4)$ = {(x, 1), (y, 2), (z, ?), (i, 3), (t, ?)} ∪ ∅
$RD_{∘}(5)$ = {(x, 1), (y, 2), (z, ?), (i, 3), (t, ?)} ∪ ∅
$RD_{⦁}(5)$ = {(x, 1), (y, 2), (z, ?), (i, 3), (t, 5)} ∪ ∅
$RD_{∘}(6)$ = {(x, 1), (y, 2), (z, ?), (i, 3), (t, 5)} ∪ ∅
$RD_{⦁}(6)$ = {(x, 6), (y, 2), (z, ?), (i, 3), (t, 5)} ∪ ∅
$RD_{∘}(7)$ = {(x, 6), (y, 2), (z, ?), (i, 3), (t, 5)} ∪ ∅
$RD_{⦁}(7)$ = {(x, 6), (y, 7), (z, ?), (i, 3), (t, 5)} ∪ ∅
$RD_{∘}(8)$ = {(x, 6), (y, 7), (z, ?), (i, 3), (t, 5)} ∪ ∅
$RD_{⦁}(8)$ = {(x, 6), (y, 7), (z, ?), (i, 8), (t, 5)} ∪ ∅
<- Następuje wyjście z pętli
$RD_{∘}(9)$ = {(x, 1), (y, 2), (z, ?), (i, 3), (t, ?)} ∪ ∅
$RD_{⦁}(9)$ = {(x, 1), (y, 9), (z, ?), (i, 3), (t, ?)} ∪ ∅

}

Iteracja 2: $RD$ od 1 do 3 się nie zmienią ,więc nie ma sensu ich zapisywać
{

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

}

## Zadanie 3
:::success
Autor: Bartosz Borecki

1
$RD_{⦁}(1)$ = $RD_{∘}(1)$ \ {(x, l) : $l∈$ Lab} ∪ {(x, 1)}
kill({(x,?),(x,1),(x,6)}) gen({x,1})

$RD_{⦁}(2)$ = $RD_{∘}(2)$ \ {(y, l) : $l∈$ Lab} ∪ {(y, 2)}
kill({(y,?),(y,2),(y,7),(y,9)}) gen({y,2})

$RD_{⦁}(3)$ = $RD_{∘}(3)$ \ {(i, l) : $l∈$ Lab} ∪ {(i, 3)}
kill({(i,?),(i,3),(i,8)}) gen({i,3})

$RD_{⦁}(4)$ = $RD_{∘}(4)$

$RD_{⦁}(5)$ = $RD_{∘}(5)$ \ {(t, l) : $l∈$ Lab} ∪ {(t, 5)}
kill({(t,?),(t,5)}) gen({t,5})

$RD_{⦁}(6)$ = $RD_{∘}(6)$ \ {(x, l) : $l∈$ Lab} ∪ {(x, 6)}
kill({(x,?),(x,1),(x,6)}) gen({x,6})

$RD_{⦁}(7)$ = $RD_{∘}(7)$ \ {(y, l) : $l∈$ Lab} ∪ {(y, 7)}
kill({(y,?),(y,2),(y,7),(y,9)}) gen({y,7})

$RD_{⦁}(8)$ = $RD_{∘}(8)$ \ {(i, l) : $l∈$ Lab} ∪ {(i, 8)}
kill({(i,?),(i,3),(i,8)}) gen({i,8})

$RD_{⦁}(9)$ = $RD_{∘}(9)$ \ {(y, l) : $l∈$ Lab} ∪ {(y, 9)}
kill({(y,?),(y,2),(y,7),(y,9)}) gen({y,9})

2
$gen([read(x)]^l) = \{(x,l)\}$
$kill([read(x)]^l) = \{(x, l') | l' \in Lab\}$

3
dla kazdej operacji i:
$RD_{∘}(i)$ = suma zbiorów OUT operacji wchodzących
$RD_{⦁}(i)$ = $RD_{∘}(i)$ / kill(i) U gen(i)
Otrzymujemy równania i wykorzystujemy algorytm stałopunktowy
:::

## Zadanie 4
:::success
Autor: Piotr Thamm


:::

## Zadanie 5
:::success
Autor: Bartosz Kruszewski
:::

### Definicja

Zmienna jest **żywa**, jeśli bedzie wykorzystywana pozniej w programie.

Przykład:

x := 1
x := 2

Zmienna $x$ jest **martwa** na początku programu,
poniewaz pozniej w programie nigdzie nie wykorzystujemy jej przypisania,
a dalej jest jeszcze zmieniona.

### Definicje $kill$ oraz $gen$:

$kill([x := a]) = \{a\}$ \
$kill([skip]) = \emptyset$ \
$kill([b]) = \emptyset$

$gen([x := a]) = FV(a)$ \
$gen([skip]) = \emptyset$ \
$gen([b]) = FV(b)$

### Równania dla programu z zadania 1:

IN(1) = OUT(1) \ {x}
IN(2) = OUT(2) \ {y}
IN(3) = OUT(3) \ {i}
IN(4) = OUT(4) U {i, z}
IN(5) = OUT(5) \ {t} U {x, y}
IN(6) = OUT(6) \ {x} U {y}
IN(7) = OUT(7) \ {y} U {t}
IN(8) = OUT(8) \ {i} U {i}
IN(9) = OUT(9) \ {y} U {x}

OUT(1) = IN(2)
OUT(2) = IN(3)
OUT(3) = IN(4)
OUT(4) = IN(5)
OUT(5) = IN(6)
OUT(6) = IN(7)
OUT(7) = IN(8)
OUT(8) = IN(9)
OUT(9) = {}

### Rozwiazanie:

OUT(9) = {}
IN(9) = OUT(9) \ {y} U {x} = {x}
OUT(8) = IN(9) = {x}
IN(8) = OUT(8) \ {i} U {i} = {x, i}
OUT(7) = IN(8) = {x, i}
IN(7) = OUT(7) \ {y} U {t} = {x, i, t}
OUT(6) = IN(7) = {x, i, t}
IN(6) = OUT(6) \ {x} U {y} = {i, t, y}
OUT(5) = IN(6) = {i, t, y}
IN(5) = OUT(5) \ {t} U {x, y} = {i, x, y}
OUT(4) = IN(5) = {i, x, y}
IN(4) = OUT(4) U {i, z} = {i, x, y, z}
OUT(3) = IN(4) = {i, x, y, z}
IN(3) = OUT(3) \ {i} = {x, y, z}
OUT(2) = IN(3) = {x, y, z}
IN(2) = OUT(2) \ {y} = {x, z}
OUT(1) = IN(2) = {x, z}
IN(1) = OUT(1) \ {x} = {z}