# Ćwiczenia 4, grupa śr. 12-14, 20 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 |
| ----------------------:| -----| --- | --- | --- | --- |
Mikołaj Balwicki | | | | | |
Małgorzata Galińska | X | X | | X | |
Maria Hreniak | X | X | X | X | |
Jakub Jankowski | X | X | X | X | |
Mikołaj Kalitka | | | | | |
Julia Konefał | ==X== | X | | X | X |
Julia Kulczycka | X | X | | X | X |
Cecylia Łyjak | X | X | | X | X |
Adam Majchrowski | X | X | | X | |
Piotr Mańkowski | | | | | |
Piotr Salamon | X | X| | X | X |
Maciej Szałasz | X | X | | X | X |
:::

Tutaj można zadeklarować zaległe zadania **3** i **4** z **listy 3**:

:::danger
| Imię i nazwisko | 3.3 | 3.4 |
| ----------------------:| -----| -----|
Jakub Jankowski | | / | pół X
| | |
:::

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

## Zadanie 1
:::success
Autor: Julia Konefał


$RD_{\circ} (1) = \{(x, ?), (y, ?), (z, ?), (t, ?), (i, ?)\}$

$RD_{\bullet} (1) = RD_{\circ} (1) \setminus \{(x, l) | l \in Lab \} \cup \{(x, 1)\}$

$RD_{\circ} (2) = RD_{\bullet} (1)$

$RD_{\bullet} (2) = RD_{\circ} (2) \setminus \{(y, l) | l \in Lab \} \cup \{(y, 2)\}$

$RD_{\circ} (3) = RD_{\bullet} (2)$

$RD_{\bullet} (3) = RD_{\circ} (3) \setminus \{(i, l) | l \in Lab \} \cup \{(i, 3)\}$

$RD_{\circ} (4) = RD_{\bullet} (3) \cup\ RD_{\bullet} (8)$

$RD_{\bullet} (4) = RD_{\circ} (4)$

$RD_{\circ} (5) = RD_{\bullet} (4)$

$RD_{\bullet} (5) = RD_{\circ} (5) \setminus \{(t, l) | l \in Lab \} \cup \{(t, 5)\}$

$RD_{\circ} (6) = RD_{\bullet} (5)$

$RD_{\bullet} (6) = RD_{\circ} (6) \setminus \{(x, l) | l \in Lab \} \cup \{(x, 6)\}$

$RD_{\circ} (7) = RD_{\bullet} (6)$

$RD_{\bullet} (7) = RD_{\circ} (7) \setminus \{(y, l) | l \in Lab \} \cup \{(y, 7)\}$

$RD_{\circ} (8) = RD_{\bullet} (7)$

$RD_{\bullet} (8) = RD_{\circ} (8) \setminus \{(i, l) | l \in Lab \} \cup \{(i, 8)\}$

$RD_{\circ} (9) = RD_{\bullet} (4)$

$RD_{\bullet} (9) = RD_{\circ} (9) \setminus \{(y, l) | l \in Lab \} \cup \{(y, 9)\}$
:::

## Zadanie 2
:::success
Autor: Piotr Salamon
Przyjmijmy "nazewnictwo" RD1 = RD∘(1), RD2 = RD●(1), ... , RD17 = RD∘(9), RD18 = RD●(9)

Inicjalizacja / Iteracja 0
RDj = ∅ (dla j = 1, 2, ..., 18)

Iteracja 1:

RD1 = {(x, ?), (y, ?), (z, ?), (i, ?), (t, ?)} [✓]
RD2 = {(x, 1), (y, ?), (z, ?), (i, ?), (t, ?)} [✓]
RD3 = {(x, 1), (y, ?), (z, ?), (i, ?), (t, ?)} [✓]
RD4 = {(x, 1), (y, 2), (z, ?), (i, ?), (t, ?)} [✓]
RD5 = {(x, 1), (y, 2), (z, ?), (i, ?), (t, ?)} [✓]
RD6 = {(x, 1), (y, 2), (z, ?), (i, 3), (t, ?)} [✓]
RD7 = {(x, 1), (y, 2), (z, ?), (i, 3), (t, ?)} ∪ ∅ <- bo nie znamy RD●(8)
RD8 = {(x, 1), (y, 2), (z, ?), (i, 3), (t, ?)} ∪ ∅
RD9 = {(x, 1), (y, 2), (z, ?), (i, 3), (t, ?)} ∪ ∅
RD10 = {(x, 1), (y, 2), (z, ?), (i, 3), (t, 5)} ∪ ∅
RD11 = {(x, 1), (y, 2), (z, ?), (i, 3), (t, 5)} ∪ ∅
RD12 = {(x, 6), (y, 2), (z, ?), (i, 3), (t, 5)} ∪ ∅
RD13 = {(x, 6), (y, 2), (z, ?), (i, 3), (t, 5)} ∪ ∅
RD14 = {(x, 6), (y, 7), (z, ?), (i, 3), (t, 5)} ∪ ∅
RD15 = {(x, 6), (y, 7), (z, ?), (i, 3), (t, 5)} ∪ ∅
RD16 = {(x, 6), (y, 7), (z, ?), (i, 8), (t, 5)} ∪ ∅ [✓] <- to jest git bo wszystko znamy już bo przeszliśmy całą pętle while
RD17 = {(x, 1), (y, 2), (z, ?), (i, 3), (t, ?)} ∪ ∅
RD18 = {(x, 1), (y, 9), (z, ?), (i, 3), (t, ?)} ∪ ∅

Iteracja 2: (pomijamy już te co są poprawnie)

RD7 = {(x, 1), (x, 6), (y, 2), (y, 7), (i, 3), (i, 8), (z, ?), (t, ?), (t, 5)} [✓]
RD8 = {(x, 1), (x, 6), (y, 2), (y, 7), (i, 3), (i, 8), (z, ?), (t, ?), (t, 5)} [✓]
RD9 = {(x, 1), (x, 6), (y, 2), (y, 7), (i, 3), (i, 8), (z, ?), (t, ?), (t, 5)} [✓]
RD10 = {(x, 1), (x, 6), (y, 2), (y, 7), (i, 3), (i, 8), (z, ?), (t, 5)} [✓]
RD11 = {(x, 1), (x, 6), (y, 2), (y, 7), (i, 3), (i, 8), (z, ?), (t, 5)} [✓]
RD12 = {(x, 6), (y, 2), (y, 7), (i, 3), (i, 8), (z, ?), (t, 5)} [✓]
RD13 = {(x, 6), (y, 2), (y, 7), (i, 3), (i, 8), (z, ?), (t, 5)} [✓]
RD14 = {(x, 6), (y, 7), (i, 3), (i, 8), (z, ?), (t, 5)} [✓]
RD15 = {(x, 6), (y, 7), (i, 3), (i, 8), (z, ?), (t, 5)} [✓]
RD17 = {(x, 1), (x, 6), (y, 2), (y, 7), (i, 3), (i, 8), (z, ?), (t, ?), (t, 5)} [✓]
RD18 = {(x, 1), (x, 6), (y, 9), (i, 3), (i, 8), (z, ?), (t, ?), (t, 5)} [✓]

:::

## Zadanie 3
:::success
Autor: Jakub Jankowski
3)program powinien przejsc po wszystkich scieżkach programu (np. DFS) i do każdej instrukcji zastosować reguły obliczania jej RD in/out wg (początkowo każdy RD = zbiór pusty):
po przejsciu powinien zapisać stan wszystkich RD. Wykonać się ponownie na nowych wartościach i potem sprawdzić czy coś się zmieniło. Jeśli tak to od nowa, a jesli nie, to zwraca zaisany stan RD.
:::

## Zadanie 4
:::success
Autor: Cecylia Łyjak
:::

## Zadanie 5
:::success
Autor: Maciej Szałasz
:::

## Analiza zmiennych żywych
Zamiast skupiać się na tym, gdzie ostatnio przypisano wartość do danej zmiennej, naszym celem będzie zidentyfikowanie, które przypisania zmiennych rzeczywiście wpływają na działanie programu. Innymi słowy, będziemy szukać punktów w programie, w których przypisanie wartości nie ma wpływu na działanie programu.

## Zmienna żywa

Zmienna będzie uznana za **żywą**, jeśli istnieje możliwość, że zostanie użyta gdziekolwiek indziej (na przykład do obliczenia innej zmiennej), zanim zostanie ponownie zdefiniowana (przypisana nowej wartości). Przykładowo, może to oznaczać, że zostanie użyta wewnątrz warunku instrukcji warunkowej.

Przykład:

Widzimy tutaj, że zmienna $x$ jest martwa na początku działania programu, bo przed przypisaniem jej nowej wartości nie ma miejsca w którym moglibyśmy wykorzystać jej starą wartość.

$FV(a)$ - zbiór wszystkich zmiennych występujących w wyrażeniu $a$

Robiąc przypisanie, "zabijamy" zmienną do której przypisujemy w tym sensie, że jej poprzednia wartość nas już nie obchodzi.

Za to nasze przypisanie może używać innych zmiennych, które z kolei w tamtym momencie stają się żywe, bo ich używamy.
Tzn. x := y + 1 "zabija" starą wartość x, ale sprawia, że wartość y jest "żywa", bo w tym miejscu jej używamy.

### Przykład z wykładu


### Analiza programu z zadania 1:
**Algorytm**

**Układ równań:**

**Rozwiązanie**
Porównując z programem rozwiązanie wydaje się dobre.