---
# System prepended metadata

title: 'Ćwiczenia 3, grupa cz. 14-16, 24. marca 2022'
tags: [SYK21, pwit, ćwiczenia]

---

# Ćwiczenia 3, grupa cz. 14-16, 24. marca 2022

###### tags: `SYK21` `ć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   | 6   | 7   | 8   |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Kamil Banaś              |       |     |     |     |     |     |     |     | 
Mateusz Burdyna          |       |     |     |     |     |     |     |     |
Dariusz Ciesielski       |       |     |     |     |     |     |     |     |
Dawid Dudek              |   X   |  X  |  X  |  X  |  X  |  X  |     |     |
Mikołaj Dworszczak       |       |     |     |     |     |     |     |     |
Przemysław Grochal       |       |     |     |     |     |     |     |     |
Adam Jarząbek            |     X  |     |     |     |     |     |     |     |
Anna Karykowska          |   X   |  X  |  X  |  X  |  X  |     |     |     |
Oleś Kulczewicz          |       |     |     |     |     |     |     |     |
Pola Marciniak           |   X   |  X  |  X  |  X  |  X  |==X==|     |     |
Mikołaj Mroziuk          |       |     |     |     |     |     |     |     |
Marcelina Oset           |       |     |     |     |     |     |     |     |
Natalia Piasta           |  X     |  ==X==   |  X   |   X  |   X  |  X  |    |     |
Krzysztof Piekarczyk     |    X   |  X   |     |     |     |     |     |     |
Marcin Płaza             |    X   |  X   |     |  X   |     |     |   X  |     |
Paweł Richert           |    ==X==   |     X| X    | X    | X     |     |     |     |
Rafał Starypan           |   X   |  X   |  X   |  ==X==   |  X   |  X   |   X  |     |
Dawid Strojek            |   X   |  X  |  X  |     |  X  |     |     |     |
Mateusz Suszek           |   X    |  X   |     |   X  |     |     |  X   |     |
Wojciech Śniady          |   X    |  X   |  X   |  X  |  X   |     |     |     |
Volha Tsekalo            |    X  |  X   |  X   |   X |   X  |     |     |     |
Yana Vashkevich          |   X    |   X  |  X   |  X   |  X   |     |     |     |
Konrad Woźniak           |   X    |   X  |  X   |  X  |  X   |     |     |     |
Natalia Czerep           |       |     |     |     |     |     |     |     |
Joanna Stachowicz        |   X   |  X  |  X  |     |  X  |     |  ==X== |     |
Marcelina Oset           |   x | x |==x==| x | x | x |x
:::


**Tutaj można do-deklarować zad. 9 z listy 2.:**
...



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



## Zadanie 1

:::success
Autor: Paweł Richert
:::
![](https://i.imgur.com/C9k53XY.png)

![](https://i.imgur.com/UVCqo1T.png)





## Zadanie 2

:::success
Autor: Natalia Piasta
:::
Dla programu z poprzedniego zadania ułóż równania dla zbiorów $RD_∘(𝑙)$ oraz $RD_⦁(𝑙)$, dla 𝑙∈{1,..., 9}. Następnie sprawdź,że zbiory wyliczone w poprzednim zadaniu spełniają te równania.

![](https://i.imgur.com/jqtu96w.jpg)

![](https://i.imgur.com/W4z2LpY.jpg)

## Zadanie 3

:::success
Autor: Konrad Woźniak
:::

![](https://i.imgur.com/HJl2LL6.png)
![](https://i.imgur.com/cyRKeBh.png)
![](https://i.imgur.com/s7ej17h.png)


$\#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)$
$RD_{\bullet}(4) = RD_{\circ}(4) =\{(x,1), (y,2), (z,?), (i,3), (t,?)\}$

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

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

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

$RD_{\circ}(8) = RD_{\bullet}(7)$
$\#RD_{\bullet}(8) = RD_{\circ}(8) \setminus \{(i,3)\} \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)\} \bigcup \{(y,9)\} =\{(x,1), (y,2), (z,?), (i,3), (t,?)\}$

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

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

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

$\#RD_{\circ}(7) = RD_{\bullet}(6)$
$\#RD_{\bullet}(7) = RD_{\circ}(7) \setminus \{(y,2), (y,7)\} \bigcup \{(y,7)\} =\{(i,3), (x,6), (y,7), (z,?), (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), (i,3), (t,?), (x,6), (y,9), (z,?), (i,8), (t,5)\}$

$\#$ - wartość ostateczna


## Zadanie 4

:::success
Autor: Rafał Starypan
:::
![](https://i.imgur.com/BtdnrKL.png)
![](https://i.imgur.com/SIyCrVe.png)

![](https://i.imgur.com/1gUe4vW.png)
![](https://i.imgur.com/WfLBFZj.png)


$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\, lub\, wczytaniem\,do \, x\}$   
    $gen_{RD}([read(x)]^{l}) = \{(x,l)\}$
    
3) Algorytm wyliczający zbiory RD(l).
 
![](https://i.imgur.com/TmvjhSC.png)

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

:::success
Autor: Anna Karykowska
:::

![](https://i.imgur.com/ZNCjnfK.png)

![](https://i.imgur.com/tG9bvwR.png)

![](https://i.imgur.com/FJnGDAI.png)

Program nigdy nie wejdzie do instrukcji 4, bo x na początku ustalamy jako 1 i to jest większe od 0. W takim razie nie potrzebujemy (y, 4) i nasze rozwiązanie nie jest optymalne.



## Zadanie 6

:::success
Autor: Marcelina Oset
:::

Zmienna jest **żywa** jeśli na wyjściu z etykiety istnieje ścieżka z tej etykiety do użycia tej zmiennej, która nie redefiniuje tej zmiennej. 

Analiza żywych zmiennych określa dla każdego punktu w programie, które zmienne mogą być żywe na wyjściu z programu. 

![](https://i.imgur.com/tVqvOAM.png)

Algorytm:

$LV_{\bullet}(l)$ = 
* $\emptyset$ dla $l \in final(S_{*})$
* $\Large\cup\normalsize\{LV_{\circ}(l')\ |\ (l', l) \in flow^{R}(S_{*})\}$ w.p.p.

$LV_{\circ}(l) = (LV_{\bullet}(l) \setminus kill_{LV}(B^l)) \cup gen_{LV}(B^l)$
gdzie $B^l \in blocks(S_{*})$ 

$kill_{LV}([x := a]^l) = {x}$
$kill_{LV}([skip]^l) = \emptyset$
$kill_{LV}([b]^l) = \emptyset$

$gen_{LV}([x := a]^l) = FV(a)$
$gen_{LV}([skip]^l) = \emptyset$
$gen_{LV}([b]^l) = FV(b)$
*FV(a) to jest zbiór wszystkich zmiennych występujących w wyrażeniu a*

Układ równań:
![](https://i.imgur.com/UV6eehX.png)

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

Na razie nie mamy wyliczonego $LV_{\circ}(5)$ więc załóżmy, że jest równy $\emptyset$

$LV_{\bullet}(4) = \{x\}$
$LV_{\circ}(4) = \{x, i, z\}$

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

---
$LV_{\bullet}(4) = \{x, y, i, z\}$
$LV_{\circ}(4) = \{x, y, i, z\}$

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

$LV_{\bullet}(3) = \{x, y, i, z\}$
$LV_{\circ}(3) = \{x, y, z\}$
$LV_{\bullet}(2) = \{x, y, z\}$
$LV_{\circ}(2) = \{x, z\}$
$LV_{\bullet}(1) = \{x, z\}$
$LV_{\circ}(1) = \{z\}$


## Zadanie 7

:::success
Autor: Joanna Stachowicz
:::
![](https://i.imgur.com/29gbT5e.jpg)


## Zadanie 8

:::success
Autor: Dawid Dudek (do-deklarowane)
:::

![](https://i.imgur.com/XRjyrnu.png)

### Jak działa analiza:

Jesteśmy w jakimś punkcie i chcemy wiedzieć jakie wyrażenia w tym punkcie mamy już policzone żeby się nie powtarzać. 

![](https://i.imgur.com/vohMxoH.png)


![](https://i.imgur.com/fc3bQqX.png)



![](https://i.imgur.com/zHBDuOh.jpg)
![](https://i.imgur.com/Jy4Zsoc.jpg)

![](https://i.imgur.com/qbiNZmD.png)
