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


i jego graf przepływu sterowania:

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

## Zadanie 4

:::success
Autor: Jakub Fila
:::


## Zadanie 5

:::success
Autor: Hubert Jabłoński
:::

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$


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


:::