From 0a2d2e26d27b27dde5a074a82af8bbee855e2aa6 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Sun, 30 Jan 2011 22:08:52 +0100
Subject: [PATCH] APSP: Metoda Rozdel a panuj

Tim by kapitola mela byt hotova, tedy az na korektury.
---
 14-floyd/14-floyd.tex | 61 ++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 57 insertions(+), 4 deletions(-)

diff --git a/14-floyd/14-floyd.tex b/14-floyd/14-floyd.tex
index e0a0cb8..122cce9 100644
--- a/14-floyd/14-floyd.tex
+++ b/14-floyd/14-floyd.tex
@@ -236,10 +236,65 @@ Dodejme je
 celou øadu dal¹ích trikù. Zájemce o~tento druh algoritmù odkazujeme na Zwickùv
 èlánek~\cite{zwick:apspint}.
 
+\h{Rozdìl a panuj}
+
+Pøedchozí pøevod je ov¹em trochu marnotratný. ©ikovným pou¾itím metody Rozdìl a panuj
+mù¾eme èasovou slo¾itost podstatnì sní¾it. Postup pøedvedeme pro dosa¾itelnost: na vstupu
+tedy dostaneme matici sousednosti~$A$, výstupem má být její transitivní uzávìr~$A^*$
+(matice dosa¾itelnosti). V¹echny souèiny matic v~tomto oddílu budou typu $(\lor,\land)$.
+
+Vrcholy grafu rozdìlíme na dvì mno¾iny $X$ a~$Y$ pøibli¾nì stejné velikosti,
+bez újmy na obecnosti tak, aby matice~$A$ mìla následující blokový tvar:
+$$A = \pmatrix{ P & Q \cr R & S \cr }.$$
+Zde podmatice~$P$ popisuje hrany z~$X$ do~$X$, podmatice~$Q$ hrany z~$X$ do~$Y$, atd.
+
+Pokud matici~$A^*$ zapí¹eme rovnì¾ v~blokovém tvaru:
+$$A^* = \pmatrix{ I & J \cr K & L \cr },$$
+bude platit:
+$$\eqalign{
+I &= (P \lor QR^*S)^*, \cr
+J &= IQS^*, \cr
+K &= S^*RI, \cr
+L &= S^* \lor S^*RIQS^*.
+}$$
+Jednotlivé rovnosti mù¾eme èíst takto:
+\def\nIJKL{\count0=`H\advance\count0 by\itemcount{\bf\char\count0:}}
+\numlist\nIJKL
+\:Sled z~$X$ do~$X$ vznikne opakováním èástí, z~nich¾ ka¾dá je buïto
+hrana uvnitø~$X$ nebo pøechod po hranì z~$X$ do~$Y$ následovaný sledem
+uvnitø~$Y$ a pøechodem zpìt do~$X$.
+\:Sled z~$X$ do~$Y$ mù¾eme rozdìlit v~místì, kdy naposledy pøechází
+po~hranì z~$X$ do~$Y$. První èást pøitom bude sled z~$X$ do~$X$,
+druhá sled uvnitø~$Y$.
+\:Se sledem z~$Y$ do~$X$ nalo¾íme obdobnì.
+\:Sled z~$Y$ do~$Y$ vede buïto celý uvnitø~$Y$, nebo ho mù¾eme rozdìlit
+na èást pøed prvním pøechodem z~$Y$ do~$X$, tento pøechod, sled z~$X$ do~$Y$,
+pøechod zpìt a sled uvnitø~$Y$.
+\endlist
+
+K~výpoètu matice~$A^*$ nám tedy staèí spoèítat 3~tranzitivní uzávìry
+matic polovièní velikosti (k~èemu¾ pou¾ijeme rekurzi), dále pak $\O(1)$
+$(\lor,\land)$-souèinù a $\O(1)$ souètù matic.
+
+Èasovou slo¾itost $t(n)$ mù¾eme popsat následující rekurencí:
+$$t(n) = 3t(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)$.
+
+Ukázali jsme tedy, ¾e výpoèet transitivního uzávìru je nejvý¹e stejnì
+nároèný jako $(\lor,\land)$-násobení matic -- mù¾eme ho tedy provést
+v~èase $\O(n^\omega)$. Dokonce mù¾eme snadno nalézt i opaèný pøevod,
+tak¾e oba problémy jsou asymptoticky stejnì tì¾ké.
+
+Podobnì nalézt matici vzdáleností je stejnì tì¾ké jako $(\min,+)$-souèin,
+tak¾e na to staèí èas $\O(n^3/\log n)$.
+
 \h{Seidelùv algoritmus}
 
-Pro neorientované neohodnocené grafy mù¾eme matici vzdáleností spoèítat v~èase $\O(n^\omega\log n)$
-Seidelovým algoritmem (FIXME: odkaz). Funguje následovnì:
+Pro neorientované neohodnocené grafy mù¾eme dosáhnout je¹tì lep¹ích
+výsledkù. Matici vzdáleností lze spoèítat v~èase $\O(n^\omega\log n)$
+Seidelovým algoritmem (FIXME: odkaz). Ten funguje následovnì:
 
 \s{Definice:} {\I Druhá mocnina grafu~$G$} je graf~$G^2$ na té¾e mno¾inì vrcholù,
 v~nìm¾ jsou vrcholy~$i$ a~$j$ spojeny hranou právì tehdy, existuje-li v~$G$ sled
@@ -277,7 +332,5 @@ v~konstantn
 trvá $\O(n^\omega)$ a jeliko¾ prùmìr grafu poka¾dé klesne alespoò dvakrát,
 je úrovní $\O(\log n)$ a celý algoritmus dobìhne ve~slíbeném èase $\O(n^\omega\log n)$.
 
-\h{Rozdìl a panuj}
-
 \references
 \bye
-- 
2.39.2