From 053fd5d167550549bea80a8d50418d7cf424e205 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 10 Jan 2007 22:24:51 +0100 Subject: [PATCH] Added lots of references, expect more soon. --- 10-decomp/10-decomp.tex | 10 +- 3-bipcon/3-bipcon.tex | 10 +- 4-ght/4-ght.tex | 5 +- 5-mst/5-mst.tex | 5 +- 6-borjar/6-borjar.tex | 21 ++- 7-ram/7-ram.tex | 11 +- 8-qheap/8-qheap.tex | 5 +- 9-suffix/9-suffix.tex | 5 +- Makerules | 7 +- all/Makefile | 6 +- all/ga.tex | 8 ++ all/preprocess | 9 +- ga.bib | 299 ++++++++++++++++++++++++++++++++++++++++ sgr.tex | 13 +- 14 files changed, 367 insertions(+), 47 deletions(-) create mode 100644 all/ga.tex create mode 100644 ga.bib diff --git a/10-decomp/10-decomp.tex b/10-decomp/10-decomp.tex index 1be6170..480112f 100644 --- a/10-decomp/10-decomp.tex +++ b/10-decomp/10-decomp.tex @@ -49,7 +49,7 @@ m bude omezena $\O(\log n)$.% \foot{Mimochodem, Path compression samotná by také na~slo¾itost $\O(\log n)$ amortizovanì staèila.} -\s{Vìta:} (Tarjan et al.) Kombinace Union by rank a Path compression vede k~amortizované +\s{Vìta:} (Tarjan, van Leeuwen \cite{tarjan84setunion}) Kombinace Union by rank a Path compression vede k~amortizované slo¾itosti obou operací $\O(\alpha(n))$, kde $\alpha$ je inverzní Ackermannova funkce.% \foot{Existuje varianta tohoto algoritmu, která dosahuje stejné slo¾itosti i v~nejhor¹ím pøípadì; té¾ je známo, ¾e asymptoticky lep¹í slo¾itosti nelze dosáhnout.} @@ -59,7 +59,8 @@ p Dále nás bude zajímat speciální varianta Union-Find problemu, v~ní¾ dopøedu známe posloupnost unionù, èili strom, který spojováním komponent vznikne. Popí¹eme algoritmus, který po~poèáteèním pøedzpracování v~èase $\O(n)$ zvládne \ i \ v~amortizovanì -konstantním èase. +konstantním èase. Tento algoritmus je kombinací dekompozic popsaných v~\cite{alstrup97optimal} +a \cite{alstrup98marked}. \s{Definice:} {\I (Microtree/Macrotree dekompozice)} Pro zakoøenìný strom $T$ o~$n$ vrcholech definujeme: @@ -165,7 +166,7 @@ rozlo \h{Fredericksonova clusterizace} Mikro/makro-stromová dekompozice není jediný zpùsob, jak stromy rozkládat. Nìkdy -se hodí napøíklad následující my¹lenka: +se hodí napøíklad následující my¹lenka: \cite{frederickson91ambivalent} \s{Definice:} (Fredericksonova clusterizace) Nech» $G$ je graf s~vrcholy stupòù nejvý¹e~3 a $c\ge 1$. Pak $c$-clusterizací grafu $G$ nazveme libovolný rozklad @@ -205,7 +206,7 @@ spole \:\dots\ co dál? \endlist -Vìrni vtipùm o~matfyzácích pøevedeme radìji tento problém na~jiný: +\>Vìrni vtipùm o~matfyzácích a èlánku \cite{bender00lca} pøevedeme radìji tento problém na~jiný. \s{Problém:} {\I (Range Minimum Query alias RMQ)} Chceme pøedzpracovat posloupnost èísel $a_1,\ldots a_n$ tak, abychom umìli rychle poèítat $\min_{x\le i\le y} a_i$.% @@ -278,4 +279,5 @@ V \s{Vìta:} Problémy LCA i RMQ je mo¾né øe¹it v~konstantním èase na~dotaz po~pøedzpracování v~lineárním èase. +\references \bye diff --git a/3-bipcon/3-bipcon.tex b/3-bipcon/3-bipcon.tex index dac9270..dcca2dd 100644 --- a/3-bipcon/3-bipcon.tex +++ b/3-bipcon/3-bipcon.tex @@ -1,8 +1,3 @@ -%%%%%%%%%%%% -% Zápisek tøetího semináre z grafových agoritmù - ze dne 20.3.2006 -% Zapsal Jiøí Peinlich - peinlich@seznam.cz a Michal Kùrka - michal.kurka@gmail.com -%%%%%%%%%%% - \input ../sgr.tex \prednaska{3}{Bipartitní párování a globální k-souvislost}{zapsali Jiøí Peinlich, Michal Kùrka} @@ -11,7 +6,7 @@ a minimálního øezu. V~této si pøedvedeme dva algoritmy pro podobné problémy, které se obejdou bez tokù. -\h{Maximální párování v regulárním bipartitním grafu} +\h{Maximální párování v regulárním bipartitním grafu \cite{alon:matching}} Nejprve si nadefinujme operaci {\I Degree Split,} která dostane jako vstup libovolný $2k$-regulární graf $G=(V,E)$ a rozdìlí ho na~podgrafy $G_1=(V,E_1)$ a $G_2=(V,E_2)$, které budou @@ -75,7 +70,7 @@ bude $\O(\kappa (G) n^{3/2} m)$, kde $\kappa(G)$ je stupe Pro minimální øezy v~neorientovaných grafech ov¹em existuje následující rychlej¹í algoritmus: -\h{Globálnì minimální øez (Nagamochi, Ibaraki)} +\h{Globálnì minimální øez (Nagamochi, Ibaraki \cite{nagaiba:conn})} Buï $G$ neorientovaný graf s~ohodnocením na~hranách. Oznaèíme si: @@ -133,4 +128,5 @@ odstranit. Operace \ pot malý poèet pøihrádek, pøípadnì zalo¾ení nové pøihrádky na správném místì. \ i \ pak budou mít slo¾itost $\O(1)$ a celý algoritmus $\O(mn)$. +\references \bye diff --git a/4-ght/4-ght.tex b/4-ght/4-ght.tex index 44127b0..5daf909 100644 --- a/4-ght/4-ght.tex +++ b/4-ght/4-ght.tex @@ -21,7 +21,7 @@ Zat grafu v~èase $\tau=\O(n^{2/3}m)$ pro~jednotkové kapacity, $\O(n^2m)$ pro obecné. Nalézt minimální \st-øez pro ka¾dou dvojici vrcholù bychom tedy dokázali v~èase $\O(n^2\tau)$. Tento výsledek budeme -chtít zlep¹it. +chtít zlep¹it. \cite{gomoryhu} \s{Znaèení:} Máme\li{} graf $(V,E)$ a $U\subseteq V$, $\d(U)$ znaèí hrany vedoucí mezi $U$ a $\overline U$, formálnì tedy $\d(U)=E \cap ((U \times \overline U) \cup (\overline U \times U))$. @@ -247,4 +247,7 @@ nalezneme v~ zpracujeme rekurzivnì. Celou výstavbu tedy zvládneme v~èase $\O(n\tau)$, èili $\O(n^{5/3}m)$ pro neohodnocené grafy. +\todo{Odkazy na rychlej¹í algoritmy} + +\references \bye diff --git a/5-mst/5-mst.tex b/5-mst/5-mst.tex index 6ef95c8..387b662 100644 --- a/5-mst/5-mst.tex +++ b/5-mst/5-mst.tex @@ -37,7 +37,7 @@ Bu Ostatním hranám nele¾ícím v~kostøe budeme øíkat {\I tì¾ké.} \endlist -\s{Vìta:} Kostra~$T$ je minimální $\Leftrightarrow$ neexistuje hrana lehká vzhledem k~$T$. +\s{Vìta:} (Tarjan \cite{tarjan:dsna}) Kostra~$T$ je minimální $\Leftrightarrow$ neexistuje hrana lehká vzhledem k~$T$. Tato vìta nám dává pìknou alternativní definici MST, která místo sèítání vah váhy pouze porovnává, èili jí místo èísel staèí (kvazi)uspoøádání na~hranách. Ne¾ se dostaneme @@ -120,7 +120,7 @@ V meta-algoritmu. Rozeberme si tedy rovnou ten. Formulujeme ho pro pøípad, kdy jsou v¹echny váhy hran navzájem rùzné. -\s{Meta-algoritmus:} +\s{Meta-algoritmus:} (Tarjan \cite{tarjan:dsna}) \algo \:Na poèátku jsou v¹echny hrany bezbarvé. @@ -242,4 +242,5 @@ P \s{Cvièení:} Naleznìte algoritmus pro výpoèet MST v~grafech ohodnocených vahami $\{1,\ldots k\}$ se slo¾itostí $\O(mk)$. +\references \bye diff --git a/6-borjar/6-borjar.tex b/6-borjar/6-borjar.tex index ca7b4ee..3d74260 100644 --- a/6-borjar/6-borjar.tex +++ b/6-borjar/6-borjar.tex @@ -15,7 +15,7 @@ z~$G$ kontrakc expandováním kontrahovaných vrcholù, je ${\rm MST}(G)$. To nás vede k následujícímu algoritmu: -\s{Algoritmus: MST v rovinných grafech} +\s{Algoritmus: MST v rovinných grafech} \cite{mm:mst} \algo \:Ke ka¾dému vrcholu najdeme nejlevnìj¹í incidentní hranu -- dostaneme mno¾inu hran $F \subseteq E$. \:Graf zkontrahujeme podle $F$ následovnì: @@ -76,8 +76,6 @@ Jeliko mù¾eme pro odhad jejich hustoty pou¾ít pøedchozí vìtu a dostaneme lineární èasovou slo¾itost dokonce pro ka¾dou netriviální minorovì uzavøenou tøídu grafù. -%%%Tomas Gavenciak - \h{Jarníkùv algoritmus s Fibonacciho haldou} Pùvodní Jarníkùv algoritmus s~haldou má díky ní slo¾itost $\O(m\log n)$, to zlep¹íme pou¾itím @@ -86,7 +84,7 @@ s~dosavadn Tyto trojice bude halda udr¾ovat uspoøádané podle vah. \newcount\algcnt -\s{Algoritmus: Jarníkùv algoritmus~\#2 (Fredman, Tarjan)} +\s{Algoritmus: Jarníkùv algoritmus~\#2 (Fredman, Tarjan \cite{ft:fibonacci})} \algo \:Zaèneme libovolným vrcholem $v_0$: $T=\{v_0\}$. \:Do~haldy $H$ umístíme v¹echny sousedy $v_0$ spolu s pøíslu¹nými hranami. @@ -135,7 +133,7 @@ velikost haldy a takto budeme b jednotlivé podkostøièky zastavené v rùstu pøeteèením haldy, podle kterých graf následnì zkontrahujeme a budeme pokraèovat s mnohem men¹ím grafem. -\s{Algoritmus: Jarníkùv algoritmus~\#4 (Fredman, Tarjan)} +\s{Algoritmus: Jarníkùv algoritmus~\#4 (Fredman, Tarjan \cite{ft:fibonacci})} \algo \:Opakuji, dokud mám netriviální $G$ (s alespoò jednou hranou): \::$t=\vert V_G\vert$. @@ -182,23 +180,24 @@ omezen \itemize\ibull \:$\O(m\alpha(m,n))$, kde $\alpha(m,n)$ je obdoba inverzní Ackermannovy funkce definovaná podobnì, jako je $\beta(m,n)$ obdobou $\log^*$. - [Chazelle 2000] + \cite{chazelle:ackermann}, \cite{pettie:ackermann} \:$\O({\cal T}(m,n))$, kde ${\cal T}(m,n)$ je hloubka optimálního rozhodovacího stromu pro nalezení minimální kostry v~grafech s~patøièným poètem hran a vrcholù - [Pettie, Ramachandran 2002]. + \cite{pettie:optimal}. Jeliko¾ ka¾dý deterministický algoritmus zalo¾ený na~porovnávání vah lze popsat rozhodovacím stromem, je tento algoritmus zaruèenì optimální. Jen bohu¾el nevíme, optimální stromy vypadají, tak¾e je stále otevøeno, zda lze MST nalézt v~lineárním èase. Nicménì jeliko¾ tento algoritmus pracuje i na~Pointer Machine, víme, ¾e pokud je lineární slo¾itosti mo¾né dosáhnout, není k~tomu potøeba výpoèetní síla RAMu.\foot{O výpoèetních modelech viz pøí¹tí kapitola.} -\:$\O(m)$ pro grafy s~celoèíselnými vahami (na~RAMu) [Fredman, Willard 1990] -- uká¾eme v~jedné +\:$\O(m)$ pro grafy s~celoèíselnými vahami (na~RAMu) \cite{fw90trans} -- uká¾eme v~jedné z~následujících kapitol. \:$\O(m)$, pokud u¾ máme hrany setøídìné podle vah: jeliko¾ víme, ¾e zále¾í jen na~uspoøádání, mù¾eme váhy pøeèíslovat na~$1\ldots n$ a pou¾ít pøedchozí algoritmus. -\:$\O(m)$ randomizovanì v~prùmìrném pøípadì [Karger, Klein, Tarjan 1995] -\:Na~zji¹tìní, zda je zadaná kostra minimální, staèí $\O(m)$ porovnání [Komlós 1984] a dokonce - lze v~lineárním èase zjistit, která to jsou [King 1995]. Z~toho ostatnì vychází pøedchozí +\:$\O(m)$ randomizovanì v~prùmìrném pøípadì \cite{karger:randomized}. +\:Na~zji¹tìní, zda je zadaná kostra minimální, staèí $\O(m)$ porovnání \cite{komlos:verify} a dokonce + lze v~lineárním èase zjistit, která to jsou \cite{king:verify}. Z~toho ostatnì vychází pøedchozí randomizovaný algoritmus. \endlist +\references \bye diff --git a/7-ram/7-ram.tex b/7-ram/7-ram.tex index 69b3f4b..da0a06d 100644 --- a/7-ram/7-ram.tex +++ b/7-ram/7-ram.tex @@ -36,7 +36,7 @@ pod Obvykle se pou¾ívají následující dva modely, které se li¹í zejména v~tom, zda je mo¾né pamì» indexovat v~konstantním èase èi nikoliv. -\s{Pointer Machine (PM)} pracuje se dvìma typy dat: {\I èísly} v~pevnì omezeném +\s{Pointer Machine (PM)} \cite{benamram95what} pracuje se dvìma typy dat: {\I èísly} v~pevnì omezeném rozsahu a {\I pointery,} které slou¾í k~odkazování na~data ulo¾ená v~pamìti. Pamì» tohoto modelu je slo¾ená z pevného poètu registrù na~èísla a na~pointery a z~neomezeného poètu {\I krabièek.} Ka¾dá krabièka má pevný @@ -48,7 +48,7 @@ Aritmetika v~tomto modelu (a pøímoèaøe, ov¹em pole musíme reprezentovat stromem, tak¾e indexování stojí $\O(\log n)$. -\s{Random Access Machine (RAM)} je rodinka modelù, které mají spoleèné to, ¾e +\s{Random Access Machine (RAM)} \cite{demaine} je rodinka modelù, které mají spoleèné to, ¾e pracují výhradnì s~(pøirozenými) èísly a ukládají je do~pamìti indexované opìt èísly. Instrukce v~programu (podobné assembleru) pracují s~operandy, které jsou buï konstanty nebo buòky pamìti adresované pøímo (èíslem buòky), @@ -100,7 +100,7 @@ jdou prov \h{Van Emde-Boas Trees} -VEBT jsou RAMová struktura, která si pamatuje mno¾inu prvkù $X$ z nìjakého +VEBT \cite{boas77} jsou RAMová struktura, která si pamatuje mno¾inu prvkù $X$ z nìjakého omezeného universa $X \subseteq \{0,\ldots,U-1\}$, a umí s~ní provádìt \uv{stromové operace} (vkládání, mazání, nalezení následníka apod.) v~èase $\O(\log\log U)$. Pomocí takové struktury pak napøíklad doká¾eme: @@ -115,7 +115,7 @@ Dijkstra &$\O(m\log\log U)$ &$\O(m+n\log\log n)$, neorientovan }}$$ \s{Definice:} VEBT($U$) pro universum velikosti $U$ (BÚNO $U=2^{2^k}$) -obsahuje: +obsahuje: (ekvivalentní formulace podle \cite{demaine}) \itemize\ibull @@ -220,6 +220,8 @@ mimo seznam~$L$ a zda je $L[R[i]]=i$. T jestli je $M[i]$ ji¾ inicializovaná, a~jsme také schopni tuto informaci v~tém¾e èase udr¾ovat. \qed + +\todo{References} } \s{\uv{Minové pole}:} Neinicializované buòky není ani dovoleno èíst. @@ -393,4 +395,5 @@ jedni pøedpokládaly prostrkané nuly a ty tu nemáme. Mù¾eme si je ale snadno poøídit a bity, které jsme nulami pøepsali, prostì zpracovat zvlá¹».} +\references \bye diff --git a/8-qheap/8-qheap.tex b/8-qheap/8-qheap.tex index 5242a12..4c0a6db 100644 --- a/8-qheap/8-qheap.tex +++ b/8-qheap/8-qheap.tex @@ -52,7 +52,7 @@ v~konstantn Pøedchozí struktura má zajímavé vlastnosti, ale èasto je její pou¾ití znemo¾nìno omezením na~velikost èísel. Popí¹eme tedy o~nìco slo¾itìj¹í -konstrukci, která doká¾e toté¾, ale s~a¾ $w$-bitovými èísly. +konstrukci \cite{fw90trans}, která doká¾e toté¾, ale s~a¾ $w$-bitovými èísly. Tato struktura má spí¹e teoretický význam (konstrukce je znaènì komplikovaná a skryté konstanty nemalé), ale pøekvapivì mnoho my¹lenek je pou¾itelných i v~praxi. @@ -214,6 +214,5 @@ po \todo{Aplikace na~kostry.} +\references \bye - -% LocalWords: MSB Vlozeni diff --git a/9-suffix/9-suffix.tex b/9-suffix/9-suffix.tex index b3c49b1..30545e0 100644 --- a/9-suffix/9-suffix.tex +++ b/9-suffix/9-suffix.tex @@ -148,7 +148,7 @@ a nakonec podle list kde ${\rm Sort}(\ldots)$ je èas potøebný pro setøídìní $n$ symbolù z~abecedy~$\Sigma$. V~kombinaci s~pøedchozími výsledky nám tedy dává lineární konstrukci ST($\sigma$) pro libovolnou fixní abecedu. -\s{Algoritmus:} (Konstrukce $A$ a $L$ podle Kärkkäinena a Sanderse) +\s{Algoritmus:} (Konstrukce $A$ a $L$ podle Kärkkäinena a Sanderse \cite{karkkainen03simple}) \algo \:Redukujeme abecedu na~$1\ldots n$: ve~vstupním slovu je nejvý¹e $n$ rùzných znakù, @@ -201,7 +201,7 @@ $$T(n) = T(2/3\cdot n) + \O(n),~\hbox{a tedy}~T(n)=\O(n).$$ \h{Ukkonenova inkrementální konstrukce} -\>Ukkonenùv algoritmus konstruuje suffixový strom bez dolarù inkrementálnì: zaène se stromem +\>Ukkonenùv algoritmus \cite{ukkonen95line} konstruuje suffixový strom bez dolarù inkrementálnì: zaène se stromem pro prázdné slovo (ten má jediný vrchol, a to koøen) a postupnì pøidává dal¹í znaky na~konec slova. To zvládne v~èase $\O(1)$ amortizovanì na~pøidání jednoho znaku. Pro slovo~$\sigma$ tedy doká¾e sestrojit ST v~èase $\O(\vert\sigma\vert)$. @@ -324,4 +324,5 @@ Celkov stromu amortizovanì konstantní. \qed +\references \bye diff --git a/Makerules b/Makerules index 337e0dc..4db4413 100644 --- a/Makerules +++ b/Makerules @@ -1,7 +1,10 @@ all: $P.ps -%.dvi: %.tex ../sgr.tex +%.dvi: %.tex ../sgr.tex ../ga.bib csplain $< + bibtex $* + csplain $< + csplain $< # BibTeX requires 3 passes of TeXing! %.pdf: %.tex ../sgr.tex pdfcsplain $< @@ -22,7 +25,7 @@ all: $P.ps pstops '2:0L(212mm,0mm)+1L(212mm,150mm)' <$< | sed 's/^%%BoundingBox: .*/%%BoundingBox: 0 0 595 842/' >$@ mostlyclean: - rm -f *.dvi *.log *~ core *.o *-700.tex *-a5.ps + rm -f *.dvi *.log *~ core *.o *-700.tex *-a5.ps *.aux *.bbl *.blg clean:: mostlyclean rm -f *.ps *.pdf diff --git a/all/Makefile b/all/Makefile index a15e9ec..16e69e0 100644 --- a/all/Makefile +++ b/all/Makefile @@ -3,11 +3,13 @@ X=$(shell for a in 1 2 3 4 5 6 7 8 9 10 ; do echo ../$$a-*/$$a-*.tex ; done) include ../Makerules -ga.tex: $(X) preprocess +ga.dvi: ga.tex body.tex + +body.tex: $(X) preprocess ./preprocess $(X) >$@ clean:: - rm -f ga.tex + rm -f body.tex upload:: ( cd .. && make clean ) diff --git a/all/ga.tex b/all/ga.tex new file mode 100644 index 0000000..4b5e505 --- /dev/null +++ b/all/ga.tex @@ -0,0 +1,8 @@ +\input ../sgr.tex + +\def\chapterend{\bigbreak\bigbreak} + +\input body.tex + +\references +\bye diff --git a/all/preprocess b/all/preprocess index b459f13..b93e562 100755 --- a/all/preprocess +++ b/all/preprocess @@ -3,22 +3,17 @@ use warnings; use strict; -print <) { /^\\input .*sgr\.tex/ && next; + /^\\references/ && next; /^\\bye/ && last; s@\\(figure|epsfbox){([^}]+)}@\\$1\{$d$2}@g; print; } close X; - print "\\bigbreak\\bigbreak\n"; + print "\\chapterend\n"; } -print <