From d57b76183484ea9a4f01f17decda0002968ba697 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Sat, 9 Dec 2006 00:55:30 +0100
Subject: [PATCH] Split chapter 8.

---
 10-decomp/10-decomp.tex                       | 113 +++++++++++++++++
 {8-qheapuf => 10-decomp}/Makefile             |   2 +-
 .../8-qheapuf.tex => 8-qheap/8-qheap.tex      | 114 +-----------------
 8-qheap/Makefile                              |   3 +
 {8-qheapuf => 8-qheap}/trie.eps               |   0
 {8-qheapuf => 8-qheap}/trie.vrr               |   0
 all/Makefile                                  |   2 +-
 7 files changed, 119 insertions(+), 115 deletions(-)
 create mode 100644 10-decomp/10-decomp.tex
 rename {8-qheapuf => 10-decomp}/Makefile (64%)
 rename 8-qheapuf/8-qheapuf.tex => 8-qheap/8-qheap.tex (53%)
 create mode 100644 8-qheap/Makefile
 rename {8-qheapuf => 8-qheap}/trie.eps (100%)
 rename {8-qheapuf => 8-qheap}/trie.vrr (100%)

diff --git a/10-decomp/10-decomp.tex b/10-decomp/10-decomp.tex
new file mode 100644
index 0000000..2e5348e
--- /dev/null
+++ b/10-decomp/10-decomp.tex
@@ -0,0 +1,113 @@
+\input ../sgr.tex
+
+\prednaska{10}{Dekompozice stromù}{zapsal Ale¹ ©nupárek}
+
+\h{Union-Find problem}
+Na Uion-Find problem (UF) mù¾eme nahlí¾et ze více stran (udr¾ování ekvivalencí, 
+inkrementální souvislost grafu). K èemu je to dobré? 
+Napøíklad v Kruskalovì algoritmu pro hledání minimálních koster v grafu.
+\h{Udr¾ování tøíd ekvivalence }
+Mìjme nìjakou mno¾inu M, která se dá rozlo¾it na k ekvivalentních podmon¾in (tøídy ekvivalence). Na mno¾iòe M chceme provádìt 
+dvì operace: jsou p,q z M ekvivalentní (ve stejné tøídì ekvivalence)? (find(p,q)) Dále chceme umìt spojit dvì tøídy ekvivalence do jedné (union(p,q)).
+\h{Inkrementální idr¾ování komponent souvislosti grafu}
+Jedná se o pøipad podobný udr¾ování tøíd ekvivalence. Tentokrát mnou¾inou M bude mno¾ina vrcholù V grafu G (V,E). 
+Za »øídy ekvivalence budou jednotlivé komponenty souvislosti grafu G. Operace find nám øekne o dvou vrcholech nachází-li
+se ve stejné komponen»e, èi nikoliv. Operace union nám spojí dvì komponenty do jedné pøidáním hrany. Pokud pøipustíme mazání hran, 
+øe©ení problému je výraznì te¾¹í.
+
+\h{Bì¾ná implementace }
+Ka¾dé tøídì ekvivalence pøiøadíme unikátní barvu, kterou obarvíme její prvky. Pro operaci find staèí porovnat barvy prvkù. 
+Pro operaci union dvou komponent je nutné pøebarvit obì na stejnou barvu. Budeme pøebarvovat 
+v¾dy tu men¹í pak celková operace union bude trvat $\O(n\log(n) + m)$. (Ka¾dé pøebarvení minimálnì zdvojnásobí velikost nové komponenty.)
+\h {Chytøej¹í implementace }
+Budeme-li prvky za stejné tøídy reprezentovat ve jednom stromì (synové mají ukazatel svého otce), operaci find
+provedeme prùchodem ze zadaných prvkù do koøene. Prvky jsou ve stejné komponentì souvislosti, pokud mají stejného otce.
+Operace union bude spojení dvou stromù do jednoho (otec jednoho stromu se zavìsí pod listy druhého). 
+Takto definovaný union nemusí garantovat logaritmickou slo¾itost pro find, 
+v extrémním pøipadì mù¾e strom mít lineární hloubku vzhledem k poètu vrcholù.
+
+Degeneraci stromu lze zabránit pøidánim podmínky urèující, jaký strom bude dole.
+První mmo¾nost (union by size) je povìsit dolu vìtsí strom.
+Druhá mo¾nost (union by rank) je ka¾dému vrcholu nastavit na zaèátku nìjaký rank (tøeba 1). Pokud je $r1<r2$ pak strom s r1 povìsíme dolu.
+Pokud $r1=r2$ pak ve slouèeném stromù zvý¹íme v koøeni rank o 1. Informace o ranku nám zabere ménì pamìti ne¾ o velikosti stromu.
+
+Dal¹i mo¾nost pro zkrácení vý¹ky stromu je path compression. Pøi operaci find si pamatujeme pro¹lé vrcholy a pøesmìrujeme 
+jejich ukazatele na otce na koøen.
+
+\s{Vìta: } UF s Union by size nebo Union by rank s path compression mají amortizovanì 
+slo¾itost $\O(n\alpha(n))$, kde $\alpha(n)$ je inverzní funkce k Ackermanovì funkci. ($\alpha(poèet atomù ve vesmíru)=5$)
+
+\h {Microtree/Macrotree decomposition}
+
+\s{Otázka: } Je mo¾né provádìt UF v lep¹ím èase kdy¾ bude pøedem znám výsledný strom?
+
+Cíl: UF lze za pomoci preprocesingu v èase $\O(n)$  zvládnout amortizovanì v èase $\O(1)$ na U,F.
+
+\h{Clusterizace}
+\s {Definice: } Nech» G je je graf kde $\forall v \in V(G): deg(v)<=3$ a $c \in N$ pak c-clusterizací grafu G je rozklad
+G na podgrafy na podgrafy G1,G2 ... Gk s následujícimi vlastnostmi:
+\itemize\ibull
+\: $\forall v  \in V \exists !\ i: v \in C_i$
+\: $\forall i\  C_i\leq C$
+\: $\forall i$ vnìj¹i stupeò $C\leq3$, pokud $C_i=3$ pak $\|C_i\|=1$
+\: ¾ádné dva sousední clustery nelze spojit
+\endlist
+
+Co udìlat se stromem, ve kterém existuje vrchol se stupnìm vìt¹im ne¾ 3? Pou¾ijeme French trick.
+V¹echny vrcholy s vy¹¹im stupnìm jak 3, rozdìlíme na více vrcholù se stupnìm 3 spojených cestou. 
+Tato ùprava nám asymptoticky nezmìní èasovou slo¾itost UF o proti pùvodnímu stromu.
+
+
+\s{Lemma: } Pro ka¾dou C-clusterizaci n-vrcholového stromu je  $\O(n/C)$ clusterù.
+
+\s{Vìta: } Pro ka¾dé C lze C-clusterizaci (splòujíci pøedchozí lemma) najít v èase $\O(n)$.
+
+\s{Dùkaz: } za pomoci DFS ...
+\h{Jednodu¹¹í clusterizace}
+Pøedpokládejme, ¾e máme zakoøeòené stromy
+\s{Definice: } Koøeny makrostromù jsou nejvy¹¹i vrcholy, pod kterými je maximálnì $\log(n)$ listù.
+Celá clusterizace se nám rozpadne na následujíci pøipady: 
+\itemize\ibull
+\:N-strom: (má stupeò 1)
+\:M-strom: (má stupeò 2)
+\:cestu: ka¾dá cesta se popí¹e bitovým polem, jednotlivé úseky se poí¹í jednotlivými slovy
+\endlist
+poèet listù v makrostromu je maximálnì $n/\log(n)$ z toho vyplývá, ¾e vý¹ka makrostromu $\O(n/log(n))$
+
+\s{Co si potøebujeme pamatovat}
+\itemize\ibull
+\: $\log(n)$ na clusterizaci
+\: makrostrom  G s $C_i$ zkontrahovanými pro deg 1,3 do vrcholu a deg 2 do hrany, jeho velikost je $\O(n/\log(n))$
+\:mikrostromy, bitovì popsány
+\endlist
+
+\h{Makrostromy}
+V makrostromu jsou takové hrany, které vedly v pùvodním stromu mezi clustery, vrcholy budou hranièní
+vrcholy pøislu¹ných clusterù, cluster stupnì 1 je v novém stromì list, cluster stupnì 2 nahradíme 
+hranou mezi hranièními vrcholy a cluster stupòe 3 má jeden vnìj¹í vrchol, který je také v novém stromì.
+
+\s{find(x,y)}
+\algo
+nech» $i,j: x \in C_i, y \in C_j$
+\:pokud $i=j$, ptáme se v $C_i$ (mikro-find(i,j))
+\:pokud $i\not = j$, najdeme hranièní vrcholy pøíslu¹ných clusterù, tj. $h_i \in C_i, h_j \in C_j$ a provedeme makro-find($h_i$,$h_j$)
+	find($i$,$j$):=makro-find($h_i$,$h_j$) and mikro-find($i$,$h_i$) and mikro-find($j$,$h_j$);
+\endalgo
+
+\s{delete(x,y)}
+\algo
+\: pokud $x,y$ je makro-hrana, sma¾eme ji
+\: pokud $x,y \in C_i$  pak mikro-delete v $C_i$, pokud je $deg(C_i)=2$ a find($h_1$,$h_2$)==FALSE ($h_1, h_2$hranièní vrcholy), 
+pak makro-delete hrany odpovýdajíci $C_i$. ($C_i$ je neprùchodná)
+\endalgo
+\h{Mikrostromy}
+\itemize\ibull
+\: strom zakoøením a oèísluji mu hrany $0..h <  \log(n)$
+\: pamatujeme si: \itemize\ibull  
+  \:$\forall v \in C_i$ mno¾inu hran $P_v$ na cestì do koøene v (bitový vektor)
+  \:mon¾inu smazaných hran, operace delete pøidá hranu do mno¾iny
+  \:hranièní vrcholy
+  \endlist
+\: $P_x \oplus  P_y$ je cesta z x do y
+\endlist
+\bye
diff --git a/8-qheapuf/Makefile b/10-decomp/Makefile
similarity index 64%
rename from 8-qheapuf/Makefile
rename to 10-decomp/Makefile
index 6dd91ee..73a8910 100644
--- a/8-qheapuf/Makefile
+++ b/10-decomp/Makefile
@@ -1,3 +1,3 @@
-P=8-qheapuf
+P=10-decomp
 
 include ../Makerules
diff --git a/8-qheapuf/8-qheapuf.tex b/8-qheap/8-qheap.tex
similarity index 53%
rename from 8-qheapuf/8-qheapuf.tex
rename to 8-qheap/8-qheap.tex
index e44d00e..2cb2601 100644
--- a/8-qheapuf/8-qheapuf.tex
+++ b/8-qheap/8-qheap.tex
@@ -12,8 +12,7 @@
 
 \input ../sgr.tex
 
-\prednaska{8}{Q-Heaps \& Union-Find problem}{zapsali Cyril Strejc a Ale¹
-©nupárek}
+\prednaska{8}{Q-Heaps}{zapsal Cyril Strejc}
 
 Na minulém semináøi jsme si mimo jiné ukázali výpoèetní model RAM a nahlédli
 jsme, ¾e pomocí RAMu mù¾eme celkem snadno (v konstatním èase) simulovat 
@@ -177,115 +176,4 @@ $B[\varphi(i)] = c_i$
 \: update $B$ (dle výsledku pøedchozího kroku), update $R$ (se¹oupnutí)
 \endalgo
 
-
-
-\h{Union-Find problem}
-Na Uion-Find problem (UF) mù¾eme nahlí¾et ze více stran (udr¾ování ekvivalencí, 
-inkrementální souvislost grafu). K èemu je to dobré? 
-Napøíklad v Kruskalovì algoritmu pro hledání minimálních koster v grafu.
-\h{Udr¾ování tøíd ekvivalence }
-Mìjme nìjakou mno¾inu M, která se dá rozlo¾it na k ekvivalentních podmon¾in (tøídy ekvivalence). Na mno¾iòe M chceme provádìt 
-dvì operace: jsou p,q z M ekvivalentní (ve stejné tøídì ekvivalence)? (find(p,q)) Dále chceme umìt spojit dvì tøídy ekvivalence do jedné (union(p,q)).
-\h{Inkrementální idr¾ování komponent souvislosti grafu}
-Jedná se o pøipad podobný udr¾ování tøíd ekvivalence. Tentokrát mnou¾inou M bude mno¾ina vrcholù V grafu G (V,E). 
-Za »øídy ekvivalence budou jednotlivé komponenty souvislosti grafu G. Operace find nám øekne o dvou vrcholech nachází-li
-se ve stejné komponen»e, èi nikoliv. Operace union nám spojí dvì komponenty do jedné pøidáním hrany. Pokud pøipustíme mazání hran, 
-øe©ení problému je výraznì te¾¹í.
-
-\h{Bì¾ná implementace }
-Ka¾dé tøídì ekvivalence pøiøadíme unikátní barvu, kterou obarvíme její prvky. Pro operaci find staèí porovnat barvy prvkù. 
-Pro operaci union dvou komponent je nutné pøebarvit obì na stejnou barvu. Budeme pøebarvovat 
-v¾dy tu men¹í pak celková operace union bude trvat $\O(n\log(n) + m)$. (Ka¾dé pøebarvení minimálnì zdvojnásobí velikost nové komponenty.)
-\h {Chytøej¹í implementace }
-Budeme-li prvky za stejné tøídy reprezentovat ve jednom stromì (synové mají ukazatel svého otce), operaci find
-provedeme prùchodem ze zadaných prvkù do koøene. Prvky jsou ve stejné komponentì souvislosti, pokud mají stejného otce.
-Operace union bude spojení dvou stromù do jednoho (otec jednoho stromu se zavìsí pod listy druhého). 
-Takto definovaný union nemusí garantovat logaritmickou slo¾itost pro find, 
-v extrémním pøipadì mù¾e strom mít lineární hloubku vzhledem k poètu vrcholù.
-
-Degeneraci stromu lze zabránit pøidánim podmínky urèující, jaký strom bude dole.
-První mmo¾nost (union by size) je povìsit dolu vìtsí strom.
-Druhá mo¾nost (union by rank) je ka¾dému vrcholu nastavit na zaèátku nìjaký rank (tøeba 1). Pokud je $r1<r2$ pak strom s r1 povìsíme dolu.
-Pokud $r1=r2$ pak ve slouèeném stromù zvý¹íme v koøeni rank o 1. Informace o ranku nám zabere ménì pamìti ne¾ o velikosti stromu.
-
-Dal¹i mo¾nost pro zkrácení vý¹ky stromu je path compression. Pøi operaci find si pamatujeme pro¹lé vrcholy a pøesmìrujeme 
-jejich ukazatele na otce na koøen.
-
-\s{Vìta: } UF s Union by size nebo Union by rank s path compression mají amortizovanì 
-slo¾itost $\O(n\alpha(n))$, kde $\alpha(n)$ je inverzní funkce k Ackermanovì funkci. ($\alpha(poèet atomù ve vesmíru)=5$)
-
-\h {Microtree/Macrotree decomposition}
-
-\s{Otázka: } Je mo¾né provádìt UF v lep¹ím èase kdy¾ bude pøedem znám výsledný strom?
-
-Cíl: UF lze za pomoci preprocesingu v èase $\O(n)$  zvládnout amortizovanì v èase $\O(1)$ na U,F.
-
-\h{Clusterizace}
-\s {Definice: } Nech» G je je graf kde $\forall v \in V(G): deg(v)<=3$ a $c \in N$ pak c-clusterizací grafu G je rozklad
-G na podgrafy na podgrafy G1,G2 ... Gk s následujícimi vlastnostmi:
-\itemize\ibull
-\: $\forall v  \in V \exists !\ i: v \in C_i$
-\: $\forall i\  C_i\leq C$
-\: $\forall i$ vnìj¹i stupeò $C\leq3$, pokud $C_i=3$ pak $\|C_i\|=1$
-\: ¾ádné dva sousední clustery nelze spojit
-\endlist
-
-Co udìlat se stromem, ve kterém existuje vrchol se stupnìm vìt¹im ne¾ 3? Pou¾ijeme French trick.
-V¹echny vrcholy s vy¹¹im stupnìm jak 3, rozdìlíme na více vrcholù se stupnìm 3 spojených cestou. 
-Tato ùprava nám asymptoticky nezmìní èasovou slo¾itost UF o proti pùvodnímu stromu.
-
-
-\s{Lemma: } Pro ka¾dou C-clusterizaci n-vrcholového stromu je  $\O(n/C)$ clusterù.
-
-\s{Vìta: } Pro ka¾dé C lze C-clusterizaci (splòujíci pøedchozí lemma) najít v èase $\O(n)$.
-
-\s{Dùkaz: } za pomoci DFS ...
-\h{Jednodu¹¹í clusterizace}
-Pøedpokládejme, ¾e máme zakoøeòené stromy
-\s{Definice: } Koøeny makrostromù jsou nejvy¹¹i vrcholy, pod kterými je maximálnì $\log(n)$ listù.
-Celá clusterizace se nám rozpadne na následujíci pøipady: 
-\itemize\ibull
-\:N-strom: (má stupeò 1)
-\:M-strom: (má stupeò 2)
-\:cestu: ka¾dá cesta se popí¹e bitovým polem, jednotlivé úseky se poí¹í jednotlivými slovy
-\endlist
-poèet listù v makrostromu je maximálnì $n/\log(n)$ z toho vyplývá, ¾e vý¹ka makrostromu $\O(n/log(n))$
-
-\s{Co si potøebujeme pamatovat}
-\itemize\ibull
-\: $\log(n)$ na clusterizaci
-\: makrostrom  G s $C_i$ zkontrahovanými pro deg 1,3 do vrcholu a deg 2 do hrany, jeho velikost je $\O(n/\log(n))$
-\:mikrostromy, bitovì popsány
-\endlist
-
-\h{Makrostromy}
-V makrostromu jsou takové hrany, které vedly v pùvodním stromu mezi clustery, vrcholy budou hranièní
-vrcholy pøislu¹ných clusterù, cluster stupnì 1 je v novém stromì list, cluster stupnì 2 nahradíme 
-hranou mezi hranièními vrcholy a cluster stupòe 3 má jeden vnìj¹í vrchol, který je také v novém stromì.
-
-\s{find(x,y)}
-\algo
-nech» $i,j: x \in C_i, y \in C_j$
-\:pokud $i=j$, ptáme se v $C_i$ (mikro-find(i,j))
-\:pokud $i\not = j$, najdeme hranièní vrcholy pøíslu¹ných clusterù, tj. $h_i \in C_i, h_j \in C_j$ a provedeme makro-find($h_i$,$h_j$)
-	find($i$,$j$):=makro-find($h_i$,$h_j$) and mikro-find($i$,$h_i$) and mikro-find($j$,$h_j$);
-\endalgo
-
-\s{delete(x,y)}
-\algo
-\: pokud $x,y$ je makro-hrana, sma¾eme ji
-\: pokud $x,y \in C_i$  pak mikro-delete v $C_i$, pokud je $deg(C_i)=2$ a find($h_1$,$h_2$)==FALSE ($h_1, h_2$hranièní vrcholy), 
-pak makro-delete hrany odpovýdajíci $C_i$. ($C_i$ je neprùchodná)
-\endalgo
-\h{Mikrostromy}
-\itemize\ibull
-\: strom zakoøením a oèísluji mu hrany $0..h <  \log(n)$
-\: pamatujeme si: \itemize\ibull  
-  \:$\forall v \in C_i$ mno¾inu hran $P_v$ na cestì do koøene v (bitový vektor)
-  \:mon¾inu smazaných hran, operace delete pøidá hranu do mno¾iny
-  \:hranièní vrcholy
-  \endlist
-\: $P_x \oplus  P_y$ je cesta z x do y
-\endlist
 \bye
-
diff --git a/8-qheap/Makefile b/8-qheap/Makefile
new file mode 100644
index 0000000..9ccefd7
--- /dev/null
+++ b/8-qheap/Makefile
@@ -0,0 +1,3 @@
+P=8-qheap
+
+include ../Makerules
diff --git a/8-qheapuf/trie.eps b/8-qheap/trie.eps
similarity index 100%
rename from 8-qheapuf/trie.eps
rename to 8-qheap/trie.eps
diff --git a/8-qheapuf/trie.vrr b/8-qheap/trie.vrr
similarity index 100%
rename from 8-qheapuf/trie.vrr
rename to 8-qheap/trie.vrr
diff --git a/all/Makefile b/all/Makefile
index a1672da..a15e9ec 100644
--- a/all/Makefile
+++ b/all/Makefile
@@ -1,5 +1,5 @@
 P=ga
-X=$(shell for a in 1 2 3 4 5 6 7 8 9 ; do echo ../$$a-*/$$a-*.tex ; done)
+X=$(shell for a in 1 2 3 4 5 6 7 8 9 10 ; do echo ../$$a-*/$$a-*.tex ; done)
 
 include ../Makerules
 
-- 
2.39.2