From 9f1aa90d1b286e2feae6b765ebb594675e72ffea Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 28 Nov 2019 15:07:37 +0100 Subject: [PATCH] =?utf8?q?Floyd:=20Drobn=C3=A9=20opravy?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- 14-floyd/14-floyd.tex | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/14-floyd/14-floyd.tex b/14-floyd/14-floyd.tex index b3b2dc2..56cf382 100644 --- a/14-floyd/14-floyd.tex +++ b/14-floyd/14-floyd.tex @@ -106,8 +106,8 @@ výrazy konečné délky sestávající z~triviálních svazků a výše uveden operací. \s{Pozorování:} Sledy můžeme reprezentovat řetězci nad abecedou, jejíž -symboly jsou identifikátory hran. Sledové výrazy pak odpovídají regulárním -výrazům nad touto abecedou. +symboly jsou identifikátory hran. Sledové výrazy pak odpovídají (typovaným) +regulárním výrazům nad touto abecedou. Ukážeme, jak pro všechny dvojice vrcholů $i,j$ sestrojit sledový výraz $R_{ij}$ popisující svazek všech sledů z~$i$ do~$j$. Podobně jako u~Floydova-Warshallova @@ -305,7 +305,7 @@ a $\O(1)$ součtů matic. $$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)$. +má tato rekurence podle kuchařkové věty řešení $t(n) \in \O(\mu(n))$. Ukázali jsme tedy, že výpočet matice dosažitelnosti je nejvýše stejně náročný jako $(\lor,\land)$-násobení matic -- můžeme ho proto provést -- 2.39.2