From 83329800368162b7bfd7b921cda7039b0af41e5c Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 7 Mar 2007 19:57:41 +0100 Subject: [PATCH] Finalni strankovy zlom, titulni strana, obsah a tiraz. --- 10-suffix/10-suffix.tex | 4 +- 11-planar/11-planar.tex | 14 +++++- 3-bipcon/3-bipcon.tex | 2 +- 4-ght/4-ght.tex | 7 +-- 5-mst/5-mst.tex | 4 +- 6-borjar/6-borjar.tex | 3 +- 7-ram/7-ram.tex | 8 +++- 8-qheap/8-qheap.tex | 6 +-- Makerules | 2 +- all/ga.tex | 103 +++++++++++++++++++++++++++++++++++++++- sgr.tex | 13 +++-- 11 files changed, 144 insertions(+), 22 deletions(-) diff --git a/10-suffix/10-suffix.tex b/10-suffix/10-suffix.tex index 9ebcbc1..9249c8a 100644 --- a/10-suffix/10-suffix.tex +++ b/10-suffix/10-suffix.tex @@ -176,7 +176,7 @@ $A_i$ zapamatujeme, kde se v~$A_{01}$ vyskytoval. a v¹echna $\sigma_0[i:{}]$ u¾ máme setøídìná, mù¾eme v¹echna $\sigma_2[i:{}]$ setøídit dvìma prùchody pøihrádkového tøídìní. \:Dopoèítáme $L_2$: Stejným trikem jako $A_2$ -- pokud jsou první písmena rùzná, je spoleèný prefix prázdný, jinak -má délku $1+{\rm LCP}(\sigma_0[i+1:{}],\sigma_0[j+1:{}]) = 1+\min_{i+1\le k< j+1} L_0[k]$. Minimum zvládneme pro ka¾dou +má délku $1+{\rm LCP}(\sigma_0[i+1:\nobreak{}],\sigma_0[j+1:{}]) = 1+\min_{i+1\le k< j+1} L_0[k]$. Minimum zvládneme pro ka¾dou dvojici $i,j$ spoèítat v~konstantním èase pomocí datové struktury pro intervalová minima. \:$A_0,A_1,A_2\buildrel merge\over\longrightarrow A$ -- sléváme tøi setøídìné posloupnosti, @@ -310,6 +310,8 @@ bude hodit p a jeho funkce \. \endalgo +\goodbreak + \s{Èasová slo¾itost:} Kanonikalizace pracuje v~amortizovanì konstantním èase, proto¾e ka¾dá její iterace diff --git a/11-planar/11-planar.tex b/11-planar/11-planar.tex index 8967f2c..307940f 100644 --- a/11-planar/11-planar.tex +++ b/11-planar/11-planar.tex @@ -1,6 +1,6 @@ \input ../sgr.tex -\prednaska{11}{Kreslení grafù do~roviny}{} +\prednaska{11}{Kreslení grafù do roviny}{} Rovinné grafy se objevují v~nejrùznìj¹ích praktických aplikacích teorie grafù, a~tak okolo nich vyrostlo znaèné mno¾ství algoritmù. I~kdy¾ existují výjimky, @@ -93,6 +93,11 @@ tak le¾ícími pod~ním pøeklopit podle koøenové artikulace, ani¾ bychom poru¹ili rovinnost. +\finalfix{ +\figure{planar1.eps}{Pøed nakreslením zpìtných hran \dots}{\epsfxsize} +\figure{planar2.eps}{\dots\ po nìm (ètvereèky jsou externì aktivní vrcholy)}{\epsfxsize} +} + V¹imnìme si, ¾e pokud vede z~nìjakého u¾ nakresleného vrcholu je¹tì nenakreslená hrana, lze pokraèovat po~nenakreslených hranách a¾ do~koøene DFS stromu. V¹echny vrcholy, ke~kterým je¹tì bude potøeba nìco pøipojit (takovým budeme øíkat {\I externì aktivní} a hranám @@ -106,10 +111,12 @@ trivi zpìtnou hranou spojí s~jinými bloky. Zpìtné hrany byly a¾ donedávna externì aktivní, tak¾e pøidání jedné zpìtné hrany nahradí cestu po~okraji bloku touto hranou (tím vytvoøí novou stìnu) a také mù¾e -slouèit nìkolik blokù do~jednoho: +slouèit nìkolik blokù do~jednoho, jak je vidìt z~obrázkù. +\separatefix{ \figure{planar1.eps}{Pøed nakreslením zpìtných hran \dots}{\epsfxsize} \figure{planar2.eps}{\dots\ po nìm (ètvereèky jsou externì aktivní vrcholy)}{\epsfxsize} +} Bude se nám hodit, ¾e èas potøebný na~tuto operaci je pøímo úmìrný poètu hran, které ubyly z~vnìj¹í stìny, co¾ je amortizovanì konstanta. @@ -197,6 +204,7 @@ zpracov tj. blok obsahující ¾ivý vrchol. Není-li ¾ivý vrchol èi blok externì aktivní, budeme mu øíkat {\I internì aktivní.} Pakli¾e není vrchol/blok ani ¾ivý, ani externì aktivní, budeme ho nazývat {\I neaktivní.} +\finalfix{\looseness=1} Pøed procházením podstromù tedy nejprve probereme v¹echny zpìtné hrany vedoucí do~$v$ a oznaèíme ¾ivé vrcholy. Pro ka¾dou zpìtnou hranu potøebujeme o¾ivit vrchol, z~nìj¾ @@ -329,6 +337,7 @@ nerovinn \:{\I pøestane být 2-souvislý} -- tehdy se zamìøíme na~bloky le¾ící na~cestì~$xy$: \numlist\nparen +\finalfix{\rightskip=0.5\rightskip} \:{\I $w$ je artikulace} na této cestì -- BÚNO je taková artikulace v~DFS prohledána po~bloku obsahujícím~$x$, ale pøed~$y$. Tehdy nám jistì $x$ nezabránilo v~tom, abychom do~$w$ do¹li (mù¾e blokovat jenom jednu stranu hranice), tak¾e jsme se ve~$w$ museli rozhodnout, ¾e pøednostnì zpracujeme @@ -346,6 +355,7 @@ hrana~$vw$, musela na~druh \:{\I zùstane 2-souvislý} a vznikne z~nìj nìjaký blok~$B'$ -- tehdy rozebereme, jaké hrany vedou mezi $v$ a $B'$: \numlist\nparen +\finalfix{\rightskip=0.5\rightskip} \:{\I více ne¾ dvì hrany} -- minor~$N_2$. \:{\I alespoò jedna hrana na \uv{horní} cestu} (to jest na~tu, na~ni¾ nele¾í~$w$) -- minor~$N_3$. \:{\I dvì hrany do~$x,y$ nebo na \uv{dolní} cestu} -- a» u¾ jsme vstoupili na~hranici bloku~$B'$ diff --git a/3-bipcon/3-bipcon.tex b/3-bipcon/3-bipcon.tex index 2393c5f..f5cf697 100644 --- a/3-bipcon/3-bipcon.tex +++ b/3-bipcon/3-bipcon.tex @@ -73,7 +73,7 @@ Pro minim \h{Globálnì minimální øez (Nagamochi, Ibaraki \cite{nagaiba:conn})} -Buï $G$ neorientovaný graf s~nezáporným ohodnocením na~hranách. Oznaèíme si: +Buï $G$ neorientovaný graf s~nezáporným ohodnocením hran. Oznaèíme si: \s{Znaèení:} diff --git a/4-ght/4-ght.tex b/4-ght/4-ght.tex index 313dc54..1aed5f7 100644 --- a/4-ght/4-ght.tex +++ b/4-ght/4-ght.tex @@ -84,8 +84,8 @@ Nyn Nejprve v¹ak budeme potøebovat jedno u¾iteèné lemma s~hnusnì technickým dùkazem: \s{Hnusnì technické lemma (HTL):} Buïte¾ $s,t$ vrcholy grafu $(V,E)$, $\d(U)$ minimální \st-øez a $u\ne v$ dva rùzné -vrcholy z~$U$. Pak existuje mno¾ina vrcholù $W \subseteq U$ taková, ¾e $\d(W)$ je minimální $uv$-øez. -[To dùle¾ité a netriviální je, ¾e celá $W$ le¾í v~$U$.] +vrcholy z~$U$. Pak existuje mno¾ina vrcholù $W \subseteq U$ taková, ¾e $\d(W)$ je minimální $uv$-øez. +\foot{To dùle¾ité a netriviální je, ¾e celá $W$ le¾í v~$U$.} \fig{4-ght-htl.eps}{\epsfxsize} @@ -93,7 +93,7 @@ vrcholy z~$U$. Pak existuje mno BÚNO mù¾eme pøedpokládat, ¾e $s\in U$ a $t\not\in U$, $u\in X$ a $v\not\in X$ a $s\in X$. Pokud by tomu tak nebylo, mù¾eme vrcholy pøeznaèit nebo nìkterou z~mno¾in nahradit jejím doplòkem. -Nyní mohou nastat dva pøípady:\numlist\nalpha +Nyní mohou nastat následující dva pøípady:\numlist\nalpha \vbox to 0pt{\rightline{\epsfysize=2.5cm\epsfbox{4-ght-htl-a.eps}}\vss}\vskip-\baselineskip {\advance\hsize by -14em \:$t\not\in X$. Tehdy si v¹imneme, ¾e platí: @@ -184,6 +184,7 @@ do t \fig{4-ght-g1g2-before.eps}{0.45\hsize} \fig{4-ght-g1g2-after.eps}{0.9\hsize} +\finalfix{\bigskip} Dále vytvoøíme mno¾iny vrcholù $R_1=R \cap \overline W$ a $R_2=R \cap W$. Dle indukèního pøedpokladu ($R_1$ i $R_2$ jsou men¹í ne¾ $R$) existuje \PGHT{} $T_1=((R_1,F_1),C_1)$ diff --git a/5-mst/5-mst.tex b/5-mst/5-mst.tex index 86b4218..8c27cf3 100644 --- a/5-mst/5-mst.tex +++ b/5-mst/5-mst.tex @@ -52,6 +52,8 @@ a vynech \figure{mst2.eps}{Kostra $T$, cesta $T[e]$ a výsledek operace $\(T,e,e')$}{\epsfxsize} +\figure{mst1.eps}{Jeden krok dùkazu swapovacího lemmatu}{\epsfxsize} + \s{Lemma o~swapování:} Máme-li libovolné kostry $T$ a $T'$, pak lze z~$T$ dostat $T'$ koneèným poètem operací \. @@ -63,8 +65,6 @@ pro kterou $\vert \check{T} \symdiff T' \vert = \vert T \symdiff T' \vert -2$. Po~koneèném poètu tìchto krokù tedy musíme dojít k~$T'$. \qed -\figure{mst1.eps}{Jeden krok dùkazu swapovacího lemmatu}{\epsfxsize} - \s{Monotónní lemma o~swapování:} Je-li $T$ kostra, k~ní¾ neexistují ¾ádné lehké hrany, a~$T'$ libovolná kostra, pak lze od~$T$ k~$T'$ pøejít posloupností swapù, pøi které váha kostry neklesá. diff --git a/6-borjar/6-borjar.tex b/6-borjar/6-borjar.tex index 139ba1d..1c4e63e 100644 --- a/6-borjar/6-borjar.tex +++ b/6-borjar/6-borjar.tex @@ -1,6 +1,6 @@ \input ../sgr.tex -\prednaska{6}{Rychlej¹í algoritmy na~minimální kostry}{} +\prednaska{6}{Rychlej¹í algoritmy na minimální kostry}{} V~této kapitole popí¹eme nìkolik pokroèilej¹ích algoritmù pro problém minimální kostry. Vesmìs to budou rùzná vylep¹ení klasických algoritmù z~minulé kapitoly. @@ -61,7 +61,6 @@ T Pokud je $\cal C$ minorovì uzavøená tøída grafù, existuje koneèná mno¾ina grafù $Z$ taková, ¾e pro ka¾dý graf $G$ platí: $$G \not\in {\cal C} \iff \exists H \in Z: H \preceq G.$$ - Jinými slovy, ka¾dou minorovì uzavøenou tøídu lze charakterizovat {\I koneèným} poètem zakázaných minorù. To není samo sebou, dokazuje se to dosti obtí¾nì (a~je to jedna z~nejslavnìj¹ích kombinatorických vìt za~posledních mnoho let), ale plyne z~toho spousta zajímavých dùsledkù. diff --git a/7-ram/7-ram.tex b/7-ram/7-ram.tex index 717add9..e66bbb6 100644 --- a/7-ram/7-ram.tex +++ b/7-ram/7-ram.tex @@ -198,7 +198,7 @@ aby programy ale je definováno, ¾e neinicializovanou buòku mù¾eme pøeèíst a dostaneme nìjakou korektní, i kdy¾ libovolnou, hodnotu. Tehdy nám pomù¾e: -{\narrower +%{\narrower\medskip \s{Vìta:} Buï $P$ program pro Word-RAM s~nulami inicializovanou pamìtí, bì¾ící v èase $T(n)$. Pak existuje program~$P'$ pro Word-RAM @@ -227,7 +227,7 @@ jestli je $M[i]$ ji v~tém¾e èase udr¾ovat. \qed -} +%\medskip} \s{\uv{Minové pole}:} Neinicializované buòky není ani dovoleno èíst. V~tomto pøípadì nejsme schopni deterministické redukce, ale alespoò @@ -254,6 +254,8 @@ po Libovolný $n$-slo¾kový vektor, jeho¾ slo¾ky jsou $b$-bitová èísla ($n(b+1)\le w$), zakódujeme poskládáním jednotlivých slo¾ek vektoru za~sebe, prolo¾enì nulovými bity: + +\nobreak \alik{\0 x_{n-1} \0 x_{n-2} \9\9\9 \0 x_1\0 x_0 \cr} \>S~vektory budeme provádìt následující operace: (latinkou znaèíme vektory, @@ -331,6 +333,8 @@ proh Staèí zvolit bitovou masku, která v~$i$-té slo¾ce ponechá právì $\varphi(i)$-tý bit. +\finalfix{\goodbreak} + \:$\(x)$ -- dostane vektor nul a jednièek a vytvoøí èíslo, jeho¾ bity jsou právì slo¾ky vektoru (jinými slovy ¹krtne nuly mezi bity): diff --git a/8-qheap/8-qheap.tex b/8-qheap/8-qheap.tex index 46ebdc5..325f702 100644 --- a/8-qheap/8-qheap.tex +++ b/8-qheap/8-qheap.tex @@ -93,9 +93,9 @@ nesouvisej pøekvapení v¹ak to, kam jsme se dostali, bude staèit ke~spoèítání ranku prvku a z~rankù u¾ odvodíme i ostatní operace. -\ss{Pøíklad:} -\figure{trie.eps}{Trie. Ohodnocení hran je pouze pro názornost, není -souèástí struktury.}{\hsize} +\s{Pøíklad:} Trie pro zadanou mno¾inu èísel. Ohodnocení hran je pouze pro názornost, není +souèástí struktury. +\fig{trie.eps}{\hsize} \s{Lemma R:} $\rank_X(x)$ je urèen jednoznaènì kombinací: \numlist\pnromanp diff --git a/Makerules b/Makerules index 0877f11..f64ab7d 100644 --- a/Makerules +++ b/Makerules @@ -16,7 +16,7 @@ all: $P.ps pstops '2:0L(210mm,0mm)+1L(210mm,148mm)' <$< | sed 's/^%%BoundingBox: .*/%%BoundingBox: 0 0 595 842/;s/^%%DocumentPaperSizes:.*/%%DocumentPaperSizes: a4\n%%Orientation: Landscape/' >$@ mostlyclean: - rm -f *.dvi *.log *~ core *.o *.aux *.bbl *.blg + rm -f *.dvi *.log *~ core *.o *.aux *.bbl *.blg *.toc clean:: mostlyclean rm -f *.ps *.pdf diff --git a/all/ga.tex b/all/ga.tex index bf8b460..28a2d82 100644 --- a/all/ga.tex +++ b/all/ga.tex @@ -1,10 +1,109 @@ \input ../sgr.tex +\def\separatefix#1{} +\def\finalfix#1{#1} + +% Sazba obsahu +\newwrite\toc +\immediate\openout\toc=ga.toc +\def\writetoc#1#2{\write\toc{\string\tocentry{#1}{#2}{\the\count0}}} +\def\tocout{ +\immediate\closeout\toc +\immediate\openin\toc=ga.toc +\ifeof\toc +\else +\input ga.toc +\fi +\immediate\closein\toc +} + +% Ujisti se, ze na strance zbyva dost mista +\def\prechapter#1#2{% +\vskip 0pt plus 30pt +\goodbreak +\vskip 0pt plus -30pt +\writetoc{#1}{#2} +} \def\chapterend{\bigbreak\bigbreak} +{\nopagenumbers +\vglue 0pt + +\vfill +\centerline{\big Martin Mare¹} +\vskip 1in +\centerline{\Big Krajinou grafových algoritmù} +\bigskip +\bigskip +\centerline{\large prùvodce pro støednì pokroèilé} + +\vfill +\vfill +\centerline{\large ITI 2007} +\vfill\eject + +\vglue 0pt plus 1fill +\leftline{\copyright~2007~Martin Mare¹} +\bigskip +\leftline{\bo ISBN 12-34567-89-0} +\bigskip +\eject +} + \input body.tex \prednaska{L}{Literatura}{} - \dumprefs -\bye + +\vfill\eject + +~~~ + +\vfill\eject + +\def\writetoc#1#2{} +\prednaska{O}{Obsah}{} + +\def\tocentry#1#2#3{\line{\hbox to 1.5em{\hfil #1.} #2\dotfill #3}\vskip 2pt} +\tocout +\tocentry{O}{Obsah}{\the\count0} + +\vfill\eject +\nopagenumbers +{\obeylines\parskip=0pt\parindent=0pt +\vglue 0pt plus 1fill + +{\large Mgr. Martin Mare¹} + +\medskip + +{\Large Krajinou grafových algoritmù} + +\bigskip + +Vydal Institut Teoretické Informatiky +~~~Univerzita Karlova v Praze +~~~Matematicko-Fyzikální Fakulta +~~~Malostranské nám.~25 +~~~118 00 Praha 1 +~~~jako 999. publikaci v~ITI Series. + +\bigskip + +Sazbu písmem Computer Modern v~programu \TeX\ provedl autor. +\medskip +Vytisklo Reprostøedisko UK MFF. + +\bigskip + +Vydání první +72 stran +Náklad 100 výtiskù +Praha 2007 + +\bigskip + +{\bo ISBN 12-34567-89-0} +} + +\eject\end diff --git a/sgr.tex b/sgr.tex index 9e8b25d..72bb227 100644 --- a/sgr.tex +++ b/sgr.tex @@ -22,11 +22,14 @@ % Zacatek prednasky {cislo prednasky}{jmeno prednasky}{jmeno zapisovatele} \def\prednaska#1#2#3{% +\prechapter{#1}{#2} +\vbox{% \line{{\Large\bf #1. #2} \hfil {\it #3}} \vskip 4pt -\hrule +\hrule} \medskip } +\def\prechapter#1#2{} % Nadpis {text} \def\h#1{\medbreak\leftline{\bf #1}\nobreak\smallskip\nobreak} @@ -67,7 +70,7 @@ \begingroup \let\:=\algoitem \let\*=\algohang -\parskip=1pt plus 1pt minus 0.3pt +\parskip=1pt plus 0.2pt minus 0.3pt \rightskip=2em \itemcount=0 } @@ -116,7 +119,7 @@ \multiply\dimen0 by \count0 \vbox to 0pt{} \nointerlineskip -\vbox to 0pt{\vbox to \dimen0{\vss\rightline{\box0\hskip 1em}\vss}} +\vbox to 0pt{\vbox to \dimen0{\vss\rightline{\box0\hskip 1em}\vss}\vss} \nointerlineskip } @@ -143,3 +146,7 @@ % Matematicke symboly \def\symdiff{\mathop{\Delta}} + +% Hacky pro finalni sazbu +\def\separatefix#1{#1} +\def\finalfix#1{} -- 2.39.2