# Ćwiczenia 4, grupa cz. 12-14, 31. marca 2022
###### tags: `SYK21` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Daniel Boguszewski | | | | | | | | |
Adam Ciężkowski | | | | | | | | |
Jacek Długopolski | x | | | | x | | | |
Jakub Fila | | | | | X | X | X | |
Krzysztof Grynkiewicz | | | | | ==X== | X | X | |
Michał Hetnar | x | x | | | x | | x | |
Hubert Jabłoński | | | | x | x | x | x | |
Antoni Kamiński | | | | | | | | |
Paweł Karaś | | | | | X | X | X | |
Emil Kisielewicz | X | | | | X | X | ==X== | |
Kacper Komenda | | | | | X | X | X | |
Filip Komorowski | | | x | x | x | ==x== | x | |
Piotr Piesiak | x | x | x | x | ==x== | x | x | |
Artur Krzyżyński | x | x | x | x | ==x== | x | x | |
Patryk Mazur | | | | | X | X |==X==| |
Szymon Mleczko | | X | X | | X | X | X | |
Michał Mróz | | | | | X | X | X | |
Dominik Olejarz | | | | | x | x | x | |
Magdalena Słonińska | | | | | X | X | X | |
Oleś Kulczewicz | | | | X | ==X== | X | X | |
Adam Szeruda | X | X | X |==X==| X | X | X | |
Kamil Tasarz | X | | | X | X | X | | |
Michał Zieliński | | | | X | X | X | X | |
:::
:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::
## Zadanie 1
:::success
Autor: Michał Hetnar
:::
## Zadanie 2
:::success
Autor: Szymon Mleczko
:::
https://miro.com/welcomeonboard/cU5raEJoMnpYYjFaenhEZWZVUUtSVHh0WktqRm5Sdk5BS0Z6S0ZUb2t0ak9zSkJybGEzNDNxQUxtNWU0Wkx2OHwzMDc0NDU3MzU1MTM0MjAyNjky?invite_link_id=74069848351
Kontrprzykład
// x = y + z // 1
// (x,y+z,1)
// y = 3;
//
## Zadanie 3
:::success
Autor: Adam Szeruda
:::
$$\begin{aligned}
F_{entry}(1) &= \emptyset &
F_{exit}(1) &= F_{entry}(1) \setminus \{(t, 5, x+y)\} \\
F_{entry}(2) &= F_{exit}(1) &
F_{exit}(2) &= F_{entry}(2) \setminus \{(t, 5, x+y\} \\
F_{entry}(3) &= F_{exit}(2) &
F_{exit}(3) &= F_{entry}(3) \\
F_{entry}(4) &= F_{exit}(3) \cap F_{exit}(8) &
F_{exit}(4) &= F_{entry}(4) \\
F_{entry}(5) &= F_{exit}(4) &
F_{exit}(5) &= F_{entry}(5) \setminus \{(t, 5, x+y)\} \cup \{(t, 5, x+y)\} \\
F_{entry}(6) &= F_{exit}(5) &
F_{exit}(6) &= F_{entry}(6) \setminus \{(t, 5, x+y)\} \\
F_{entry}(7) &= F_{exit}(6) &
F_{exit}(7) &= F_{entry}(7) \setminus \{(t, 5, x+y)\} \\
F_{entry}(8) &= F_{exit}(7) &
F_{exit}(8) &= F_{entry}(8) \\
F_{entry}(9) &= F_{exit}(4) &
F_{exit}(9) &= F_{entry}(9) \setminus \{(t, 5, x+y)\} \\
\end{aligned}$$
Rozwiązanie:
$$\begin{aligned}
F_{entry}(6) &= \{(t,5,x+y)\} &
F_{exit}(5) &= \{(t,5,x+y)\} \\
F_{entry}(*) &= \emptyset &
F_{exit}(*) &= \emptyset \\
\end{aligned}$$
:::spoiler
```python
#!/usr/bin/env python
t = ("t", 5, "x+y")
all = {t, ("i", 8, "i+1")}
F_en = [all] * 10
F_ex = [all] * 10
while True:
F2_en = [set()] * 10
F2_ex = [set()] * 10
F2_en[1] = set()
F2_ex[1] = F_en[1] - {t}
F2_en[2] = F_ex[1]
F2_ex[2] = F_en[2] - {t}
F2_en[3] = F_ex[2]
F2_ex[3] = F_en[3]
F2_en[4] = F_ex[3] & F_ex[8]
F2_ex[4] = F_en[4]
F2_en[5] = F_ex[4]
F2_ex[5] = F_en[5] - {t} | {t}
F2_en[6] = F_ex[5]
F2_ex[6] = F_en[6] - {t}
F2_en[7] = F_ex[6]
F2_ex[7] = F_en[7] - {t}
F2_en[8] = F_ex[7]
F2_ex[8] = F_en[8] - {t}
F2_en[9] = F_ex[4]
F2_ex[9] = F_en[9] - {t}
if F2_en == F_en and F2_ex == F_ex:
for i, (en, ex) in enumerate(zip(F_en[1:], F_ex[1:])):
print(f"F_en({i+1}) = {str(en):20} F_ex({i+1}) = {str(ex):20}")
break
else:
F_en, F_ex = F2_en, F2_ex
```
:::
## Zadanie 4
:::success
Autor: Hubert Jabłoński
:::
$gen_{SLV}([x:=a]^l)=\{ x\in SLV_{exit}(l) ? FV(a) : \emptyset \}$
backwards i may
## Zadanie 5
:::success
Autor: Krzysztof Grynkiewicz
:::
### 1. while (𝑏) { ... }
```c
goto Test
Loop:
{...}
Test: if b goto Loop
```
Optymalizacja:
```c
if ~b goto End
Loop:
{...}
Test: if b goto Loop
End:
```
### 2. for (𝑖 = 0; 𝑖 < 𝑛; 𝑖 ++) { ... }
```c
i := 0
goto Test
Loop:
{...}
i := i + 1
Test: if i < n goto Loop
```
Optymalizacja:
```c
i := 0
if i >= n goto End
Loop:
{...}
i := i + 1
Test: if i < n goto Loop
End:
```
### 3. do {...} while (𝑏)
```c
Loop:
{...}
Test: if b goto Loop
```
## Zadanie 6
:::success
Autor: Filip Komorowski
:::
Poprawiona wersja z mem jako tablicą:
## Zadanie 7
:::success
Autor: Emil Kisielewicz
:::
Insertion sort, pseudokod:
```
i ← 1
while i < length(A)
j ← i
while j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j ← j - 1
end while
i ← i + 1
end while
```
W kodzie trójkowym:
```
i := 1
W1: if i >= n goto E1
j := i
W2: if j <= 0 goto E2
t1 := j * 4 // adres t[i]
t2 := t[t1] // np. t5 = t + t1; t2 = *t5
t3 := t1 - 4 // adres t[i-1]
t4 := t[t3]
if t2 >= t4 goto E2
t[t3] := t2 // swap
t[t1] := t4
j := j - 1
goto W2
E2: i := i + 1
goto W1
E1:
```
## Zadanie 8
:::danger
Autor: do-deklarować
:::
## Zadanie 8
:::success
Autor: Jan Dalecki
:::
### 1. Układ sekwencyjny z jednym CSA
Posiadamy jeden moduł carry-save adder, który w pierwszym cyklu przeprowadzi obliczenia na b0A, b1A, b2A. Wynik takiego pośredniego obliczenia będziemy zapisywać w dwóch rejestrach Reg0 i Reg1, które na początku przechowują wartości b0A, b1A. Do 3 wejścia CSA podajemy w każdym cyklu kolejne wartości b2A, b3A i b4A.
Układ ten symuluje układ kombinacyjny z 3 sumatorami CSA. Każdy cykl to przejście do kolejnego poziomu. Po 3 cyklu na wyjściu RCA otrzymamy wynik mnożenia.
Reg2:0 przechowuje wyniki p0, p1, p2 które są uzyskiwane na każdym poziomie w układzie kombinacyjnym.
### 2. Układ sekwencyjny z 3 CSA
W tym układzie pamiętamy każde obliczenia wykonane przez sumatory CSA. Dzięki temu możemy skrócić czas na obliczenie dużej liczby kolejnych par liczb. Bez pamięci czas zegara byłby ograniczony przez czas obliczenia całego układu. Wprowadzając rejestry możemy zwiększyć częstotliwość zegara, który ograniczamy jedynie czasem RCA.
Google Drive
Gist
Clipboard
Sign in with Wallet
