# Ćwiczenia 3, grupa śr. 10-12, 15 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 | | | | | | |
Mikołaj Dworszczak | | | | | | | | |
Kacper Jóźwiak | | | | | | | | |
Dominik Kiełbowicz | | | | | | | | |
Michał Kolasa | | | | | | | | |
Konrad Kowalczyk | X | X | X | | X | | | |
Oskar Kropielnicki | X | X | X | | X | | | |
Anna Krysta | X | X | X | X | X | X | X | X |
Jakub Krzyżowski | X | X | | | | | | |
Oskar Kubkowski | X | X | X | X | X | | ==X== | |
Patryk Maciąg | | | | | | | | |
Mateusz Mazur | X | X | X | | | | | |
Barbara Moczulska | X | X | X | | X | | | |
Kacper Sojda | X | X | X | X | X | | X | |
Marta Strzelec | x | x | x | | ==x== | | x | |
Mikołaj Swoboda | X | X | X | | X | | X | |
Filip Szczepański | X | | | | | | | |
Julian Włodarek | X | | | | | | | |
Beata Łakoma | x | x | x | x | x | | x | |
Michał Łukasik | X | X | X | | X | | | |
:::

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

## Zadanie 1
:::success
Autor: Mateusz Biłyk
:::


| nr | wejscie | wyjscie |
| --- | ----------------------------------------- | ----------------------------------------- |
| 1 | | (x,1) |
| 2 | (x,1) | (x,1),(y,2) |
| 3 | (x,1),(y,2) | (x,1),(y,2),(i,3) |
| 4 | (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) |
| 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,1),(y,2),(i,3),(t,5),(x,6),(y,7),(i,8) | (y,2),(i,3),(t,5),(x,6),(y,7),(i,8) |
| 7 | (y,2),(i,3),(t,5),(x,6),(y,7),(i,8) | (i,3),(t,5),(x,6),(y,7),(i,8) |
| 8 | (i,3),(t,5),(x,6),(y,7),(i,8) | (t,5),(x,6),(y,7),(i,8) |
| 9 | (x,1),(y,2),(i,3),(t,5),(x,6),(y,7),(i,8) | (x,1),(i,3),(t,5),(x,6),(i,8),(y,9)
## Zadanie 2
:::success
Autor: Mateusz Mazur
:::


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

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

$RD_{\circ}(3) = RD_{\bullet}(2)$
$RD_{\bullet}(3) = RD_{\circ}(3) \setminus \{(i,?)\}\ \bigcup \{(i,3)\} = \{(x,1), (y,2), (z,?), (i,3), (t,?)\}$

$RD_{\circ}(4) = RD_{\bullet}(3) \bigcup RD_{\bullet}(8) = \{(x,1), (x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,?) (t,5)\}$
$RD_{\bullet}(4) = RD_{\circ}(4)$

$RD_{\circ}(5) = RD_{\bullet}(4)$
$RD_{\bullet}(5) = RD_{\circ}(5) \setminus \{(t,?)\} \bigcup \{(t,5)\} = \{(x,1), (x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,5)\}$

$RD_{\circ}(6) = RD_{\bullet}(5)$
$RD_{\bullet}(6) = RD_{\circ}(6) \setminus \{(x,1), (x,6)\} \bigcup \{(x,6)\} = \{(x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,5)\}$

$RD_{\circ}(7) = RD_{\bullet}(6)$
$RD_{\bullet}(7) = RD_{\circ}(7) \setminus \{(y,7),(y,2)\} \bigcup \{(y,7)\} = \{(x,6), (y,7), (z,?), (i,3), (i,8), (t,5)\}$

$RD_{\circ}(8) = RD_{\bullet}(7)$
$RD_{\bullet}(8) = RD_{\circ}(8) \setminus \{(i,3),(i,8)\} \bigcup \{(i,8)\} = \{(x,6), (y,7), (z,?), (i,8), (t,5)\}$

$RD_{\circ}(9) = RD_{\bullet}(4)$
$RD_{\bullet}(9) = RD_{\circ}(9) \setminus \{(y,2),(y,7)\} \bigcup \{(y,9)\} = \{(x,1), (x,6), (y,9), (z,?), (i,3), (i,8), (t,?) (t,5)\}$

## Zadanie 3
:::success
Autor: Oskar Kropielnicki
:::


:::info
$RD_\bullet(1) = RD_\circ(1) \backslash \{(x, l) | l \in \text{Lab}\} \cup \{(x, 1)\}$
$RD_\bullet(2) = RD_\circ(2) \backslash \{(y, l) | l \in \text{Lab}\} \cup \{(y, 2)\}$
$RD_\bullet(3) = RD_\circ(3) \backslash \{(i, l) | l \in \text{Lab}\} \cup \{(i, 3)\}$
$RD_\bullet(4) = RD_\circ(4)$
$RD_\bullet(5) = RD_\circ(5) \backslash \{(t, l) | l \in \text{Lab}\} \cup \{(t, 5)\}$
$RD_\bullet(6) = RD_\circ(6) \backslash \{(x, l) | l \in \text{Lab}\} \cup \{(x, 6)\}$
$RD_\bullet(7) = RD_\circ(7) \backslash \{(y, l) | l \in \text{Lab}\} \cup \{(y, 7)\}$
$RD_\bullet(8) = RD_\circ(8) \backslash \{(i, l) | l \in \text{Lab}\} \cup \{(i, 8)\}$
$RD_\bullet(9) = RD_\circ(9) \backslash \{(y, l) | l \in \text{Lab}\} \cup \{(y, 9)\}$
<br>
$RD_\circ(1) = \{(v, ?) | v \in \{x, y, z, i, t\}\}$
$RD_\circ(2) = RD_\bullet(1)$
$RD_\circ(3) = RD_\bullet(2)$
$RD_\circ(4) = RD_\bullet(3) \cup RD_\bullet(8)$
$RD_\circ(5) = RD_\bullet(4)$
$RD_\circ(6) = RD_\bullet(5)$
$RD_\circ(7) = RD_\bullet(6)$
$RD_\circ(8) = RD_\bullet(7)$
$RD_\circ(9) = RD_\bullet(4)$
:::

### Iteracja 0.

$RD_\alpha(i) = \emptyset \quad (i \in \{1, 2, ..., 9\}; \alpha \in \{\circ, \bullet\})$

### Iteracja 1.

$\ast$ oznacza wartość, która w kolejnych iteracjach pozostaje taka sama.

$RD_\circ^\ast(1) = \{(x, ?), (y, ?), (z, ?), (i, ?), (t, ?)\}$
$RD_\bullet^\ast(1) = \{(x, 1), (y, ?), (z, ?), (i, ?), (t, ?)\}$
$RD_\circ^\ast(2) = \{(x, 1), (y, ?), (z, ?), (i, ?), (t, ?)\}$
$RD_\bullet^\ast(2) = \{(x, 1), (y, 2), (z, ?), (i, ?), (t, ?)\}$
$RD_\circ^\ast(3) = \{(x, 1), (y, 2), (z, ?), (i, ?), (t, ?)\}$
$RD_\bullet^\ast(3) = \{(x, 1), (y, 2), (z, ?), (i, 3), (t, ?)\}$
$RD_\circ(4) = \{(x, 1), (y, 2), (z, ?), (i, 3), (t, ?)\} \cup \emptyset$
$RD_\bullet(4) = \{(x, 1), (y, 2), (z, ?), (i, 3), (t, ?)\}$
$RD_\circ(5) = \{(x, 1), (y, 2), (z, ?), (i, 3), (t, ?)\}$
$RD_\bullet(5) = \{(x, 1), (y, 2), (z, ?), (i, 3), (t, 5)\}$
$RD_\circ(6) = \{(x, 1), (y, 2), (z, ?), (i, 3), (t, 5)\}$
$RD_\bullet(6) = \{(x, 6), (y, 2), (z, ?), (i, 3), (t, 5)\}$
$RD_\circ(7) = \{(x, 6), (y, 2), (z, ?), (i, 3), (t, 5)\}$
$RD_\bullet(7) = \{(x, 6), (y, 7), (z, ?), (i, 3), (t, 5)\}$
$RD_\circ(8) = \{(x, 6), (y, 7), (z, ?), (i, 3), (t, 5)\}$
$RD_\bullet^\ast(8) = \{(x, 6), (y, 7), (z, ?), (i, 8), (t, 5)\}$
$RD_\circ(9) = \{(x, 1), (y, 2), (z, ?), (i, 3), (t, ?)\}$
$RD_\bullet(9) = \{(x, 1), (y, 9), (z, ?), (i, 3), (t, ?)\}$

### Iteracja 2.

$RD_\circ^\ast(4) = \{(x, 1), (y, 2), (z, ?), (i, 3), (t, ?)\} \cup \{(x, 6), (y, 7), (z, ?), (i, 8), (t, 5)\} \\ \qquad = \{(x, 1), (x, 6), (y, 2), (y, 7), (z, ?), (i, 3), (i, 8), (t, ?), (t, 5)\}$
$RD_\bullet^\ast(4) = \{(x, 1), (x, 6), (y, 2), (y, 7), (z, ?), (i, 3), (i, 8), (t, ?), (t, 5)\}$
$RD_\circ^\ast(5) = \{(x, 1), (x, 6), (y, 2), (y, 7), (z, ?), (i, 3), (i, 8), (t, ?), (t, 5)\}$
$RD_\bullet^\ast(5) = \{(x, 1), (x, 6), (y, 2), (y, 7), (z, ?), (i, 3), (i, 8), (t, 5)\}$
$RD_\circ^\ast(6) = \{(x, 1), (x, 6), (y, 2), (y, 7), (z, ?), (i, 3), (i, 8), (t, 5)\}$
$RD_\bullet^\ast(6) = \{(x, 6), (y, 2), (y, 7), (z, ?), (i, 3), (i, 8), (t, 5)\}$
$RD_\circ^\ast(7) = \{(x, 6), (y, 2), (y, 7), (z, ?), (i, 3), (i, 8), (t, 5)\}$
$RD_\bullet^\ast(7) = \{(x, 6), (y, 7), (z, ?), (i, 3), (i, 8), (t, 5)\}$
$RD_\circ^\ast(8) = \{(x, 6), (y, 7), (z, ?), (i, 3), (i, 8), (t, 5)\}$
$RD_\circ^\ast(9) = \{(x, 1), (x, 6), (y, 2), (y, 7), (z, ?), (i, 3), (i, 8), (t, ?), (t, 5)\}$
$RD_\bullet^\ast(9) = \{(x, 1), (x, 6), (y, 9), (z, ?), (i, 3), (i, 8), (t, ?), (t, 5)\}$

## Zadanie 4
:::success
Autor: Kacper Sojda
:::


## Zadanie 5
:::success
Autor: Marta Strzelec
:::


## Zadanie 6
:::success
Autor: Anna Krysta
:::

## Zadanie 7
:::success
Autor: Oskar Kubkowski
:::

| $l$ | $RD_{\circ} (l)$ | $RD_{\bullet} (l)$ |
| --- | ------------------------------------------------------------------------ | ------------------------------------------------------------------------ |
| 1 | {(x, ?), (y, ?), (t, ?), (i, ?), (z, ?)} | {(x, 1), (y, ?), (t, ?), (i, ?), (z, ?)} |
| 2 | {(x, 1), (y, ?), (t, ?), (i, ?), (z, ?)} | {(x, 1), (y, 2), (t, ?), (i, ?), (z, ?)} |
| 3 | {(x, 1), (y, 2), (t, ?), (i, ?), (z, ?)} | {(x, 1), (y, 2), (t, ?), (i, 3), (z, ?)} |
| 4 | {(x, 1), (y, 2), (t, ?), (i, 3), (z, ?), (t, 5), (x, 6), (y, 7), (i, 8)} | {(x, 1), (y, 2), (t, ?), (i, 3), (z, ?), (t, 5), (x, 6), (y, 7), (i, 8)} |
| 5 | {(x, 1), (y, 2), (t, ?), (i, 3), (z, ?), (t, 5), (x, 6), (y, 7), (i, 8)} | {(x, 1), (y, 2), (i, 3), (z, ?), (t, 5), (x, 6), (y, 7), (i, 8)} |
| 6 | {(x, 1), (y, 2), (i, 3), (z, ?), (t, 5), (x, 6), (y, 7), (i, 8)} | { (y, 2), (i, 3), (z, ?), (t, 5), (x, 6), (y, 7), (i, 8)} |
| 7 | {(y, 2), (i, 3), (z, ?), (t, 5), (x, 6), (y, 7), (i, 8)} | { (i, 3), (z, ?), (t, 5), (x, 6), (y, 7), (i, 8)} |
| 8 | {(i, 3), (z, ?), (t, 5), (x, 6), (y, 7), (i, 8)} | {(z, ?), (t, 5), (x, 6), (y, 7), (i, 8)} |
| 9 | {(x, 1), (y, 2), (t, ?), (i, 3), (z, ?), (t, 5), (x, 6), (y, 7), (i, 8)} | {(x, 1), (t, ?), (i, 3), (z, ?), (t, 5), (x, 6), (i, 8), (y, 9)} |

| $ud(x,l)$ | $x$ | $y$ | $t$ | $i$ | $z$ |
| ------- | ----------- | ----------- | ----------- | ----------- | ----------- |
| $1$ | $\emptyset$ | $\emptyset$ | $\emptyset$ | $\emptyset$ | $\emptyset$ |
| $2$ | $\emptyset$ | $\emptyset$ | $\emptyset$ | $\emptyset$ | $\emptyset$ |
| $3$ | $\emptyset$ | $\emptyset$ | $\emptyset$ | $\emptyset$ | $\emptyset$ |
| $4$ | $\emptyset$ | $\emptyset$ | $\emptyset$ | {3,8} | {?} |
| $5$ | {1,6} | {2,7} | $\emptyset$ | $\emptyset$ | $\emptyset$ |
| $6$ | $\emptyset$ | {2,7} | $\emptyset$ | $\emptyset$ | $\emptyset$ |
| $7$ | $\emptyset$ | $\emptyset$ | {5} | $\emptyset$ | $\emptyset$ |
| $8$ | $\emptyset$ | $\emptyset$ | $\emptyset$ | {3,8} | $\emptyset$ |
| $9$ | {1,6} | $\emptyset$ | $\emptyset$ | $\emptyset$ | $\emptyset$ |

## Zadanie 8
:::success
Autor: Anna Krysta
:::