---
# System prepended metadata

title: 'Ćwiczenia 4, grupa śr. 10-12, 22 marca 2023'
tags: [pwit, ćwiczenia, SYK23]

---

# Ćwiczenia 4, grupa śr. 10-12, 22 marca 2023

###### tags: `SYK23` `ć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   |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Mateusz Biłyk            |       |  x  | x   |     |  x  |   x |  x  |     | 
Mikołaj Dworszczak       |       |     |     |     |     |     |     |     |
Kacper Jóźwiak           |       |     |     |     |  X  | X   |  X  |     |
Dominik Kiełbowicz       |       |     |     |     |     |     |     |     |
Michał Kolasa            |       |     |     |     |     |     |     |     |
Konrad Kowalczyk         |       |     |     |     |  X  |  X |  X  |     |
Oskar Kropielnicki       |       |     |     |     |  X  |  X  |  X  |     |
Anna Krysta              |    X  |  X  |  X  |  X  |  X  |  X  |  X  |  X  |
Jakub Krzyżowski         |       |     |     |     |  X  |  X  |  X  |     |
Oskar Kubkowski          |   X   |     |     |     |  ==X==  |  X  |  X  |     |
Patryk Maciąg            |       |     |     |     |     |     |     |     |
Mateusz Mazur            |       |     |     |     |   X  |  X   |  X   |     |
Barbara Moczulska        |       |     |     |     |  X  |  X  |  X  |     |
Kacper Sojda             |       |     |     |     |  X   |  X   |  X   |     |
Marta Strzelec           |       |     |     |     |  x   |  x   | x    |     |
Mikołaj Swoboda          |   X   |  X  |  X  |     |  X  |  X  |  X  |     |
Filip Szczepański        |       |     |     |     |  X   |  X   |  X   |     |
Julian Włodarek          |       |     |     |     | X    |  X   |  X   |     |
Beata Łakoma             |    x   |     |     |   x  |  x   |  x   | x    |     |
Michał Łukasik           |       |     |     |     |  X  |  X  |  X  |     |
:::





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




## Zadanie 1
:::danger
Autor: Beata Łakoma	
:::
równania z poprzedniej listy
!![](https://i.imgur.com/Szwue9d.jpg)


init
AE_ent(i)= {x,i,z,y,x+y,t}
AE_ex(i)= {x,i,z,y,x+y,t}

krok 1
AE_ent(1) = 0
AE_ent(2) = {x,i,z,y,x+y,t}
AE_ent(3) = {x,i,z,y,x+y,t}
AE_ent(4) = {x,i,z,y,x+y,t}
AE_ent(5) = {x,i,z,y,x+y,t}
AE_ent(6) = {x,i,z,y,x+y,t}
AE_ent(7) = {x,i,z,y,x+y,t}
AE_ent(8) = {x,i,z,y,x+y,t}
AE_ent(9) = {x,i,z,y,x+y,t}

AE_ex(1)= {x,i,z,y,x+y,t}
AE_ex(2)= {x,i,z,y,x+y,t}
AE_ex(3)= {x,i,z,y,x+y,t}
AE_ex(4)= {x,i,z,y,x+y,t}
AE_ex(5)= {x,i,z,y,x+y,t}
AE_ex(6)= {i,z,y,t}
AE_ex(7)= {x,i,z,x+y,t}
AE_ex(8)= {x,z,y,x+y,t}
AE_ex(9)= {x,i,z,y,x+y,t}

krok 2
AE_ent(1) = 0
AE_ent(2) = {x,i,z,y,x+y,t}
AE_ent(3) = {x,i,z,y,x+y,t}
AE_ent(4) = {x,z,y,x+y,t}
AE_ent(5) = {x,i,z,y,x+y,t}
AE_ent(6) = {x,i,z,y,x+y,t}
AE_ent(7) = {i,z,y,t}
AE_ent(8) = {x,i,z,x+y,t}
AE_ent(9) = {x,i,z,y,x+y,t} +

AE_ex(1)= 0
AE_ex(2)= {x,i,z,y,x+y,t}
AE_ex(3)= {x,i,z,y,x+y,t}
AE_ex(4)= {x,i,z,y,x+y,t}
AE_ex(5)= {x,i,z,y,x+y,t}
AE_ex(6)= {i,z,y,t}
AE_ex(7)= {x,i,z,x+y,t}
AE_ex(8)= {x,z,y,x+y,t}
AE_ex(9)= {x,i,z,y,x+y,t}

krok 3
AE_ent(1) = 0
AE_ent(2) = 0
AE_ent(3) = {x,i,z,y,x+y,t}
AE_ent(4) = {x,z,y,x+y,t}
AE_ent(5) = {x,i,z,y,x+y,t}
AE_ent(6) = {x,i,z,y,x+y,t}
AE_ent(7) = {i,z,y,t}
AE_ent(8) = {x,i,z,x+y,t}
AE_ent(9) = {x,i,z,y,x+y,t}

AE_ex(1)= 0
AE_ex(2)= {x,i,z,y,x+y,t}
AE_ex(3)= {x,i,z,y,x+y,t}
AE_ex(4)= {x,i,z,y,x+y,t}
AE_ex(5)= {x,i,z,y,x+y,t}
AE_ex(6)= {i,z,y,t}
AE_ex(7)= {x,i,z,x+y,t}
AE_ex(8)= {x,z,y,x+y,t}
AE_ex(9)= {x,i,z,y,x+y,t}
krok 4

AE_ent(1) = 0
AE_ent(2) = 0
AE_ent(3) = {x,i,z,y,x+y,t}
AE_ent(4) = {x,z,y,x+y,t}
AE_ent(5) = {x,i,z,y,x+y,t}
AE_ent(6) = {x,i,z,y,x+y,t}
AE_ent(7) = {i,z,y,t}
AE_ent(8) = {x,i,z,x+y,t}
AE_ent(9) = {x,i,z,y,x+y,t}

AE_ex(1)= 0
AE_ex(2)= 0
AE_ex(3)= {x,i,z,y,x+y,t}
AE_ex(4)= {x,i,z,y,x+y,t}
AE_ex(5)= {x,i,z,y,x+y,t}
AE_ex(6)= {i,z,y,t}
AE_ex(7)= {x,i,z,x+y,t}
AE_ex(8)= {x,z,y,x+y,t}
AE_ex(9)= {x,i,z,y,x+y,t}

krok 5
 
AE_ent(1) = 0
AE_ent(2) = 0
AE_ent(3) = 0
AE_ent(4) = {x,z,y,x+y,t}
AE_ent(5) = {x,i,z,y,x+y,t}
AE_ent(6) = {x,i,z,y,x+y,t}
AE_ent(7) = {i,z,y,t}
AE_ent(8) = {x,i,z,x+y,t}
AE_ent(9) = {x,i,z,y,x+y,t}

AE_ex(1)= 0
AE_ex(2)= 0
AE_ex(3)= {x,i,z,y,x+y,t}
AE_ex(4)= {x,i,z,y,x+y,t}
AE_ex(5)= {x,i,z,y,x+y,t}
AE_ex(6)= {i,z,y,t}
AE_ex(7)= {x,i,z,x+y,t}
AE_ex(8)= {x,z,y,x+y,t}
AE_ex(9)= {x,i,z,y,x+y,t}

krok 6

AE_ent(1) = 0
AE_ent(2) = 0
AE_ent(3) = 0
AE_ent(4) = {x,z,y,x+y,t}
AE_ent(5) = {x,i,z,y,x+y,t}
AE_ent(6) = {x,i,z,y,x+y,t}
AE_ent(7) = {i,z,y,t}
AE_ent(8) = {x,i,z,x+y,t}
AE_ent(9) = {x,i,z,y,x+y,t}

AE_ex(1)= 0
AE_ex(2)= 0
AE_ex(3)= 0
AE_ex(4)= {x,i,z,y,x+y,t}
AE_ex(5)= {x,i,z,y,x+y,t}
AE_ex(6)= {i,z,y,t}
AE_ex(7)= {x,i,z,x+y,t}
AE_ex(8)= {x,z,y,x+y,t}
AE_ex(9)= {x,i,z,y,x+y,t}

krok 7


AE_ent(1) = 0
AE_ent(2) = 0
AE_ent(3) = 0
AE_ent(4) = 0
AE_ent(5) = {x,i,z,y,x+y,t}
AE_ent(6) = {x,i,z,y,x+y,t}
AE_ent(7) = {i,z,y,t}
AE_ent(8) = {x,i,z,x+y,t}
AE_ent(9) = {x,i,z,y,x+y,t}

AE_ex(1)= 0
AE_ex(2)= 0
AE_ex(3)= 0
AE_ex(4)= {x,i,z,y,x+y,t}
AE_ex(5)= {x,i,z,y,x+y,t}
AE_ex(6)= {i,z,y,t}
AE_ex(7)= {x,i,z,x+y,t}
AE_ex(8)= {x,z,y,x+y,t}
AE_ex(9)= {x,i,z,y,x+y,t}

krok 8


AE_ent(1) = 0
AE_ent(2) = 0
AE_ent(3) = 0
AE_ent(4) = 0
AE_ent(5) = {x,i,z,y,x+y,t}
AE_ent(6) = {x,i,z,y,x+y,t}
AE_ent(7) = {i,z,y,t}
AE_ent(8) = {x,i,z,x+y,t}
AE_ent(9) = {x,i,z,y,x+y,t}

AE_ex(1)= 0
AE_ex(2)= 0
AE_ex(3)= 0
AE_ex(4)= {i,z}
AE_ex(5)= {x,i,z,y,x+y,t}
AE_ex(6)= {i,z,y,t}
AE_ex(7)= {x,i,z,x+y,t}
AE_ex(8)= {x,z,y,x+y,t}
AE_ex(9)= {x,i,z,y,x+y,t}

krok 9

AE_ent(1) = 0
AE_ent(2) = 0
AE_ent(3) = 0
AE_ent(4) = 0
AE_ent(5) = {i,z}
AE_ent(6) = {x,i,z,y,x+y,t}
AE_ent(7) = {i,z,y,t}
AE_ent(8) = {x,i,z,x+y,t}
AE_ent(9) = {i,z}

AE_ex(1)= 0
AE_ex(2)= 0
AE_ex(3)= 0
AE_ex(4)= {i,z}
AE_ex(5)= {x,i,z,y,x+y,t}
AE_ex(6)= {i,z,y,t}
AE_ex(7)= {x,i,z,x+y,t}
AE_ex(8)= {x,z,y,x+y,t}
AE_ex(9)= {x,i,z,y,x+y,t}

krok 10

AE_ent(1) = 0
AE_ent(2) = 0
AE_ent(3) = 0
AE_ent(4) = 0
AE_ent(5) = {i,z}
AE_ent(6) = {x,i,z,y,x+y,t}
AE_ent(7) = {i,z,y,t}
AE_ent(8) = {x,i,z,x+y,t}
AE_ent(9) = {i,z}

AE_ex(1)= 0
AE_ex(2)= 0
AE_ex(3)= 0
AE_ex(4)= {i,z}
AE_ex(5)= {i,z,x,y,x+y}
AE_ex(6)= {i,z,y,t}
AE_ex(7)= {x,i,z,x+y,t}
AE_ex(8)= {x,z,y,x+y,t}
AE_ex(9)= {i,z,x} ->

krok 11

AE_ent(1) = 0
AE_ent(2) = 0
AE_ent(3) = 0
AE_ent(4) = 0
AE_ent(5) = {i,z}
AE_ent(6) = {i,z,x,y,x+y}
AE_ent(7) = {i,z,y,t}
AE_ent(8) = {x,i,z,x+y,t}
AE_ent(9) = {x,z,y,x+y,t}

AE_ex(1)= 0
AE_ex(2)= 0
AE_ex(3)= 0
AE_ex(4)= {i,z}
AE_ex(5)= {i,z,x,y,x+y}
AE_ex(6)= {i,z,y,t}
AE_ex(7)= {x,i,z,x+y,t}
AE_ex(8)= {x,z,y,x+y,t}
AE_ex(9)= {x,i,z,y,x+y,t}

krok 12

AE_ent(1) = 0
AE_ent(2) = 0
AE_ent(3) = 0
AE_ent(4) = 0
AE_ent(5) = {i,z}
AE_ent(6) = {i,z,x,y,x+y}
AE_ent(7) = {i,z,y,t}
AE_ent(8) = {x,i,z,x+y,t}
AE_ent(9) = {x,z,y,x+y,t}

AE_ex(1)= 0
AE_ex(2)= 0
AE_ex(3)= 0
AE_ex(4)= {i,z}
AE_ex(5)= {i,z,x,y,x+y}
AE_ex(6)= {i,z,y}
AE_ex(7)= {x,i,z,x+y,t}
AE_ex(8)= {x,z,y,x+y,t}
AE_ex(9)= {x,i,z,y,x+y,t}

krok 13

AE_ent(1) = 0
AE_ent(2) = 0
AE_ent(3) = 0
AE_ent(4) = 0
AE_ent(5) = {i,z}
AE_ent(6) = {i,z,x,y,x+y}
AE_ent(7) = {i,z,y}
AE_ent(8) = {x,i,z,x+y,t}
AE_ent(9) = {x,z,y,x+y,t}

AE_ex(1)= 0
AE_ex(2)= 0
AE_ex(3)= 0
AE_ex(4)= {i,z}
AE_ex(5)= {i,z,x,y,x+y}
AE_ex(6)= {i,z,y}
AE_ex(7)= {x,i,z,x+y,t}
AE_ex(8)= {x,z,y,x+y,t}
AE_ex(9)= {x,i,z,y,x+y,t}

krok 14

AE_ent(1) = 0
AE_ent(2) = 0
AE_ent(3) = 0
AE_ent(4) = 0
AE_ent(5) = {i,z}
AE_ent(6) = {i,z,x,y,x+y}
AE_ent(7) = {i,z,y}
AE_ent(8) = {x,i,z,x+y,t}
AE_ent(9) = {x,z,y,x+y,t}

AE_ex(1)= 0
AE_ex(2)= 0
AE_ex(3)= 0
AE_ex(4)= {i,z}
AE_ex(5)= {i,z,x,y,x+y}
AE_ex(6)= {i,z,y}
AE_ex(7)= {i,z,t}
AE_ex(8)= {x,z,y,x+y,t}
AE_ex(9)= {x,i,z,y,x+y,t}

krok 15

AE_ent(1) = 0
AE_ent(2) = 0
AE_ent(3) = 0
AE_ent(4) = 0
AE_ent(5) = {i,z}
AE_ent(6) = {i,z,x,y,x+y}
AE_ent(7) = {i,z,y}
AE_ent(8) = {i,z,t}
AE_ent(9) = {x,z,y,x+y,t}

AE_ex(1)= 0
AE_ex(2)= 0
AE_ex(3)= 0
AE_ex(4)= {i,z}
AE_ex(5)= {i,z,x,y,x+y}
AE_ex(6)= {i,z,y}
AE_ex(7)= {i,z,t}
AE_ex(8)= {x,z,y,x+y,t}
AE_ex(9)= {x,i,z,y,x+y,t}

krok 16

AE_ent(1) = 0
AE_ent(2) = 0
AE_ent(3) = 0
AE_ent(4) = 0
AE_ent(5) = {i,z}
AE_ent(6) = {i,z,x,y,x+y}
AE_ent(7) = {i,z,y}
AE_ent(8) = {i,z,t}
AE_ent(9) = {x,z,y,x+y,t}

AE_ex(1)= 0
AE_ex(2)= 0
AE_ex(3)= 0
AE_ex(4)= {i,z}
AE_ex(5)= {i,z,x,y,x+y}
AE_ex(6)= {i,z,y}
AE_ex(7)= {i,z,t}
AE_ex(8)= {z,t}
AE_ex(9)= {x,i,z,y,x+y,t}

krok 17

AE_ent(1) = 0
AE_ent(2) = 0
AE_ent(3) = 0
AE_ent(4) = 0
AE_ent(5) = {i,z}
AE_ent(6) = {i,z,x,y,x+y}
AE_ent(7) = {i,z,y}
AE_ent(8) = {i,z,t}
AE_ent(9) = {i,z}

AE_ex(1)= 0
AE_ex(2)= 0
AE_ex(3)= 0
AE_ex(4)= {i,z}
AE_ex(5)= {i,z,x,y,x+y}
AE_ex(6)= {i,z,y}
AE_ex(7)= {i,z,t}
AE_ex(8)= {z,t}
AE_ex(9)= {x,i,z,y,x+y,t}

krok 18


AE_ent(1) = 0
AE_ent(2) = 0
AE_ent(3) = 0
AE_ent(4) = 0
AE_ent(5) = {i,z}
AE_ent(6) = {i,z,x,y,x+y}
AE_ent(7) = {i,z,y}
AE_ent(8) = {i,z,t}
AE_ent(9) = {i,z}

AE_ex(1)= 0
AE_ex(2)= 0
AE_ex(3)= 0
AE_ex(4)= {i,z}
AE_ex(5)= {i,z,x,y,x+y}
AE_ex(6)= {i,z,y}
AE_ex(7)= {i,z,t}
AE_ex(8)= {z,t}
AE_ex(9)= {i,z,x}

kroków będzie o 2 mniej bo pominąłem przypisanie AEen(9)=AEex(4)
teraz to poprawie
## Zadanie 2
:::success
Autor: Mikołaj Swoboda	
:::

**Wariant 1.**
Dziedziną $\Omega$ zbiorów występujących w tej analizie jest zbiór nietrywialnych wyrażeń, jakie są przypisywane do zmiennej *x* w czasie wykonywania programu.
$$ 
gen([x := a]) = \{ a\} \setminus \mathbf{Var} \text{, jeśli } x \notin FV(a) \\
gen(B) = \varnothing \text{ w p. p.} \\
kill([x := a]) = \Omega\\
kill([v := a]) = \{a' \in \Omega : v \in FV(a')\} \\
kill(B) = \varnothing \text{ w p. p.}
$$

$$
AE_{x, \circ}(l) = \begin{cases}
\varnothing & l = init(S) \\
\bigcap \{AE_{x, \bullet}(l') : (l', l) \in flow(S)\} & \text{w p. p.}
\end{cases}\\
AE_{x, \bullet}(l) = (AE_{x, \circ}(l) \setminus kill(B^l)) \cup gen(B^l), B^l \in blocks(S)
$$

**Wariant 2.**
$\Omega = \mathbf{Var} \times \mathbf{Exp}$
$$ 
gen([x := a]) = (x, \{ a\} \setminus \mathbf{Var}) \text{, jeśli } x \notin FV(a) \\
gen(B) = \varnothing \text{ w p. p.} \\
kill([x := a]) = \{ (a, b) : x = a \lor x \in FV(b)\}\\
kill(B) = \varnothing \text{ w p. p.}
$$

$$
AE_{\circ}(l) = \begin{cases}
\varnothing & l = init(S) \\
\bigcap \{AE_\bullet(l') : (l', l) \in flow(S)\} & \text{w p. p.}
\end{cases}\\
AE_{\bullet}(l) = (AE_{\circ}(l) \setminus kill(B^l)) \cup gen(B^l), B^l \in blocks(S)
$$

W punkcie (a) jest mowa o *wszystkich* ścieżkach prowadzących *do l*, zatem jest to analiza typu *must* oraz *forward*.

## Zadanie 3
:::success
Autor: Mateusz Biłyk	
:::
![](https://i.imgur.com/G8HmcAs.png)
Dziedzina to iloczyn kartezjański zbioru zmiennych i wyrażeń: $Var \times AExp$. 
$$kill([x = a]^l)= \{ a' \in AExp | x \in FV(a') \}
\\
kill([skip]^l)= \emptyset
\\
kill([b]^l)=\emptyset
\\
gen([x = a]^l)= (x,a)
\\
gen([skip]^l)= \emptyset
\\
gen([b]^l)=\emptyset
$$
$$
F_{entry}(l)=\bigcap_{(l',l)} F_{out}(l')
\\
F_{out}(l)=F_{entry}(l)\cup gen(l) \setminus kill(l)
$$
Ta analiza jest typu must bo liczą się wszystkie ścieżki oraz forward bo idzimy zgodnie z grafem przepływu.
Używamy algorytmu stałopunktowego liczącego największy stały punkt. Na początku każda zmienna zaiwera całą dziedzinę.
![](https://i.imgur.com/aio3qgn.png)
$$
F_{entry}(4)=F_{out}(3) \cap F_{out}(8) 
\\
    F_{out}(5)=F_{entry}(5) \cup (t,x+y)
$$

$$
F_{entry}(1)=\emptyset
\\
F_{out}(1)=\emptyset
\\
F_{entry}(2)=\emptyset
\\
F_{out}(2)=\emptyset
\\
F_{entry}(3)=\emptyset
\\
F_{out}(3)=\emptyset
\\
F_{entry}(4)=\emptyset
\\
F_{out}(4)=\emptyset
\\
F_{entry}(5)=\emptyset
\\
F_{out}(5)=(t,x+y)
\\
F_{entry}(6)=(t,x+y)
\\
F_{out}(6)=\emptyset
\\
F_{entry}(7)=\emptyset
\\
F_{out}(7)=\emptyset
\\
F_{entry}(8)=\emptyset
\\
F_{out}(8)=\emptyset
\\
F_{entry}(9)=\emptyset
\\
F_{out}(9)=\emptyset
\\
$$
## Zadanie 4
:::success
Autor: Anna Krysta	
:::
Będziemy chcieli wyliczyć najmniejszy punkt stały.
![](https://i.imgur.com/85WQ9ki.jpg)

## Zadanie 5
:::success
Autor: Oskar Kubkowski	
:::
![](https://i.imgur.com/SHYQaRs.png)

#### 1. while (b) {...}

```assembler=
goto Test
Loop: {...}
Test: if (b) goto Loop
```

#### 2. for (i = 0; i < n; i++) {...}
```assembler=
        i := 0 
        goto ITest
ILoop: {...}
       i := i + 1
ITest: if (i < n) goto ILoop

```

#### 3. do {...} while (b)
```assembler=
Loop: {...}
Test: if (b) goto Loop
```

## Zadanie 6
:::success
Autor: Kacper Jóźwiak	
:::

t1 := a * a
t2 := t1 * a

x := t2

t1 := a * b
t2 := t1 * a
t1 := t2 * 4

x := x + t1

t1 := b * b
t2 := t1 * a
t1 := t2 * 4
x := x + t1

t1 := b * b
t2 := t1 * b

x := x + t2

użycie mem

mem[1] := a * a
mem[4] := mem[1] * a

x := mem[1]

mem[1] := a * b
mem[4] := mem[1] * a
mem[1] := mem[4] * 4

x := x + mem[1]

mem[1] := b * b
mem[4] := mem[1] * a
mem[1] := mem[4] * 4
x := x + mem[1]

mem[1] := b * b
mem[4] := mem[1] * b

x := x + mem[4]

Rozw v2
t := a + b
x := t * t
x := x * t

t := a * b
t := t * a
x := x + t

t := t / a
t := t * b
x := x + t

## Zadanie 7
:::success
Autor: Barbara Moczulska	
:::

![](https://i.imgur.com/pxktGo2.png)
``` c=
0. Insert_sort(A, n)

1.  for i=2 to n :
# Wstaw A[i] w posortowany ciąg A[1 ... i-1]
3.      x = A[i]
4.      j = i - 1
5.      while j>0 and A[j] > x:
6.          A[j + 1] = A[j]
7.          j = j - 1
8.      A[j + 1] = x
```

```

    i := 2
W1: if i >= n goto E1
    x := t[i]
    j := i - 1
    
W2: if j <= 0 goto E2
    if t[j] <= x goto E2
    t1 := j + 1
    t[t1] := t[j]    
    j = j - 1
    goto W2
    
E2: t1 := j + 1
    t[t1] = x
    i := i + 1
    goto W1

E1:

```

## Zadanie 8
:::success
Autor: Anna Krysta
:::
![](https://i.imgur.com/dOhbTHk.jpg)
![](https://i.imgur.com/iaISiAv.jpg)
![](https://i.imgur.com/DcMfIFt.jpg)
![](https://i.imgur.com/YpE2oCe.jpg)
