Floyd: Drobne korektury

[ga.git] / 14-floyd / 14-floyd.tex

diff --git a/14-floyd/14-floyd.tex b/14-floyd/14-floyd.tex
index 91897462779416f4de4b44a1d31894d1b3c48c2a..45508a0ecf50ef5c639a6de169f800e9a4ff7d8e 100644 (file)
--- a/14-floyd/14-floyd.tex
+++ b/14-floyd/14-floyd.tex
@@ -285,12 +285,12 @@ op
 \endlist
 
 \s{Algoritmus:}
-Výpoèet matice~$A^*$ provedeme podle pøedchozí vìty. Spoèítáme 3~tranzitivní uzávìry
+Výpoèet matice~$A^*$ provedeme podle pøedchozí vìty. Spoèítáme 2~tranzitivní uzávìry
 matic polovièní velikosti rekurzivním voláním, dále pak $\O(1)$ $(\lor,\land)$-souèinù
 a $\O(1)$ souètù matic.
 
 Èasová slo¾itost $t(n)$ tohoto algoritmu bude splòovat následující rekurenci:
-$$t(1)=\Theta(1), \quad t(n) = 3t(n/2) + \Theta(1)\cdot\mu(n/2) + \Theta(n^2),$$
+$$t(1)=\Theta(1), \quad t(n) = 2t(n/2) + \Theta(1)\cdot\mu(n/2) + \Theta(n^2),$$
 kde $\mu(k)$ znaèí èas potøebný na jeden $(\lor,\land)$-souèin
 matic $k\times k$. Jeliko¾ jistì platí $\mu(n/2)=\Omega(n^2)$,
 má tato rekurence podle kuchaøkové vìty øe¹ení $t(n) = \mu(n)$.
@@ -337,7 +337,7 @@ $d'(u) < d(v)$ a pro v
 
 Prùmìry pøes sousedy pøitom mù¾eme spoèítat násobením matic: vynásobíme matici
 vzdáleností~$D'$ maticí sousednosti grafu~$G$. Na pozici~$i,j$ se objeví souèet
-hodnot $D_{ik}$ pøes v¹echny sousedy~$k$ vrcholu~$j$. Ten staèí vydìlit stupòem
+hodnot $D'_{ik}$ pøes v¹echny sousedy~$k$ vrcholu~$j$. Ten staèí vydìlit stupòem
 vrcholu~$j$ a hledaný prùmìr je na svìtì.
 
 Po~provedení jednoho násobení matic tedy dovedeme pro ka¾dou dvojici vrcholù