---
# System prepended metadata

title: 'Ćwiczenia 3, grupa śr. 12-14, 13 marca 2024'
tags: [pwit, ćwiczenia, SYK24]

---

# Ćwiczenia 3, grupa śr. 12-14, 13 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   |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- |
Mikołaj Balwicki         |      |     |     |     |     |     |     | 
Małgorzata Galińska      |   ==X==   |   X  |     |     |     |  X   |  X   |
Maria Hreniak            |   X   |  ==X==   |     |     |     |  X   |   X  |
Jakub Jankowski          |   X   |  X   |     |     |     |  X   |   X  |
Mikołaj Kalitka          |   X   |   X  |     |     |     |   X  |  X   |
Julia Konefał            |  X    |  X   |     |     |     |  ==X==   |  X   |
Julia Kulczycka          |   X   |  X   |     |     |     |  X   |   X  |
Cecylia Łyjak            |      |     |     |     |     |     |     |
Adam Majchrowski         |   X   |   X  |     |     |  ==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 **6** i **8** z **listy 2**:

:::danger
| Imię i nazwisko        | 2.6  | 2.8  |
| ----------------------:| -----| -----|
                         |      |      | 
                         |      |      |
:::



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



## Zadanie 1
:::success
Autor: 	Małgorzata Galińska	
:::
![image](https://hackmd.io/_uploads/SJwsyGyR6.png)


Kodowanie Bootha polega na dodaniu dodatkowej wartości bitu: (-1). Tym sposobem możemy wyrażać długie ciągi jedynek …0111110… jako …10000(-1)0… i czasami dzięki temu oszczędzać czas przy mnożeniu dwóch liczb. Jeśli liczba A to powyższa liczba i mamy wymnożyć ją przez B, to zamiast 5 razy mnożyć B i 4 razy do siebie dodawać, wymnożymy B raz przez 1 i raz przez (-1) i dodamy te dwie liczby do siebie. 

W układzie mnożącym dwie liczby w naturalnym kodzie binarnym będziemy sprawdzać dwa sąsiednie bity jakiej są postaci:
•	10 – rozpoczyna się ciąg jedynek, odejmujemy od wyniku B
•	11 – jesteśmy w ciągu jedynek, nie robimy nic
•	00 – jesteśmy w ciągu zer, nie robimy nic
•	01 – koniec ciągu jedynek, dodajemy do wyniku B

Inicjalizacja: Dodaj jedną dodatkową pozycję bitową po prawej stronie liczby A, ustawiając ją na 0.
1.	Podział liczby A: Podziel A na grupy bitów o długości 2 (11, 00, 01, 10).
2.	Iteracje:
•	Dla każdej grupy bitów w A:
o	Jeśli bity to "00" lub "11", pozostaw P bez zmian.
o	Jeśli bity to "01", wykonaj operację P + B.
o	Jeśli bity to "10", wykonaj operację P - B.
3.	Przesunięcie bitowe: Po każdej iteracji przesuń bity P i A w prawo o jedno miejsce.

Aby mnożyć liczby ze znakiem należy zmienić zwykłe przesunięcie w prawo na arytmetyczne przesunięcie w prawo, aby móc zachować poprawny znak wyniku. 
![image](https://hackmd.io/_uploads/r1mMzfJR6.png)
Zmodyfikowany algorytm:

Inicjalizacja: Dodaj jedną dodatkową pozycję bitową po prawej stronie liczby A, ustawiając ją na 0.
1.	Podział liczby A: Podziel A na grupy bitów o długości 2 (np., 00, 01, 10).
5.	Iteracje:
•	Dla każdej grupy bitów w A:
o	Jeśli bity to "00" lub "11", pozostaw P bez zmian.
o	Jeśli bity to "01", wykonaj operację P + B.
o	Jeśli bity to "10", wykonaj operację P - B (jeśli B jest ujemne, to jest to jednoznaczne z dodaniem liczby przeciwnej do B)
6.	Przesunięcie bitowe: Po każdej iteracji przesuń bity P i A arytmetycznie w prawo o jedno miejsce. Dzięki temu zachowujemy znak P.

Przykład działania:
![image](https://hackmd.io/_uploads/rJzdRZJCa.png)



## Zadanie 2
:::success
Autor: 	Maria Hreniak
:::
![image](https://hackmd.io/_uploads/SJrQRb1Aa.png)

![image](https://hackmd.io/_uploads/SkT4Ab1Rp.png)

PRZYKŁAD DZIELENIA:

![zad2przyklad](https://hackmd.io/_uploads/S1_DRZ1C6.png)


![image](https://hackmd.io/_uploads/r1VI0-kRT.png)





## Zadanie 3
:::danger
Autor: do zadeklarowania następnym razem
:::

## Zadanie 4
:::success
Autor:  Jakub Jankowski 
![image](https://hackmd.io/_uploads/S1b4u8dAT.png)
![image](https://hackmd.io/_uploads/ByVr_UdR6.png)

:::

## Zadanie 5
:::success
Autor: 	Adam Majchrowski
![image](https://hackmd.io/_uploads/H1UWA-yRp.png)
![image](https://hackmd.io/_uploads/BJZMC-yR6.png)
![image](https://hackmd.io/_uploads/Sy_MAZ1CT.png)
![image](https://hackmd.io/_uploads/SygQC-y0T.png)
![image](https://hackmd.io/_uploads/H1hRA-kAT.png)
![image](https://hackmd.io/_uploads/H1vI58_Ca.png)
:::

## Zadanie 6
:::success
Autor: 	Julia Konefał
![Screenshot from 2024-03-13 12-11-59](https://hackmd.io/_uploads/BkiQ0-yCa.png)
![431447541_937124674529237_5379457287536833122_n](https://hackmd.io/_uploads/HJiVA-J0T.jpg)
| $l$ | $RD_{\circ} (l)$                                                         | $RD_{\bullet} (l)$                                                       |
| --- | ------------------------------------------------------------------------ | ------------------------------------------------------------------------ |
| 1   | {(x, ?), (y, ?), (t, ?), (i, ?)}                                 | {(x, 1), (y, ?), (t, ?), (i, ?)}                                 |
| 2   | {(x, 1), (y, ?), (t, ?), (i, ?)}                                 | {(x, 1), (y, 2), (t, ?), (i, ?)}                                 |
| 3   | {(x, 1), (y, 2), (t, ?), (i, ?)}                                 | {(x, 1), (y, 2), (t, ?), (i, 3)}                                 |
| 4   | {(x, 1), (y, 2), (t, ?), (i, 3), (t, 5), (x, 6), (y, 7), (i, 8)} | {(x, 1), (y, 2), (t, ?), (i, 3), (t, 5), (x, 6), (y, 7), (i, 8)} |
| 5   | {(x, 1), (y, 2), (t, ?), (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), (t, ?), (i, 3), (t, 5), (x, 6), (y, 7), (i, 8)} | {(x, 1), (t, ?), (i, 3), (t, 5), (x, 6), (i, 8), (y, 9)}         |
:::

## Zadanie 7
:::success
Autor: 	Piotr Salamon	
- `Zadanie 7. Kompilator wygenerował kod pośredni, w którym
występuje następujący fragment. W jaki sposób zoptymalizować
go pod względem wydajności? Wymyśl odpowiednią analizę
przepływu danych: a) zdefiniuj ją słownie, b) zastanów się, w
jaki sposób powinien wyglądać pojedynczy fakt w takiej
analizie, c) napisz zbiory faktów prawdziwych na wejściu–do
oraz wyjściu–z każdej instrukcji tego programu.`

RD1◦ = {{x, ?}, {y, ?}, {z, ?}, ... (w każdym zbiorze mogą istnieć jeszcze inne zmienne, tutaj ich nie uwzględniam bo nie zajdą w nich zmiany) }
1: [𝑥 : = 10] 
RD1• = {{x, 10}, {y, ?}, {z, ?}}

RD2◦ = {{x, 10}, {y, ?}, {z, ?}}
2: [𝑦 : = 𝑥 + 10]
RD2• = {{x, 10}, {y, 20}, {z, ?}}

RD3◦ = {{x, 10}, {y, 20}, {z, ?}}
3: [𝑧 : = 𝑦 + 𝑥]
RD3• = {{x, 10}, {y, 20}, {z, 30}}

Optymalizacja

RD1◦ = {{x, ?}, {y, ?}, {z, ?}}
1: [𝑥 : = 10] 
RD1• = {{x, 10}, {y, ?}, {z, ?}}

RD2◦ = {{x, 10}, {y, ?}, {z, ?}}
2: [𝑦 : = 20]
RD2• = {{x, 10}, {y, 20}, {z, ?}}

RD3◦ = {{x, 10}, {y, 20}, {z, ?}}
3: [𝑧 : = 30]
RD3• = {{x, 10}, {y, 20}, {z, 30}}


:::


