---
# System prepended metadata

title: Zadanie 1
tags: [SYK24]

---

## Zadanie 1
//Zdjecie tresci 1

Generowanie przeniesienia: na podstawie bitów a_i i b_i (niezależnie od przeniesienia c_in) => a_i AND b_i

Propagacja przeniesienia: patrzymy na c_in, kiedy jest równe 1 to przeniesiemy jeżeli a_i lub b_i => a_i OR b_i

//Zdjecie wzorow do 1

//Zdjecie układu + zdjecie czasu

wiersze wykonuja sie równolegle (najpierw cały górny na raz, potem wiersz 1 itd.)

rozmiar (liczba bramek) = 2*(n+1) + 3*n/2*log(n) + 2*n

(pierwszy wiersz, wszystkie pomiędzy 1 i ostatnim, ostatni wiersz)

## Zadanie 2
//Zdjecie tresc 2
// Zdjecie do zad 2
// Zdjecie legenda do 2

Rozmiar:
2n -> gorne kwadraty liczace gi,pi (n kwadratow kazdy po 2 bramki)
2n -> dolne kwadraty liczace Si (n kwadratow kazdy po 2 bramki)
ilosc czarnych kwadratow -> n*logn - (2^0 + 2^1 + 2^2 + ... + 2^(logn-1)) = n*logn - n + 1  
każdy czarny ma 3 bramki więc łącznie z czarnych 3*(nlogn - n +1)

Zatem łącznie: 4n+3(nlogn - n +1)

## Zadanie 3
//Zdjecie tresc 1
//Zdjecie part 1
//Zdjecie part 2
//Zdjecie part 3

Czas: 2*logn + 1 => O(logn) przejscie 2 razy po drzewie o wysokosci logn oraz wyliczenie sumy na koniec

Rozmiar:
1. n bloków "A" => n*4 (4 bramki w bloku "A")
2. ilość bloków "B" dąży do n => "B"* n*(1/2 + 1/4 + 1/8 ...) = "B"*n*1 = n * 5 (5 bramek w bloku "B")
3. Łącznie rozmiar => 4n+5n = 9n


## Zadanie 4
//Zdjecie tresci do 4
//Zdjecie calego ukladu
//Zdjecia (legenda) blok C + wzory do 4

c = n/k
n - ilosc bitow
c - ilosc blokow C
k - "szerokosc" bloku C


Rozmiar:
1. FA -> 5 bramek => 5*n
2. Bloki C -> w jednym C jest k bloków "1" i około k bloków "2" (blok "1" - 2 bramki, blok "2" - 3 bramki) => k*2 + k*3 = 5k. Bloków c jest n/k więc łącznie n/k * 5k = 5n
3. Bloki B -> każdy blok B ma 5 bramek, a jest ich około c (bo c*(1/2 + 1/4 ...) = c) => więc łącznie 5*c

Sumując wychodzi -> 5n+5n+5c = 10n+5c

Czas:
log(n/m) + log(n/m) + 3m

## Zadanie 5