From 8b8cafc3bddcc9341e5b3dfd48a9015a17e63f88 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 29 Dec 2006 19:30:43 +0100 Subject: [PATCH] Preklepy. --- 10-decomp/10-decomp.tex | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/10-decomp/10-decomp.tex b/10-decomp/10-decomp.tex index 1727415..02e4fd0 100644 --- a/10-decomp/10-decomp.tex +++ b/10-decomp/10-decomp.tex @@ -17,7 +17,7 @@ zda dva vrcholy le v~Kruskalovì algoritmu pro hledání minimální kostry. \s{Triviální øe¹ení:} Ka¾dé tøídì pøiøadíme unikátní barvu, kterou obarvíme prvky tøídy. Operace \ -porovává barvy, operace \ prvky jedné tøídy pøebarví. +porovnává barvy, operace \ prvky jedné tøídy pøebarví. Operace \ tak pracuje v~konstantním èase, \ mù¾e zabrat a¾ lineární. Mù¾eme si ale pomoci tím, ¾e v¾dy pøebarvíme {\I men¹í} ze~sluèovaných ekvivalenèních tøíd (budeme @@ -75,7 +75,7 @@ alespo listù makrostromu je nejvý¹e $n/\log n$. Vnitøních vrcholù makro- i mikrostromù ale mù¾e být ne¹ikovnì mnoho, proto¾e se ve~stromech mohou -vyskytovat dlouhé cesty. Pomu¾eme si snadno: ka¾dou cestu si budeme pamatovat zvlá¹» a ve~stromu +vyskytovat dlouhé cesty. Pomù¾eme si snadno: ka¾dou cestu si budeme pamatovat zvlá¹» a ve~stromu ji nahradíme hranou, která bude existovat právì tehdy, kdy¾ budou pøítomny v¹echny hrany cesty. \s{Algoritmus pro cesty:} Cestu délky~$l$ rozdìlíme na~úseky délky $\log n$, pro nì¾ si pamatujeme @@ -100,7 +100,7 @@ amortizovan \s{Algoritmus pro mikrostromy:} Po~kompresi cest má ka¾dý mikrostrom nejvý¹e $2\log n$ vrcholù, èili také nejvý¹e tolik hran. Hrany si oèíslujeme pøirozenými èísly, ka¾dou mno¾inu hran pak mù¾eme reprezentovat $2\log n$-bitovým èíslem a mno¾inové operace -provádìt pomocí bitových v~konstatním èase. +provádìt pomocí bitových v~konstantním èase. Pro ka¾dý mikrostrom si pøedpoèítáme pro v¹echny jeho vrcholy~$v$ mno¾iny~$P_v$ hran le¾ících na~cestì z~koøene mikrostromu do~$v$. Navíc si budeme pamatovat mno¾inu pøítomných hran~$F$. @@ -163,7 +163,7 @@ $G$ na~souvisl \itemize\ibull \:$\forall v \in V \exists ! i: v \in C_i$. \:$\forall i: \vert C_i\vert \le c$. -\:$\forall i$ je vnìj¹i stupeò $C_i$ (tj. poèet hran, které vedou mezi $C_i$ a zbytkem grafu) +\:$\forall i$ je vnìj¹í stupeò $C_i$ (tj. poèet hran, které vedou mezi $C_i$ a zbytkem grafu) nejvý¹e~3. Navíc pokud je právì~3, je cluster triviální, èili $\vert C_i \vert = 1$. \:®ádné dva sousední clustery nelze spojit. \endlist @@ -265,7 +265,7 @@ prvku amortizovan Výsledky této podkapitoly mù¾eme shrnout do~následující vìty: -\s{Vìta:} Problémy LCA i RMQ je mo¾né øe¹it v~konstatním èase na~dotaz +\s{Vìta:} Problémy LCA i RMQ je mo¾né øe¹it v~konstantním èase na~dotaz po~pøedzpracování v~lineárním èase. \bye -- 2.39.5