Santa Claus — 2022-11-28 23:59 (37 days ago) — edit — reply
1. Pro každou možnou poslopnost na vstupu, kterých je $2^k$ si připravíme mezivýstup z hradla takto:
Všechny vstupy proženeme AND hradlem, vstupy, které mají být pro daný vstup nulové, nejdříve znegujeme. Toto nám zabere pro každou možnou posloupnost maximálně hloubku $k$ - a to pokud použijeme najivní AND hradlo postavené z $k-1$ binárních AND hradel.
2. Pro každý z těchto vstupů vytvoříme nulární hradlo, výstupem bude požadovaná hodnota pro danou posloupnost. Pak přivedeme na binární AND tuto konstantu a předpřipravený mezivýstup indikující danou posloupnost na vstupu.
3. Nyní máme $2^k$ výstupů, ty nyní proženeme OR hradlem. Protože už máme daleko větší počet mezivstupů, využijeme tentokráte nenaivní přístup, a sice na binární OR hradlo vždycky přivedeme mezivýstupy z předchozí vrstvy našeho velkého OR hradla.
Takto na každé vrstvě zmenšíme počet mezivýstupů na polovinu, celková hloubka velkého OR hradla bude $\log_2 2^k = k$.
Jediný výstup nám určuje požadovaný výstup.
## Správnost
Aby na výstupu byla jednička pro požadovanou posloupnost, musí být aktivní indikátor dané posloupnosti, což je právě jeden. Ten spojíme AND hradlem s požadovanou hodnotou: pokud je to nula, bude to vždy nula, jinak jednička pouze při aktivním indikátorovém mezivýstupu. No a jakmile máme tento jeden mezivýstup nastaven na jedničku, projde velkým OR hradlem až na výstup.
## Hloubka
1. Naivní AND s $k$ vstupy - hloubka $k$. Pro každý z $2^k$ vstupů, ale paralelně.
2. Nulární hradlo a jeden AND - hloubka $2$
3. Velké OR hradlo - jak jsem náhledl, hloubka $k$.
## Velikost
1. Naivní AND s $k$ vstupy - $k - 1$ hradel pro vstup, $k \cdot 2^k \in O(2^k)$
2. Nulární hradlo a jeden AND - hloubka $2 \cdot 2^k \in O(2^k)$
3. Velké OR hradlo - $2^k + 2^{k-1} + ... + 1 \in O(2^k)$ geometrická řada
## Optimalizace
Ve skutečnosti se můžeme vykašlat na vstupy, pro které máme dát nulu. Případně můžeme prohodit nulu a jedničku. Pokud chceme pro většinu vstupů vypsat stejný výstup, může nám toto velmi ušetřit prostor.