---
# System prepended metadata

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

---

# Ć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	
:::


![Zrzut ekranu 2024-03-21 o 4.00.39 PM](https://hackmd.io/_uploads/BJWnjTtAa.png)

![Zrzut ekranu 2024-03-21 o 4.02.05 PM](https://hackmd.io/_uploads/ryq23TKRT.png)


![Zrzut ekranu 2024-03-21 o 3.49.02 PM](https://hackmd.io/_uploads/Hy2R2TKCT.png)




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
![image](https://hackmd.io/_uploads/SJies0tAp.png)


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	

![Lista 4-4](https://hackmd.io/_uploads/BJuIxk9RT.jpg)



:::

## 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}
```

