# Ćwiczenia 5, grupa śr. 14-16, 27 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 | 6 | 7 | 8 | 9 |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- | --- | --- |
Krzysztof Chorzempa | X | X | | | | X | | | |
Maciej Ciepiela | X | X | | | | ==X== | X | X | X |
Szymon Fica | X | | | | | X | X | X | X |
Agnieszka Grala | X | | | | | X | | X | X |
Karolina Jędraszek | X | | | | | X | X | X |X |
Katarzyna Jodłowska | X | | | | | X | X | X | X |
Dominik Kiełbowicz | | | | | | X | X | X | X |
Michał Kolasa | | | | | | X | X | X | X |
Rafał Krysa | X | X | X | X | | X | X | X | |
Miłosz Krzysiek | X | X | | | | X | X | X | ==X== |
Łukasz Kulczycki | | | | | | | | | |
Leon Lepkowski | X | | | | | X | X | X | X |
Hanna Makowska | X | | | | | X | | X | |
Jan Marek | | | | | | X | X | X | X |
Cezary Miłek | X | | | | | X | | X | |
Anna Pierzchała | ==X== | | | | | X | X | X | X |
Alan Pietrasz | | | | | | | | | |
Kacper Ponikowski | X | | | | | X | X | X | X |
Dominik Walecko | X | | | | | X | X | ==X== | X |
Michał Włodarczak | X | X | | | | X | X | X | |
:::

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

## Zadanie 1
:::success
Autor: Anna Pierzchała
:::


## Zadanie 2
:::success
Autor: Krzysztof Chorzempa
:::

### Definicja
### Kod z zadania 3.6
### Równania
#### entry
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = AE_{exit}(1)$
$AE_{entry}(3) = AE_{exit}(2)$
$AE_{entry}(4) = AE_{exit}(3) \bigcap AE_{exit}(8)$
$AE_{entry}(5) = AE_{exit}(4)$
$AE_{entry}(6) = AE_{exit}(5)$
$AE_{entry}(7) = AE_{exit}(6)$
$AE_{entry}(8) = AE_{exit}(7)$
$AE_{entry}(9) = AE_{exit}(4)$
#### exit
$AE_{exit}(1) = AE_{entry}(1) = \emptyset$
$AE_{exit}(2) = AE_{entry}(2)$
$AE_{exit}(3) = AE_{entry}(3)$
$AE_{exit}(4) = AE_{entry}(4)$
$AE_{exit}(5) = AE_{entry}(5) \setminus \{a \in AExp_* | t \in FV(a)\} + \{x+y\}$ (usuwamy wszystkie wyrażenia, gdzie korzystamy z wartości $t$)
$AE_{exit}(6) = AE_{entry}(6) \setminus \{a \in AExp_* | x \in FV(a)\}$ (nie ma sensu dodawać $y$ jako wyrażenie)
$AE_{exit}(7) = AE_{entry}(7) \setminus \{a \in AExp_* | y \in FV(a)\}$ (podobnie jak wyżej)
$AE_{exit}(8) = AE_{entry}(8) \setminus \{a \in AExp_* | i \in FV(a)\}$ (nie będziemy po tym kroku mieli wyliczonego aktualnego $i+1$)
$AE_{exit}(9) = AE_{entry}(9) \setminus \{a \in AExp_* | y \in FV(a)\}$ (nie ma sensu dodawać $x$ jako wyrażenie)

### Algorytm punktu stałego
Zaczynamy od:
$\forall 1 \leq i \leq 9 . AE_{entry}(i)=AE_{exit}(i):=ALL=\text{wszystkie wyrażenia} = \{x+y, (i+1)\}$.

Dopóki coś się zmienia to redukujemy:

$AE_{entry}(1):=\emptyset$
$AE_{exit}(1):=\emptyset$
(... podobnie dla $i=2,3$)
$AE_{entry}(4):=\emptyset \bigcap ALL = \emptyset$
$AE_{exit}(4):=\emptyset$
$AE_{entry}(5):=\emptyset$
$AE_{exit}(5):=\emptyset \bigcup \{x+y\} = \{x+y\}$
$AE_{entry}(6):=\{x+y\}$
$AE_{exit}(6):=\emptyset$
$AE_{entry}(7):=\emptyset$
$AE_{exit}(7):=\emptyset$
$AE_{entry}(8):=\emptyset$
$AE_{exit}(8):=\emptyset$
$AE_{entry}(9):=\emptyset$
$AE_{exit}(9):=\emptyset$

Jeżeli spróbowalibyśmy wyliczyć jakikolwiek $entry$ to dostalibyśmy to samo co mamy teraz (zawsze byłby to zbiór pusty, poza $i=6$).
Jeżeli spróbowalibyśmy wyliczyć jakikolwiek $exit$ to też dostalibyśmy to samo, bo zabrać nic za bardzo nie możemy (ze zbioru pustego), a jedyne dopisywanie jest przy $i=5$ - nie możemy dopisać nic więcej.

## Zadanie 3
:::success
Autor: Rafał Krysa
:::


## Zadanie 4
:::success
Autor: Rafał Krysa
:::

<details>

**Iteracja 0:**
AE_o(1)={(t, x+y) (i, i+1) },
AE_out(1)={(t, x+y) (i, i+1) },
AE_o(2)={(t, x+y) (i, i+1) },
AE_out(2)={(t, x+y) (i, i+1) },
AE_o(3)={(t, x+y) (i, i+1) },
AE_out(3)={(t, x+y) (i, i+1) },
AE_o(4)={(t, x+y) (i, i+1) },
AE_out(4)={(t, x+y) (i, i+1) },
AE_o(5)={(t, x+y) (i, i+1) },
AE_out(5)={(t, x+y) (i, i+1) },
AE_o(6)={(t, x+y) (i, i+1) },
AE_out(6)={(t, x+y) (i, i+1) },
AE_o(7)={(t, x+y) (i, i+1) },
AE_out(7)={(t, x+y) (i, i+1) },
AE_o(8)={(t, x+y) (i, i+1) },
AE_out(8)={(t, x+y) (i, i+1) },
AE_o(9)={(t, x+y) (i, i+1) },
AE_out(9)={(t, x+y) (i, i+1) },
**Iteracja 1:**
AE_o(1)={},
AE_out(1)={(i, i+1) },
AE_o(2)={(t, x+y) (i, i+1) },
AE_out(2)={(i, i+1) },
AE_o(3)={(t, x+y) (i, i+1) },
AE_out(3)={(t, x+y) },
AE_o(4)={(t, x+y) (i, i+1) },
AE_out(4)={(t, x+y) (i, i+1) },
AE_o(5)={(t, x+y) (i, i+1) },
AE_out(5)={(i, i+1) (t, x+y) },
AE_o(6)={(t, x+y) (i, i+1) },
AE_out(6)={(i, i+1) },
AE_o(7)={(t, x+y) (i, i+1) },
AE_out(7)={(i, i+1) },
AE_o(8)={(t, x+y) (i, i+1) },
AE_out(8)={(t, x+y) },
AE_o(9)={(t, x+y) (i, i+1) },
AE_out(9)={(i, i+1) },
**Iteracja 2:**
AE_o(1)={},
AE_out(1)={},
AE_o(2)={(i, i+1) },
AE_out(2)={(i, i+1) },
AE_o(3)={(i, i+1) },
AE_out(3)={(t, x+y) },
AE_o(4)={(t, x+y) },
AE_out(4)={(t, x+y) (i, i+1) },
AE_o(5)={(t, x+y) (i, i+1) },
AE_out(5)={(i, i+1) (t, x+y) },
AE_o(6)={(i, i+1) (t, x+y) },
AE_out(6)={(i, i+1) },
AE_o(7)={(i, i+1) },
AE_out(7)={(i, i+1) },
AE_o(8)={(i, i+1) },
AE_out(8)={(t, x+y) },
AE_o(9)={(t, x+y) (i, i+1) },
AE_out(9)={(i, i+1) },
**Iteracja 3:**
AE_o(1)={},
AE_out(1)={},
AE_o(2)={},
AE_out(2)={(i, i+1) },
AE_o(3)={(i, i+1) },
AE_out(3)={},
AE_o(4)={(t, x+y) },
AE_out(4)={(t, x+y) },
AE_o(5)={(t, x+y) (i, i+1) },
AE_out(5)={(i, i+1) (t, x+y) },
AE_o(6)={(i, i+1) (t, x+y) },
AE_out(6)={(i, i+1) },
AE_o(7)={(i, i+1) },
AE_out(7)={(i, i+1) },
AE_o(8)={(i, i+1) },
AE_out(8)={},
AE_o(9)={(t, x+y) (i, i+1) },
AE_out(9)={(i, i+1) },
**Iteracja 4:**
AE_o(1)={},
AE_out(1)={},
AE_o(2)={},
AE_out(2)={},
AE_o(3)={(i, i+1) },
AE_out(3)={},
AE_o(4)={},
AE_out(4)={(t, x+y) },
AE_o(5)={(t, x+y) },
AE_out(5)={(i, i+1) (t, x+y) },
AE_o(6)={(i, i+1) (t, x+y) },
AE_out(6)={(i, i+1) },
AE_o(7)={(i, i+1) },
AE_out(7)={(i, i+1) },
AE_o(8)={(i, i+1) },
AE_out(8)={},
AE_o(9)={(t, x+y) },
AE_out(9)={(i, i+1) },
**Iteracja 5:**
AE_o(1)={},
AE_out(1)={},
AE_o(2)={},
AE_out(2)={},
AE_o(3)={},
AE_out(3)={},
AE_o(4)={},
AE_out(4)={},
AE_o(5)={(t, x+y) },
AE_out(5)={(t, x+y) },
AE_o(6)={(i, i+1) (t, x+y) },
AE_out(6)={(i, i+1) },
AE_o(7)={(i, i+1) },
AE_out(7)={(i, i+1) },
AE_o(8)={(i, i+1) },
AE_out(8)={},
AE_o(9)={(t, x+y) },
AE_out(9)={},
**Iteracja 6:**
AE_o(1)={},
AE_out(1)={},
AE_o(2)={},
AE_out(2)={},
AE_o(3)={},
AE_out(3)={},
AE_o(4)={},
AE_out(4)={},
AE_o(5)={},
AE_out(5)={(t, x+y) },
AE_o(6)={(t, x+y) },
AE_out(6)={(i, i+1) },
AE_o(7)={(i, i+1) },
AE_out(7)={(i, i+1) },
AE_o(8)={(i, i+1) },
AE_out(8)={},
AE_o(9)={},
AE_out(9)={},
**Iteracja 7:**
AE_o(1)={},
AE_out(1)={},
AE_o(2)={},
AE_out(2)={},
AE_o(3)={},
AE_out(3)={},
AE_o(4)={},
AE_out(4)={},
AE_o(5)={},
AE_out(5)={(t, x+y) },
AE_o(6)={(t, x+y) },
AE_out(6)={},
AE_o(7)={(i, i+1) },
AE_out(7)={(i, i+1) },
AE_o(8)={(i, i+1) },
AE_out(8)={},
AE_o(9)={},
AE_out(9)={},
**Iteracja 8:**
AE_o(1)={},
AE_out(1)={},
AE_o(2)={},
AE_out(2)={},
AE_o(3)={},
AE_out(3)={},
AE_o(4)={},
AE_out(4)={},
AE_o(5)={},
AE_out(5)={(t, x+y) },
AE_o(6)={(t, x+y) },
AE_out(6)={},
AE_o(7)={},
AE_out(7)={(i, i+1) },
AE_o(8)={(i, i+1) },
AE_out(8)={},
AE_o(9)={},
AE_out(9)={},
**Iteracja 9:**
AE_o(1)={},
AE_out(1)={},
AE_o(2)={},
AE_out(2)={},
AE_o(3)={},
AE_out(3)={},
AE_o(4)={},
AE_out(4)={},
AE_o(5)={},
AE_out(5)={(t, x+y) },
AE_o(6)={(t, x+y) },
AE_out(6)={},
AE_o(7)={},
AE_out(7)={},
AE_o(8)={(i, i+1) },
AE_out(8)={},
AE_o(9)={},
AE_out(9)={},
**Iteracja 10:**
AE_o(1)={},
AE_out(1)={},
AE_o(2)={},
AE_out(2)={},
AE_o(3)={},
AE_out(3)={},
AE_o(4)={},
AE_out(4)={},
AE_o(5)={},
AE_out(5)={(t, x+y) },
AE_o(6)={(t, x+y) },
AE_out(6)={},
AE_o(7)={},
AE_out(7)={},
AE_o(8)={},
AE_out(8)={},
AE_o(9)={},
AE_out(9)={},

</details>

## Zadanie 5
:::danger
Autor: dodeklarować!
:::

## Zadanie 6
:::success
Autor: Maciej Ciepiela
:::

## Zadanie 7
:::success
Autor: Katarzyna Jodłowska
:::
*Przetłumacz następujący program na kod trójkowy.
Występujące w nim zmienne są typu całkowitego i mają po 4 bajty. Zmienne a, b, c są niemodyfikowalne. Użyj jak najmniejszej liczby zmiennych (rejestrów) tymczasowych. Następnie załóż, że w dodatkowym rejestrze o nazwie mem zapamiętany jest adres początku tablicy bajtów, którą możesz wykorzystać do pamiętania tymczasowych wyników obliczeń. Wykonaj ponownie tłumaczenie minimalizując liczbę wykorzystanych rejestrów tymczasowych “przelewając” je (ang. register spilling) do pamięci.***

Mamy
x = aaa + 4aab + 4abb + bbb = (a+b)^3 + aab + abb = (a+b)^3 + ab(a+b)

1.

t1 := a + b     // t1 = a + b
t2 := t1        // t2 = a + b
t2 := t2 * t1   // t2 = (a + b)^2
t2 := t2 * t1   // t2 = (a + b)^3
t1 := t1 * a    // t1 = (a + b)a
t1 := t1 * b    // t1 = (a + b)ab
t1 := t1 + t2   // t1 = (a + b)ab + (a + b)^3

2.

Niech *mem[i] := t*
oznacza *mem[4*i] := t*
oraz
niech *t := mem[i]*
oznacza *t := mem[4*i]*

t := a * a
t := t * a     //aaa
mem[0] := t    //zapisujemy aaa
t := 4 * a    
t := t * a
t := t * b    //4aab
mem[1] := t   //zapisujemy 4aab
t := 4 * a    
t := t * b
t := t * b    //4abb
mem[2] := t    //zapisujemy 4abb
t := b * b
t := t * b    //bbb
mem[3] := t    //zapisujemy bbb

//Odczytywanie wartości
r := mem[0] 
t := r        //aaa
r := mem[1]
t := t + r    //aaa + 4aab
r := mem[2]
t := t + r    //aaa + 4aab + 4abb
r := mem[3]
t := t + r    //aaa + 4aab + 4abb + bbb

## Zadanie 8
:::success
Autor: Michał Kolasa
:::
FOR I := 1 TO n - 1 DO
FOR J := I TO 1 DO
IF A[J] > A[J+1] THEN
BEGIN
Temp := A[J]
A[J] := A[J + 1]
A[J + 1] := Temp
END
DONE
DONE

Lecture:
I := 1 ; <<B1>>
goto ITest
ILoop: J := I ; <<B2>>
goto JTest
JLoop: t1 := 4 * J ; <<B3>>
t2 := A[t1] ; A[J]
t3 := J + 1
t4 := 4 * t3
t5 := A[t4] ; A[J + 1]
if t2 <= t5 goto JPlus
t6 := 4 * J ; <<B4>>
Temp := A[t6] ; Temp := A[J]
t7 := J + 1
t8 := 4 * t7
t9 := A[t8] ; A[J + 1]
t10 := 4 * J
A[t10] := t9 ; A[J] := A[J + 1]
t11 := J + 1
t12 := 4 * t11
A[t12] := Temp ; A [J + 1] := Temp
JPlus: J := J - 1 ; <<B5>>
JTest: if J >= 1 goto JLoop ; <<B6>>
IPlus: I := I + 1 ; <<B7>>
ITest: t13 := n - 1
if I <= t13 goto ILoop ; <<B8>>

more optimal?
I := 1
t13 := n - 1
goto ITest
ILoop: J := I
goto JTest
JLoop: t1 := 4 * J
t2 := A[t1]
t3 := J + 1
t4 := 4 * t3
t5 := A[t4]
if t2 <= t5 goto JPlus
A[t1] := t5
A[t4] := t2
JPlus: J := J - 1
JTest: if J >= 1 goto JLoop
IPlus: I := I + 1
ITest: if I <= t13 goto ILoop

## Zadanie 9
:::success
Autor: Miłosz Krzysiek
:::