Nova verze geometrickych zapisku.

[ads2.git] / 1-hradla / 1-hradla.tex

diff --git a/1-hradla/1-hradla.tex b/1-hradla/1-hradla.tex
index e1ecbae2480ecfc8d948299dc24138861a5699fe..6b75cc111302c2e38a6bb3ad20317d9dfb6fab0e 100644 (file)
--- a/1-hradla/1-hradla.tex
+++ b/1-hradla/1-hradla.tex
@@ -101,33 +101,33 @@ M
 Budeme chtít spoèítat jejich souèet $z_nz_{n-1}\ldots z_1z_0$.
 
 \h{Algoritmus základní ¹koly}
-Pøenosy oznaèíme $c_0$ a¾ $c_{n-1}$ v krocích poèítání, dodefinujeme $c_{-1}=0$. Algoritmus probíhá zleva od místa s nejni¾¹í vahou, viz Obrázek 1.6. 
+Pøenosy oznaèíme $c_0$ a¾ $c_{n-1}$ v krocích poèítání, dodefinujeme $c_{-1}=0$. Algoritmus probíhá zleva od místa s nejni¾¹í vahou, viz Obrázek 1.7. 
  
-Výsledné èíslo $z_{n}...z_1z_0$ lze tedy vyjádøit pøedpisem $$z_i=x_i \oplus y_i \oplus c_{i-1}$$ kde $\oplus$ znaèí operaci XOR. Pøenos nastane, pokud je alespoò 1 èíslo jednièka, tedy
+Výsledné èíslo $z_{n}...z_1z_0$ lze tedy vyjádøit pøedpisem: $$z_i=x_i \oplus y_i \oplus c_{i-1},$$ kde $\oplus$ znaèí operaci XOR. Pøenos nastane, pokud jsou alespoò dvì èísla jednièky, tedy
 $$c_i=(x_i \land y_i)\lor((x_i \lor y_i) \land c_{i-1})$$.
-\figure{1_6_hloupe_scitani.eps}{Obrázek 1.7 sèítání}{8cm}
-Bohu¾el na to abychom spoèítali $z_i$ musíme znát hodnotu $c_{i-1}$, tedy mít spoèítané hodnoty pro v¹echny èísla men¹í ne¾ i. To dává lineární èasovou slo¾itost. Zamysleme se nad tím jak by se proces sèítání mohl zrychlit.
+\figure{1_6_hloupe_scitani.eps}{Obrázek 1.7 -- Sèítání}{8cm}
+Bohu¾el na to abychom spoèítali $z_i$ musíme znát hodnotu $c_{i-1}$, tedy mít spoèítané hodnoty pro v¹echny èísla men¹í ne¾ $i$. To dává lineární èasovou slo¾itost. Zamysleme se nad tím jak by se proces sèítání mohl zrychlit.
 
-\h{Trik - chování blokù souètu}
+\h{Trik -- chování blokù souètu}
 
-\figure{1_7_blok_scitani.eps}{Obrázek 1.8 - Blok souètu}{8cm}
+\figure{1_7_blok_scitani.eps}{Obrázek 1.8 -- Blok souètu}{8cm}
 \>Blok se mù¾e chovat tøemi rùznými zpùsoby:
 
 \numlist{\ndotted}
-\:V¾dy vydá pøenos 0 
-\:V¾dy vydá pøenos 1
-\:Kopíruje (pøedá dál)
+\:V¾dy vydá pøenos 0,
+\:V¾dy vydá pøenos 1,
+\:Kopíruje (pøedá dál).
 \endlist
 
 \h{Rozdìlení a skládání blokù}
-Blok B lze rozdìlit na 2 bloky p,q (pokud B není trivální)
-\figure{1_10_konvence_deleni_bloku.eps}{Obrázek 1.9 - Dìlení blokù}{3cm}
+\>Blok B lze rozdìlit na dva bloky p, q (pokud B není trivální).
+\figure{1_10_konvence_deleni_bloku.eps}{Obrázek 1.9 -- Dìlení blokù}{3cm}
 
 
 \h{Triviální bity}
-\figure{1_11_tabulka_kodovani.eps}{Obrázek 1.10 - Tabulka triviálních bitù}{3cm}
+\figure{1_11_tabulka_kodovani.eps}{Obrázek 1.10 -- Tabulka triviálních bitù}{3cm}
 
-\s{Tvrzení:} Ka¾dý blok mohu postavit z triviálních bitù. 
+\s{Tvrzení:} Ka¾dý blok mohu postavit z~triviálních bitù. 
 
 \proof 
 Dùkaz indukcí z asociativity.
@@ -137,31 +137,31 @@ D
 \h{Kódování typù chování blokù}
 %\>{\I Sem tabulku prosím :)}
 
-\>Definujeme (a,x) : 
+\>Definujeme $(a,x)$:
 \itemize\ibull
-\:$(1,*) = <$
-\:$(0,0) = 0$
+\:$(1,*) = <$,
+\:$(0,0) = 0$,
 \:$(0,1) = 1$
 \endlist
 
-\>a operaci skládání blokù $\sigma$ pro kterou platí
+\>a operaci skládání blokù $\sigma$ pro kterou platí:
 
-$(a,x) \sigma (b,y) = (c,z)$
+$(a,x) \sigma (b,y) = (c,z)$,
 
 \>kde
 
-$c = a \land b$
+$c = a \land b$,
 
-$z = (\neg a \land x) \lor (a \land y)$
+$z = (\neg a \land x) \lor (a \land y)$.
 
 
 
 \h{Lep¹í algoritmus sèítání}
-V na¹em pùvodním algoritmu ze základní ¹koly jsme mìli O(n) hradel v O(n) hladinách. Algoritmus tedy nebyl paralelní a trval èas O(n).
+V na¹em pùvodním algoritmu ze základní ¹koly jsme mìli $\O(n)$ hradel v~$\O(n)$ hladinách. Algoritmus tedy nebyl paralelní a trval èas $\O(n)$.
 
-\figure{1_9_deleni_bloku.eps}{Obrázek 1.11 - Výpoèet pøenosu}{8cm}
+\figure{1_9_deleni_bloku.eps}{Obrázek 1.11 -- Výpoèet pøenosu}{8cm}
 Víme pro ka¾dý blok velikosti $2^k$ na pozici dìlitelné $2^k$ jeho chování.
-Teï, kdy¾ u¾ známe v¹echny zbytky $c_0$ a¾ $c_n$ mù¾eme u¾ jednodu¹e v konstantním èase spoèítat výsledek.
+Teï, kdy¾ u¾ známe v¹echny zbytky $c_0$ a¾ $c_n$, mù¾eme u¾ jednodu¹e v konstantním èase spoèítat výsledek.