From d26cf3cba04958b6de7c2acbebba2646af8f200d Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 24 Nov 2020 23:36:35 +0100 Subject: [PATCH] =?utf8?q?Floyd:=20Drobn=C3=A9=20korektury?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- 14-floyd/14-floyd.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/14-floyd/14-floyd.tex b/14-floyd/14-floyd.tex index 56cf382..4c655e7 100644 --- a/14-floyd/14-floyd.tex +++ b/14-floyd/14-floyd.tex @@ -93,7 +93,7 @@ těmito operacemi: \:$AB$ nebo $A\cdot B$ -- {\I zřetězení} $uv$-svazku~$A$ s~$vw$-svazkem~$B$: výsledkem je $uw$-svazek obsahující všechna spojení sledu z~$A$ se sledem z~$B$, \:$A^*$ -- {\I iterace} $uu$-svazku: výsledkem je $uu$-svazek -$\varepsilon \cup A \cup AA \cup AAA \cup \ldots$ (tedy všechna možná +$\varepsilon_u \cup A \cup AA \cup AAA \cup \ldots$ (tedy všechna možná spojení konečně mnoha sledů z~$A$). \endlist @@ -233,7 +233,7 @@ Podobně jako v~předchozí sekci si tedy můžeme pořídit funkci~$f$ přiřaz svazkům hodnoty z~nějaké množiny~$X$ a operace $\oplus$ a $\otimes$ na~$X$, pro něž platí $f(\alpha\cup\beta) = f(\alpha) \oplus f(\beta)$ a $f(\alpha\beta) = f(\alpha) \otimes f(\beta)$. Pak stačí vzít matici popisující ohodnocení -všech sledů délky 0 nebo~1 (to je obdoba matice sousednosti), a provést $\O(\log n)$ +všech sledů délky~1 (to je obdoba matice sousednosti), a provést $\O(\log n)$ $(\oplus,\otimes)$-součinů k~tomu, abychom znali ohodnocení svazků sledů délky právě~$k$ pro nějaké $k\ge n$. -- 2.39.2