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

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

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.