X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=4-hradla%2F4-hradla.tex;h=7c77f036165c87b75840fc6d563be8fe3f9626c7;hb=582ed5145e870105f25a1bb5b459e6c0808027b4;hp=cbe23def5e70aabac5aaf5e6127fdc7aafcf75ca;hpb=61b142de4510f91205a3a55691a71ece9f06f8c4;p=ads2.git

diff --git a/4-hradla/4-hradla.tex b/4-hradla/4-hradla.tex
index cbe23de..7c77f03 100644
--- a/4-hradla/4-hradla.tex
+++ b/4-hradla/4-hradla.tex
@@ -1,6 +1,6 @@
 \input ../lecnotes.tex
 
-\prednaska{4}{Hradlové sítì a paralelní algoritmy}{(zapsal: Petr Jankovský)}
+\prednaska{4}{Hradlové sítì}{(zapsal: Petr Jankovský)}
 
 \def\land{\mathbin{\&}}
 
@@ -15,33 +15,34 @@ a 
 zamìstnáme je pøi~výpoètu v¹echny.
 
 My se podíváme na~abstraktní výpoèetní model, který je je¹tì paralelnìj¹í.
-Techniky, které si uká¾eme na~tomto modelu, se v¹ak dají pøekvapivì vyu¾ít
-i~pøi~reálném paralelizování na~nìkolik málo procesorù. Budeme se zabývat 
+Techniky, které si uká¾eme na~tomto modelu, se v¹ak dají pøekvapivì vyu¾ít i~pøi~reálném
+paralelizování na~nìkolika málo procesorech. Konec koncù i proto, ¾e vnitøní
+architektura procesoru se na¹emu modelu velmi podobá. Budeme se zabývat 
 jednoduchým modelem paralelního poèítaèe, toti¾ hradlovou sítí.
 
 \h{Hradlové sítì}
 
 \s{Definice:} {\I Hradlo} je prvek, který umí vyhodnocovat nìjakou funkci
-nad~koneènou abecedou.
-$$f: {\sum}^{k} \rightarrow \sum$$
+nad~koneènou abecedou $\Sigma$.
 
-Obecnì se na~hradlo díváme jako na~funkci, která dostane $k$ vstupù a~vrátí jeden
-výstup, pøièem¾ hodnoty, nad~kterými pracuje, budou z~nìjaké koneèné abecedy -- 
-tedy z~nìjaké koneèné mno¾iny symbolù $\sum$. Písmenku $k$ zde øíkáme {\I arita hradla}.
+Obecnì se na~hradlo díváme jako na~funkci $f: {\Sigma}^{k} \rightarrow \Sigma$, která dostane $k$ vstupù
+a~vrátí jeden výstup, pøièem¾ hodnoty, nad~kterými pracuje, budou z~nìjaké koneèné
+abecedy -- tedy z~nìjaké koneèné mno¾iny symbolù $\Sigma$. Písmenku $k$ zde øíkáme {\I arita
+hradla}.
 
-\s{Pøíklad:} Èasto studujeme hradla booleovská, která poèítají nìjaké logické funkce.
+\s{Pøíklad:} Èasto studujeme hradla booleovská (pracující nad abecedou $\{0,1\}$), která poèítají logické funkce.
 
 Z~nich nejèastìji potkáme:
 
 \itemize\ibull
-\:nulární: to jsou konstanty (0, 1, ...  -- zkrátka jakákoli konstanta abecedy),
+\:nulární: to jsou konstanty (FALSE=0, TRUE=1),
 \:unární: napø. negace (znaèíme~$\lnot$),
 \:binární: logický souèin ({\sc and},~$\land$), souèet ({\sc or},~$\lor$), ...
 \endlist
 
 \>Hradla kreslíme tøeba následovnì:
 
-\figure{hradlo_and.eps}{Binární hradlo provádìjící logickou operaci {\sc and}.}{1in}
+\figure{hradlo_and.eps}{Binární hradlo provádící logickou operaci {\sc and}.}{1in}
 
 Jednotlivá hradla mù¾eme navzájem urèitým zpùsobem propojovat a vytváøet
 z nich {\I hradlové sítì}. Pokud pou¾íváme pouze booleovská hradla, øíkáme takto vytvoøeným
@@ -51,7 +52,7 @@ mno
 Ka¾dá hradlová sí» má nìjaké vstupy, nìjaké výstupy a uvnitø jsou propojovaná
 hradla. Ka¾dý vstup hradla je pøipojen buïto na~nìkterý ze~vstupù sítì nebo
 na~výstup jiného hradla. Výstupy hradel mohou být propojeny na~vstupy dal¹ích
-hradel a mohou se vìtvit, nebo na výstupy sítì. Pøitom máme zakázáno vytváøet
+hradel (mohou se vìtvit), nebo na výstupy sítì. Pøitom máme zakázáno vytváøet
 cykly. 
 
 Ne¾ si øekneme formální definici, podívejme se na obrázek.
@@ -79,13 +80,13 @@ jedni
 \:$\forall i \in I: \deg^{in}(i)=0$ (do~vstupù nic nevede);
 \:$\forall o \in O: \deg^{in}(o)=1~\land~\deg^{out}(o)=0$ (z~výstupù nic nevede a do~ka¾dého vede právì jedna hrana);
 \:$\forall h \in H: \deg^{in}(v)=a(v)$ (do~ka¾dého hradla vede tolik hran, kolik je jeho arita);
-\:$\forall h \in H~\forall j: 1\le j\le a(h)$ existuje právì jedena hrana~$e$ taková, ¾e $z(e)=j$, $e$ konèí v $h$
+\:$\forall h \in H~\forall j: 1\le j\le a(h)$ existuje právì jedena hrana~$e$ taková, ¾e~$e$ konèí v~$h$ a~$z(e)=j$, 
   (v¹echny vstupy hradel jsou zapojeny).
 \endlist
 
 \s{Pozorování:} Kdybychom pøipustili hradla s~libovolnì vysokým poètem vstupù, mohli
 bychom libovolný problém se vstupem délky~$n$ vyøe¹it jedním hradlem o~$n$~vstupech,
-kterému bychom pøiøadili funkci, která by na¹i úlohu rovnou vyøe¹ila... Tento model,
+kterému bychom pøiøadili funkci, která by na¹i úlohu rovnou vyøe¹ila. Tento model
 v¹ak není ani realistický, ani pìkný. Proto pøijmìme omezení, ¾e~arity v¹ech hradel
 budou omezeny nìjakou pevnou konstantou $k$ (uká¾e se, ¾e nám bude staèit dvojka
 a~vystaèíme si tedy pouze s nulárními, unárními a binárními hradly). 
@@ -95,15 +96,15 @@ N
 
 
 Nyní bychom je¹tì mìli definovat, co taková hradlová sí» vlastnì poèítá a~jak
-vlastní výpoèet probíhá.
+její výpoèet probíhá.
 
 \s{Definice:} {\I Výpoèet sítì} probíhá po~{\I taktech.} V nultém taktu jsou definovány pouze 
-hodnoty na~vstupech a na~hradlech arity 0. Mù¾eme si to pøedstavit tak, ¾e na~zaèátku
-nemá ¾ádné hradlo definovánu výstupní hodnotu (a¾ na ji¾ zmínìná hradla
-nulární). V~ka¾dém dal¹ím taktu pak vydají výstup hradla, která na~konci minulého
-taktu mìla definovány v¹echny hodnoty na vstupech. Jakmile budou po~nìjakém 
-koneèném poètu taktù definované i hodnoty v¹ech výstupù, sí» se zastaví a~vydá
-výsledek.
+hodnoty na~vstupech sítì a na~výstupech hradel arity 0. Mù¾eme si to pøedstavit
+tak, ¾e na~zaèátku nemá ¾ádné hradlo definovánu výstupní hodnotu (a¾ na ji¾ 
+zmínìná hradla nulární). V~ka¾dém dal¹ím taktu pak vydají výstup hradla, která
+na~konci minulého taktu mìla definovány v¹echny hodnoty na vstupech. Jakmile
+budou po~nìjakém koneèném poètu taktù definované i hodnoty v¹ech výstupù, sí»
+se zastaví a~vydá výsledek.
 
 \s{Pozorování:} Proto¾e je sí» acyklická, je jasné, ¾e jakmile jednou nìjaké hradlo vydá
 výstup, tak se tento výstup bìhem dal¹ího výpoètu sítì ji¾ nezmìní.
@@ -127,12 +128,12 @@ vyskytuje alespo
 slo¾itost odpovídají~$\Theta(n)$. Zde ov¹em vùbec nevyu¾íváme toho, ¾e by mohlo poèítat více
 hradel souèasnì.
 
-\figure{hloupy_or.eps}{Hradlová sí», která zjistí, zda-li je na vstupu alespoò jedna jednièka.}{0.7in}
+\figure{hloupy_or.eps}{Hradlová sí», která zjistí, zdali je na vstupu alespoò jedna jednièka.}{0.7in}
 
 \>{\I Druhé øe¹ení:} Hradla budeme spojovat do~dvojic, pak výsledky z~tìchto dvojic opìt
 do~dvojic a tak dále. Díky paralelnímu zapojení dosáhneme èasové slo¾itosti $\Theta(\log n)$,
 prostorová slo¾itost zùstane lineární.
 
-\figure{chytry_or.eps}{Chytøej¹í øe¹ení stejného problému.}{1.7in}
+\figure{chytry_or.eps}{Chytøej¹í øe¹ení stejného problému pro vstup velikosti 16.}{3in}
 
 \bye