---
# System prepended metadata

title: 'Ćwiczenia 4, grupa cz. 10-12, 21 marca 2024'
tags: [pwit, ćwiczenia, SYK24]

---

# Ćwiczenia 4, grupa cz. 10-12, 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   |
| ----------------------:| -----| --- | --- | --- | --- |
Borys Adamiak            |   X   |  X   |     |   X  |  X   | 
Michał Chawar            |   X   |  X   |  X   |  X   |  X  | 
Julia Cygan              |   X  |   X |    |   X  |  X  | 
Maciej Dengusiak         |   ==X==   |  X   |  X   |  X   |  X   | 
Patryk Flama             |  X   |  X  |  X  | ==X==   |  X  | 
Szymon Fluder            |      |     |     |     |     | 
Aleksandra Jędrzejak     |   X   |  X   |     |  X  |     | 
Mikołaj Karapka          |    X  | X    |     | X    |   X  | 
Viktoriia Kashpruk       |    X  |  X   |   X  |   X  |  X   | 
Wiktor Małek             |    X  |  ==X==   |  X   |   X  |   X  | 
Błażej Molik             |  X   |  X   | X |  X   |    X  | 
Andrzej Morawski         |      |     |     |     |     | 
Konrad Oleksy            |      |     |     |     |     | 
Lucjan Pucelak           |   X   |  X   |     |  X   |  X   |
Aleksandra Sęk           |   X   |     |     |     |     | 
Radosław Śliwiński       |      |     |     |     |     | 
Piotr Traczyński         |   X   |  X   |   X  |  X   |   X  | 
Katarzyna Trzos          |   X  | X   |     |  X   |  X  |
Piotr Warząchowski       |   X   |  X   |     |   X  |   X  |
Olga Zaborska            |  X  |  X  |  X  |  X  |  ==X==  | 
:::





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

:::danger
|                        | 3.3  | 3.4  |
| ----------------------:| -----| -----|
Borys Adamiak            |      |      | 
Michał Chawar            |      |      | 
Julia Cygan              |      |      | 
Maciej Dengusiak         |      |      | 
Patryk Flama             |      |      | 
Szymon Fluder            |      |      | 
Aleksandra Jędrzejak     |      |      | 
Mikołaj Karapka          |      |      | 
Viktoriia Kashpruk       |    X  |      | 
Wiktor Małek             |      |      | 
Błażej Molik             |      |      | 
Andrzej Morawski         |      |      | 
Konrad Oleksy            |      |      | 
Lucjan Pucelak           |      |      | 
Aleksandra Sęk           |      |      | 
Radosław Śliwiński       |      |      | 
Piotr Traczyński         |      |      | 
Katarzyna Trzos          |      |      | 
Piotr Warząchowski       |      |      | 
Olga Zaborska            |      |      | 
:::





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



## Zadanie 1
:::success
Autor: Maciej Dengusiak	
![image](https://hackmd.io/_uploads/rk8sABuAT.png)

![image](https://hackmd.io/_uploads/rkLgvLOA6.png)

Po przeprowadzeniu analizy programu i wypisaniu zbioru faktów wychodzą nam następujące równania definiujące zbiory $RD_{∘}(l)$ i $RD_{⦁}(l)$, dla $l∈$ {1,...,9}:

### Równania:

$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)$


### Zbiory z zadania 6

![image](https://hackmd.io/_uploads/SymSqUu0a.png)

#### Łatwo sprawdzić że te zbiory spełniają powyższe równania.
:::
:::

## Zadanie 2
:::success
Autor: Wiktor Małek	
:::
Inicjalizacja: Wszystkie zbiory puste

I iteracja:

$$RD_{in}(1)=\{(x, ?), (y, ?), (i, ?), (t, ?)\}$$
$$RD_{out}(1)=\{(x, 1), (y, ?), (i, ?), (t, ?)\}$$

$$RD_{in}(2)=\{(x, 1), (y, ?), (i, ?), (t, ?)\}$$
$$RD_{out}(2)=\{(x, 1), (y, 2), (i, ?), (t, ?)\}$$

$$RD_{in}(3)=\{(x, 1), (y, 2), (i, ?), (t, ?)\}$$
$$RD_{out}(3)=\{(x, 1), (y, 2), (i, 1), (t, ?)\}$$

$$RD_{in}(4)=\{(x, 1), (y, 2), (i, 1), (t, ?)\}$$
$$RD_{out}(4)=\{(x, 1), (y, 2), (i, 1), (t, ?)\}$$

$$RD_{in}(5)=\{(x, 1), (y, 2), (i, 1), (t, ?)\}$$
$$RD_{out}(5)=\{(x, 1), (y, 2), (i, 1), (t, 5)\}$$

$$RD_{in}(6)=\{(x, 1), (y, 2), (i, 1), (t, 5)\}$$
$$RD_{out}(6)=\{(x, 6), (y, 2), (i, 1), (t, 5)\}$$

$$RD_{in}(7)=\{(x, 6), (y, 2), (i, 1), (t, 5)\}$$
$$RD_{out}(7)=\{(x, 6), (y, 7), (i, 1), (t, 5)\}$$

$$RD_{in}(8)=\{(x, 6), (y, 7), (i, 1), (t, 5)\}$$
$$RD_{out}(8)=\{(x, 6), (y, 7), (i, 8), (t, 5)\}$$

$$RD_{in}(9)=\{(x, 1), (y, 2), (i, 1), (t, ?)\}$$

II iteracja:

linie 1,2,3 się nie zmienią więc pomijam

$$RD_{in}(4)=\{(x, 1), (y, 2), (i, 1), (t, ?), (x, 6), (y, 7), (i, 8), (t, 5)\}$$
$$RD_{out}(4)=\{(x, 1), (y, 2), (i, 1), (t, ?), (x, 6), (y, 7), (i, 8), (t, 5)\}$$

$$RD_{in}(5)=\{(x, 1), (y, 2), (i, 1), (t, ?), (x, 6), (y, 7), (i, 8), (t, 5)\}$$
$$RD_{out}(5)=\{(x, 1), (y, 2), (i, 1), (x, 6), (y, 7), (i, 8), (t, 5)\}$$

$$RD_{in}(6)=\{(x, 1), (y, 2), (i, 1), (x, 6), (y, 7), (i, 8), (t, 5)\}$$
$$RD_{out}(6)=\{(y, 2), (i, 1), (x, 6), (y, 7), (i, 8), (t, 5)\}$$

$$RD_{in}(7)=\{(y, 2), (i, 1), (x, 6), (y, 7), (i, 8), (t, 5)\}$$
$$RD_{out}(7)=\{(i, 1), (x, 6), (y, 7), (i, 8), (t, 5)\}$$

$$RD_{in}(8)=\{(i, 1), (x, 6), (y, 7), (i, 8), (t, 5)\}$$
$$RD_{out}(8)=\{(x, 6), (y, 7), (i, 8), (t, 5)\}$$

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

Po II iteracji już nic się nie zmieni, więc zatrzymujemy się.

## Zadanie 3
:::success
Autor: Michał Chawar	
:::

![image](https://hackmd.io/_uploads/rkna5dFCp.png)

**1.** Wystąpienia funkcji $kill$ i $gen$ pojawiają się w równaniach $RD_{\bullet}$, które są postaci $RD_{\bullet}(*) = RD_{\circ}(*) \setminus kill \cup gen$.  
Np. w  
$RD_{\bullet}(3) = RD_{\circ}(3) \setminus \{ (i, \ell) \mid \ell \in Lab \} \cup \{ (i, 3) \}$  
wystąpienie funkcji $kill$ to $\{ (i, \ell) \mid \ell \in Lab \} = \{ (i, ?) \}$, a funkcji $gen$ to $\{ (i, 3) \}$.

**2.** Dla instrukcji $read$ funkcja $kill$ powinna usuwać wszystkie poprzednie przypisania zmiennej $x$, bo instrukcją $read$ nadpisujemy ją bezwarunkowo. Instrukcja $gen$ powinna więc generować informację o nadpisaniu tej zmiennej przez siebie.

$$
kill_{RD}([read(x)]^{\ell}) = \{ (x, ?) \} \cup \{ (x, \ell') \mid \text{w instrukcji $\ell'$ jest przypisanie do $x$} \}
$$

$$
gen_{RD}([read(x)]^{\ell}) = \{ (x, \ell) \}
$$

Okazuje się, że w zakresie instrukcji $kill$ i $gen$ instrukcja $read$ nie różni się od zwykłego przypisania do zmiennej. 

**3.** Z pliku `slides2.pdf` (slajd $19$) mamy

$$
RD_{\circ}(\ell) = \begin{cases}
      \ \ \ \ \ \{ (x, ?) \ \ \ \ \mid x \in FV \} & \text{gdy $\ell$ = 1}\\
      \bigcup \ \{ RD_{\bullet}(\ell') \mid \text{$\ell'$ przechodzi do $\ell$} \} & \text{w przeciwnym przypadku}
\end{cases}
$$

$$
RD_{\bullet}(\ell) = [ RD_{\circ}(\ell) \setminus kill_{RD}([...]^\ell) ] \cup gen_{RD}([...]^\ell)
$$

($FV$ to zbiór wszystkich zmiennych występujących w programie).

Widzimy więc, że zbiory $RD_{\circ}$ i $RD_{\bullet}$ można obliczyć tylko na podstawie informacji o przypisaniach do zmiennych w programie i wiedzy o kolejności wykonywania instrukcji.
Stąd wystarczy przejść po przepływie sterowania, odnotowując wszystkie nadpisania zmiennych w instrukcjach, po czym przejść jeszcze raz i wygenerować te zbiory na podstawie zebranych danych.  

## Zadanie 4
:::success
Autor: Patryk Flama	
:::
![image](https://hackmd.io/_uploads/ryf60r_R6.png)
![image](https://hackmd.io/_uploads/rJPaCS_06.png)
![image](https://hackmd.io/_uploads/HJXJtUuAT.png)
![image](https://hackmd.io/_uploads/Hkdz7wO0T.png)
![image](https://hackmd.io/_uploads/BJsmQPdRa.png)
W faktycznym wykonaniu naszego programu druga opcja if'a nigdy nie zajdzie, więc policzona krotka (y, 4) jest zbędna. Otrzymaliśmy więc rozwiązanie bezpieczne, a nie dokładne.


## Zadanie 5
:::success
Autor: Olga Zaborska
:::
![image](https://hackmd.io/_uploads/B1b_WdK06.png)

![image](https://hackmd.io/_uploads/HJksWdKCT.png)

Zmienne żywe to te, których program użyje zanim nadpisze im nową wartość
Na przykładzie z wykładu
![image](https://hackmd.io/_uploads/HJYR4uKR6.png)
Widzimy, że pierwsze wystąpienie $x$ nie jest żywe, ponieważ jego wartość zostanie nadpisana przed pierwszym użyciem. 

Schemat działania:

![image](https://hackmd.io/_uploads/Syezb_YR6.png)

![image](https://hackmd.io/_uploads/rk1kf_tAa.png)
Wracając do przykładu: 
![image](https://hackmd.io/_uploads/SylPrOtAa.png)
![image](https://hackmd.io/_uploads/HJYR4uKR6.png)

Teraz dla zadania:
![image](https://hackmd.io/_uploads/HkWuP_YA6.png)


| l | $kill_{LV}(l)$ | $gen_{LV}(l)$ |
| -------- | -------- | -------- |
|   1   |  {x}   |  $\emptyset$    |
|   2   |  {y}   |  $\emptyset$    |
|   3   |  {i}   |  $\emptyset$    |
|   4   |  $\emptyset$    | {i,z}     |
|   5   |  {t}    |   {x,y}   |
|   6   |  {x}    |   {y}   |
|   7   |  {y}    |   {t}   |
|   8   |  {i}    |   {i}   |
|   9   |  {y}    |   {x}   |


Kolejny krok

![image](https://hackmd.io/_uploads/H1JqQutCp.png)

Dla przykładu 
![image](https://hackmd.io/_uploads/SkGYddt0T.png)

Dla programu z treści zadania

| l | $kill_{LV}(l)$ | $gen_{LV}(l)$ |$LV_{entry}$ |$LV_{exit}$ |
| -------- | -------- | -------- | --- | ---|
|   1   |  {x}   |  $\emptyset$    |  {z}    |  {x,z}    |
|   2   |  {y}   |  $\emptyset$    |  {x,z}    |  {x,y,z}    |
|   3   |  {i}   |  $\emptyset$    |  {x,y,z}    | {x,y,z,i}     |
|   4   |  $\emptyset$    | {i,z}  |  {x,y,z,i}    |  {x,y,z,i}    |
|   5   |  {t}    |   {x,y}   |  {x,y,z,i}   | {t,y,z,i}     |
|   6   |  {x}    |   {y}   |  {t,y,z,i}   | {x,t,z,i}     |
|   7   |  {y}    |   {t}   |  {x,t,z,i}   | {x,y,z,i}     |
|   8   |  {i}    |   {i}   |  {x,y,z,i}   | {x,y,z,i}     |
|   9   |  {y}    |   {x}   |   {x}   |  $\emptyset$    |

$LV_{in}(1) = LV_{out}(1) \setminus{\{x\}}$
$LV_{out}(1) = LV_{in}(2)$

$LV_{in}(2) = LV_{out}(2) \setminus{\{y\}}$
$LV_{out}(2) = LV_{in}(3)$

$LV_{in}(3) = LV_{out}(3) \setminus{\{i\}}$
$LV_{out}(3) = LV_{in}(4)$

$LV_{in}(4) = LV_{out}(4) \cup{\{z,i\}}$
$LV_{out}(4) = LV_{in}(5) \cup LV_{in}(5)$

$LV_{in}(5) = LV_{out}(5) \setminus{\{t\}} \cup{\{x,y\}}$
$LV_{out}(5) = LV_{in}(6)$

$LV_{in}(6) = LV_{out}(6) \setminus{\{x\}} \cup {\{y\}}$
$LV_{out}(6) = LV_{in}(7)$

$LV_{in}(7) = LV_{out}(7) \setminus{\{y\}} \cup {\{t\}}$
$LV_{out}(7) = LV_{in}(8)$

$LV_{in}(8) = LV_{out}(8) \setminus{\{i\}} \cup {\{i\}}$
$LV_{out}(8) = LV_{in}(4) = LV_{out}(4) \cup \{i,z\} = (LV_{in}(5) \cup LV_{in}(9)) \cup \{i,z\} = (LV_{out}(5) \setminus\{t\} \cup \{x,y\}) \cup \{x\} \cup \{i,z\} = \ ... \setminus \{t\} \cup \{x,y,z,i\} = \{x,y,z,i\}$

$LV_{in}(9) = LV_{out}(9) \setminus{\{y\} \cup {\{x\}}}$
$LV_{out}(9) = \emptyset$

$LV_{in}(9) = \{x\}$


