---
# System prepended metadata

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

---

# Ćwiczenia 3, grupa cz. 12-14, 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   |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
 Daniel Boguszewski      |   X   |  X  |  X  |  X  |     |     |     |     |
 Adam Ciężkowski         |       |     |     |     |     |     |     |     |
 Jacek Długopolski       |    X   |   X  |   X  |     |  X   |     |   X  |     |
 Jakub Fila              |    X  |  X  |     |  X  |     |     |  X  |     |
 Krzysztof Grynkiewicz   |    X   |  X   |     |     |     |     |     |     |
 Michał Hetnar           |   x   |  x  |  x  |  x  |  x  |     |     |     |
 Hubert Jabłoński        |   x   |  x  |  x  |  x  |  x  |  x  |  x  |     |
 Antoni Kamiński         |   X    |  X   |   X  |     |     |     |     |     |
 Paweł Karaś | X | X | X | X  |     |     |     |     |
 Emil Kisielewicz        |   X   |  X  |     |     |     |     |     |     |
 Kacper Komenda          |    X  |  X  |     |     |     |     |     |     |
 Filip Komorowski        |    x   |  x   |  x   |  x   |   x  |     |  x   |     |
 Piotr Piesiak           |    x   | x    | x    |  x   |  x   |  x   |  x   |     |
 Artur Krzyżyński        |   x   |  x  |  x  |   x  |  x  |  x  |  x   |     |
 Patryk Mazur            |==X==|  X  |  X  |  X  |  X  |     |     |     | 
 Szymon Mleczko          |    X   |   X  |   X  |   X  |    X |     |   X  |x|
 Michał Mróz             |   X   |  X   |  X  |  X  |  X  |     |==X==|     |
 Dominik Olejarz         |    X   |  X   |  X   |     | X    |     |  X   |     |
 Magdalena Słonińska     |   X    |  ==X==   |   X  |  X   |   X  |     |     |     |
 Oleś Kulczewicz         | ==X== |  X  |  X  |  X  |  X  |     |     |     |
 Adam Szeruda            |   X   |  X  |  X  |  X  |  X  |  X  |  X  |     |
 Kamil Tasarz            |   X   |  X  |  X  |  X  |  X  |     |  X  |     |
 Michał Zieliński        | ==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: Oleś Kulczewicz
:::
1
| step | instruction        | sets before the step                  | sets after the step                  |
| ---  | ---                | --- | --- |
|  1   | $[x:=0]^1$         |  $\{(x, ?), (y, ?), (i, ?), (t, ?)\}$ | $\{(x, 1), (y, ?), (i, ?), (t, ?)\}$ |
|  2   | $[y:=1]^2$         |  $\{(x, 1), (y, ?), (i, ?), (t, ?)\}$ | $\{(x, 1), (y, 2), (i, ?), (t, ?)\}$ |
|  3   | $[i:=1]^3$         | $\{(x, 1), (y, 2), (i, ?), (t, ?)\}$  | $\{(x, 1), (y, 2), (i, 3), (t, ?)\}$ |
|  4   | $while [i<z]^4 do$ | $\{(x, 1), (y, 2), (i, 3), (t, ?)\}$  | |
|  5   | $[t:=x+y]^5$       | | |
|  6   | $[x:=y]^6$         | | |
|  7   | $[y:=t]^7$         | | |
|  8   | $[i:=i+1]^8$       | | |
|      | $od$               |$\{(x, 1), (y, 2), (i, 3), (t, ?)\}$  | $\{(x, 1), (y, 2), (i, 3), (t, ?)\}$ |
|  9   | $[y:=x]^9$         | | |


2.

| step | instruction        | set before the step                   | set after the step                   |
| ---   | ---                | ---                                   | ---                                  |
|  1   | $[x:=0]^1$         |  $\$ | $\{(x, 1), (y, ?), (i, ?), (t, ?)\}$ |
|  2   | $[y:=1]^2$         |  $\{(x, 1), (y, ?), (i, ?), (t, ?)\}$ | $\{(x, 1), (y, 2), (i, ?), (t, ?)\}$ |
|  3   | $[i:=1]^3$         |  $\{(x, 1), (y, 2), (i, ?), (t, ?)\}$ | $\{(x, 1), (y, 2), (i, 3), (t, ?)\}$ |
|  4   | $while [i<z]^4 do$ |  $\{(x, 1), (y, 2), (i, 3), (t, ?)\}$ | $\{(x, 1), (y, 2), (i, 3), (t, ?)\}$ |
|  5   | $[t:=x+y]^5$       |  $\{(x, 1), (y, 2), (i, 3), (t, ?)\}$ | $\{(x, 1), (y, 2), (i, 3), (t, 5)\}$ |
|  6   | $[x:=y]^6$         |  $\{(x, 1), (y, 2), (i, 3), (t, 5)\}$ | $\{(x, 6), (y, 2), (i, 3), (t, 5)\}$ |
|  7   | $[y:=t]^7$         |  $\{(x, 6), (y, 2), (i, 3), (t, 5)\}$ | $\{(x, 6), (y, 7), (i, 3), (t, 5)\}$ |
|  8   | $[i:=i+1]^8$       |  $\{(x, 6), (y, 2), (i, 3), (t, 5)\}$ | $\{(x, 6), (y, 2), (i, 8), (t, 5)\}$ |
|      | $od$               |  $\{(x, 6), (y, 2), (i, 8), (t, 5)\}$ | $\{(x, 1), (y, 2), (i, 3), (t, ?)\}$ |
|  9   | $[y:=x]^9$         | | |

3.

| step | instruction        | set before the step                   | set after the step                   |
| ---   | ---               | ---                                   | ---                                  |
|  1   | $[x:=0]^1$         |  $\{(x, ?), (y, ?), (i, ?), (t, ?)\}$ | $\{(x, 1), (y, ?), (i, ?), (t, ?)\}$ |
|  2   | $[y:=1]^2$         |  $\{(x, 1), (y, ?), (i, ?), (t, ?)\}$ | $\{(x, 1), (y, 2), (i, ?), (t, ?)\}$ |
|  3   | $[i:=1]^3$         |  $\{(x, 1), (y, 2), (i, ?), (t, ?)\}$ | $\{(x, 1), (y, 2), (i, 3), (t, ?)\}$ |
|  4   | $while [i<z]^4 do$ |  $\{(x, 1), (y, 2), (i, 3), (t, ?)\} \cup \{(x, 6), (y, 2), (i, 8), (t, 5)\}$ | $\{(x, 1), (y, 2), (i, 3), (t, 5), (x, 6), (y, 7), (i, 8)\}$ |
|  5   | $[t:=x+y]^5$       |  $\{(x, 1), (y, 2), (i, 3), (t, 5), (x, 6), (y, 7), (i, 8)\}$ | $\{(x, 1), (y, 2), (i, 3), (t, 5), (x, 6), (y, 7), (i, 8)\}$ |
|  6   | $[x:=y]^6$         |  $\{(x, 1), (y, 2), (i, 3), (t, 5), (x, 6), (y, 7), (i, 8)\}$ | $\{(x, 6), (y, 2), (i, 3), (t, 5), (y, 7), (i, 8)\}$ |
|  7   | $[y:=t]^7$         |  $\{(x, 6), (y, 2), (i, 3), (t, 5), (y, 7), (i, 8)\}$ | $\{(x, 6), (y, 7), (i, 3), (t, 5), (i, 8)\}$ |
|  8   | $[i:=i+1]^8$       |  $\{(x, 6), (y, 7), (i, 3), (t, 5), (i, 8)\}$ | $\{(x, 6), (y, 7), (i, 8), (t, 5)\}$ |
|      | $od$               |  $\{(x, 6), (y, 7), (i, 8), (t, 5)\}$ | $\{(x, 1), (x, 6), (y, 2), (y, 7), (i, 3), (i, 8), (t, 5)\}$ |
|  9   | $[y:=x]^9$         |  $\{(x, 1), (x, 6), (y, 2), (y, 7), (i, 3), (i, 8), (t, 5)\}$ | $\{(x, 1), (x, 6), (y, 9), (i, 3), (i, 8), (t, 5)\}$ |

## Zadanie 2

:::success
Autor Magdalena Słonińska
:::

> Dla programu z poprzedniego zadania ułóż równania dla zbiorów $RD_{\circ} (l)$ oraz $RD_{\bullet} (l)$, dla $l \in \{1, \dots, 9\}$. Następnie sprawdź, że zbiory wyliczone w poprzednim zadaniu spełniają te równania.

Mamy następujący algorytm:

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

i jego graf przepływu sterowania:

```graphviz
digraph{
1 -> 2
2 -> 3
3 -> 4
4 -> 5
4 -> 9
5 -> 6
6 -> 7
7 -> 8
8 -> 4
}
```

Przy analizie każdej kolejnej instrukcji musimy wziąć pod uwagę dwie sytuacje:
1. $RD_{\circ} (l) \setminus \{(x, l') | l' \in Lab \} \cup \{(x, l)\} = RD_{\bullet} (l)$ dla instrukcji $l$ typu `x := a`
2. $RD_{\bullet} (l_1) \cup RD_{\bullet} (l_2) = RD_{\circ} (l)$ dla instrukcji $l_1, l_2$ prowadzących do $l$

Rozpoczynamy naszą analizę ze zbiorem postaci `{(x, ?), (y, ?), (i, ?), (z, ?), (t, ?)}`.
* $RD_{\circ} (1) = RD_{\bullet} (0)$

**Instrukcja 1** (warunek 1)
* $RD_{\bullet} (1) = RD_{\circ} (1) \setminus \{(x, l') | l' \in \{1, \dots, 9\}\} \cup \{(x, 1)\} =$
`{(x, 1), (y, ?), (i, ?), (z, ?), (t, ?)}`
* $RD_{\circ} (2) = RD_{\bullet} (1) =$
`{(x, 1), (y, ?), (i, ?), (z, ?), (t, ?)}`

**Instrukcja 2** (warunek 1)
* $RD_{\bullet} (2) = RD_{\circ} (2) \setminus \{(y, l') | l' \in \{1, \dots, 9\}\} \cup \{(y, 2)\} =$
`{(x, 1), (y, 2), (i, ?), (z, ?), (t, ?)}`
* $RD_{\circ} (3) = RD_{\bullet} (2) =$
`{(x, 1), (y, 2), (i, ?), (z, ?), (t, ?)}`

**Instrukcja 3** (warunek 1)
* $RD_{\bullet} (3) = RD_{\circ} (3) \setminus \{(i, l') | l' \in \{1, \dots, 9\}\} \cup \{(i, 3)\} =$
`{(x, 1), (y, 2), (i, 3), (z, ?), (t, ?)}`
* $RD_{\circ} (4) = RD_{\bullet} (3) \cup RD_{\bullet} (8) =$
`{(x, 1), (x, 6), (y, 2), (y, 7), (i, 3), (i, 8), (z, ?), (t, ?), (t, 5)}`

**Instrukcja 4** (wyjątkowo warunek 2 z instrukcjami 3, 8)
* $RD_{\bullet} (4) = RD_{\circ} (4) =$
`{(x, 1), (x, 6), (y, 2), (y, 7), (i, 3), (i, 8), (z, ?), (t, ?) (t, 5)}`
* $RD_{\circ} (5) = RD_{\bullet} (4) =$
`{(x, 1), (x, 6), (y, 2), (y, 7), (i, 3), (i, 8), (z, ?), (t, ?) (t, 5)}`

**Instrukcja 5** (warunek 1)
* $RD_{\bullet} (5) = RD_{\circ} (5) \setminus \{(t, l') | l' \in \{1, \dots, 9\}\} \cup \{(t, 5)\} =$
`{(x, 1), (x, 6), (y, 2), (y, 7), (i, 3), (i, 8), (z, ?), (t, 5)}`
* $RD_{\circ} (6) = RD_{\bullet} (5) =$
`{(x, 1), (x, 6), (y, 2), (y, 7), (i, 3), (i, 8), (z, ?), (t, 5)}`

**Instrukcja 6** (warunek 1)
* $RD_{\bullet} (6) = RD_{\circ} (6) \setminus \{(x, l') | l' \in \{1, \dots, 9\}\} \cup \{(x, 6)\} =$
`{(x, 6), (y, 2), (y, 7), (i, 3), (i, 8), (z, ?), (t, 5)}`
* $RD_{\circ} (7) = RD_{\bullet} (6) =$
`{(x, 6), (y, 2), (y, 7), (i, 3), (i, 8), (z, ?), (t, 5)}`

**Instrukcja 7**
* $RD_{\bullet} (7) = RD_{\circ} (7) \setminus \{(y, l') | l' \in \{1, \dots, 9\}\} \cup \{(y, 7)\} =$
`{(x, 6), (y, 7), (i, 3), (i, 8), (z, ?), (t, 5)}`
* $RD_{\circ} (8) = RD_{\bullet} (7) =$
`{(x, 6), (y, 7), (i, 3), (i, 8), (z, ?), (t, 5)}`

**Instrukcja 8**
* $RD_{\bullet} (8) = RD_{\circ} (8) \setminus \{(i, l') | l' \in \{1, \dots, 9\}\} \cup \{(i, 8)\} =$
`{(x, 6), (y, 7), (i, 8), (z, ?), (t, 5)}`
* $RD_{\circ} (9) = RD_{\bullet} (4) =$
`{(x, 1), (x, 6), (y, 2), (y, 7), (i, 3), (i, 8), (z, ?), (t, 5)}`

**Instrukcja 9**
* $RD_{\bullet} (9) = RD_{\circ} (9) \setminus \{(y, l') | l' \in \{1, \dots, 9\}\} \cup \{(y, 9)\} =$
`{(x, 1), (x, 6), (y, 9), (i, 3), (i, 8), (z, ?), (t, 5)}`

## Zadanie 3

:::success
Autor: Jacek Długopolski
:::
![](https://i.imgur.com/NJQkI1x.jpg)
![](https://i.imgur.com/DwWRvdK.jpg)
![](https://i.imgur.com/XC04uVf.jpg)
![](https://i.imgur.com/kZDNUG5.jpg)




## Zadanie 4

:::success
Autor: Jakub Fila
:::

![](https://i.imgur.com/Y9GaVx2.png)
![](https://i.imgur.com/FpRaKhu.png)
![](https://i.imgur.com/1Fsr2pa.png)


## Zadanie 5

:::success
Autor: Hubert Jabłoński
:::
![](https://i.imgur.com/SZpGM4x.png)

Algorytm:
$RD_{in}(1) :=\{(x,?),(y,?),(z,?)\}$
$RD_{out}(1):=\{(x,1),(y,?),(z,?)\}$

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

$RD_{in}(3) :=\{(x,1),(y,?),(z,?)\}$
$RD_{out}(3):=\{(x,1),(y,3),(z,?)\}$

$RD_{in}(4) :=\{(x,1),(y,?),(z,?)\}$
$RD_{out}(4):=\{(x,1),(y,4),(z,?)\}$

$RD_{in}(5) :=\{(x,1),(y,3),(y,4),(z,?)\}$
$RD_{out}(5):=\{(x,1),(y,3),(y,4),(z,5)\}$

Najlepsza możliwość:
$RD_{in}(1) :=\{(x,?),(y,?),(z,?)\}$
$RD_{out}(1):=\{(x,1),(y,?),(z,?)\}$

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

$RD_{in}(3) :=\{(x,1),(y,?),(z,?)\}$
$RD_{out}(3):=\{(x,1),(y,3),(z,?)\}$

$RD_{in}(4) :=\{(x,1),(y,?),(z,?)\}$
$RD_{out}(4):=\{(x,1),(y,4),(z,?)\}$

$RD_{in}(5) :=\{(x,1),(y,3),(z,?)\}$
$RD_{out}(5) :=\{(x,1),(y,3),(z,5)\}$


## Zadanie 6

:::success
Autor: Piotr Piesiak
:::
Zmienna jest uznawana za żywą, gdy może przydać się w dalszej części programu. Definiujemy:
$KILL(l)$ - zbiór zmiennych nadpisanych w linijce $l$
$GEN(l)$ - zbiór zmiennych występujących w wyrażeniu w danej linijce $l$
![](https://i.imgur.com/G7n9pRm.png)
![](https://i.imgur.com/Npouwzs.png)

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





## Zadanie 7

:::success
Autor:  Michał Mróz
Definicja: analiza łancuchów use-definition ma na zadaniu pokazać nam jeżeli w danym polu używamy danej zmiennej, to skąd będzie wzięta jej definicja. Analizę to się przeprowadza w taki sposób, że robimy przekrój zbioru definicji zmiennych które do danego miejsca mogą przejsć z używaną tam zmienną.

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

## Zadanie 8

:::danger
Autor: Szymon Mleczko

rozwiązanie nie pełne! stąd nie zgłaszałem

https://miro.com/welcomeonboard/SnUza2hhUVQ1b1pZUVIxZWhBamtQam5ESlBaUWxKWFNJSjYxd29Ca1BYQUlKZVdwU0ZUWVd6eXJtalZ3bUNRdHwzMDc0NDU3MzU1MTM0MjAyNjky?invite_link_id=527784255735

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

:::


