From 8c528fb0147cceb9461acecc20e8a185e19ee013 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 24 May 2007 08:51:00 +0200 Subject: [PATCH] Prvni verze kapitoly o nejkratsich cestach. --- 10-cesty/10-cesty.tex | 217 ++++++++++++++++++++++++++++++++++++++ 10-cesty/Makefile | 3 + 10-cesty/praseci-graf.eps | Bin 0 -> 40201 bytes all/Makefile | 2 +- 4 files changed, 221 insertions(+), 1 deletion(-) create mode 100644 10-cesty/10-cesty.tex create mode 100644 10-cesty/Makefile create mode 100644 10-cesty/praseci-graf.eps diff --git a/10-cesty/10-cesty.tex b/10-cesty/10-cesty.tex new file mode 100644 index 0000000..fb5e6e6 --- /dev/null +++ b/10-cesty/10-cesty.tex @@ -0,0 +1,217 @@ +\input ../lecnotes.tex + +\prednaska{10}{Hledání nejkrat¹í cesty}{(zapsali L. Banáková, O. Hoferek, J. Bøeèka)} + +\s{Problém:} Je dán graf G, kde $l(u,v)$~=~délka hrany~$(u,v)$. Dále jsou dány vrcholy +$s,c~\in~V(G)$. Chceme najít cestu $s=v_1, v_2, \dots, v_k=c$ takovou, aby +$$l(v_1, v_2) + l(v_2, v_3) + \dots + l(v_{k-1}, v_k)$$ bylo minimální. Takovéto +cestì budeme øíkat nejkrat¹í cesta z~$s$~do~$c$. + +\noindent +Bez újmy na obecnosti budeme pøedpokládat, ¾e graf G je orientovaný, bez smyèek a +násobných hran. + +\noindent +Nejprve uvá¾íme, ¾e $l=const.$ $1$ : + +\s{Algoritmus:} (Prohledávání do ¹íøky (BFS)) + +\algo +\:$z(*) \leftarrow 0, z(s) \leftarrow 1$ +\:$Q \leftarrow {s}$ +\:while $Q \not= \emptyset$ +\::$v \leftarrow Get(Q)$ +\::for $\forall w: (v,w)\in E$ +\:::if $z(w) = 0$ then +\::::$z(w) \leftarrow 1$ +\::::$Put(Q, w)$ +\endalgo + +\s{Lemma È (èasové):} BFS dobìhne v~èase $\O(m+n)$. + +\proof +Ka¾dý vrchol se do fronty dostane maximálnì jednou a ka¾dou hranu zpracujeme +maximálnì jednou. +\qed + +\s{Lemma D (dosa¾itelnost):} BFS oznaèí právì vrcholy dostupné ze $s$. + +\proof + +\noindent +,,$\Rightarrow$``: Zjevné, indukcí podle bìhu algoritmu. + +\noindent +,,$\Leftarrow$``: Doká¾eme sporem. Uva¾me, ¾e existuje vrchol dostupný, ale algoritmem +neoznaèený. Vezmìme takovýto ,,¹patný`` vrchol $v$, který je $s$ nejblí¾e. Uva¾me +nejkrat¹í cestu $(s,v)$: $s,\dots,u,v$. Pøedchozí vrchol na této cestì $u$ +musí být ,,dobrý``. Vrchol $u$ se dostane do fronty, pak je z~ní vybrán a tím +se zpracuje i vrchol $v$ $\Rightarrow$ spor. + +\s{Definice:} {\I Vzdálenost vrcholù} $d(u,v)$ je délka nejkrat¹í cesty $(u,v)$, +pokud existuje, nebo $+\infty$, pokud taková cesta neexistuje. + +Pøedchozím algoritmem jsme pouze zjistili, které vrcholy jsou z~$s$ dosa¾itelné. +Nyní si tento algoritmus modifikujeme tak, abychom na¹li $d(s,v)$ pro v¹echna +$v~\in~V(G)$. + +\s{Roz¹íøený algoritmus:} (Prohledávání do ¹íøky (BFS)) + +\algo +\:$z(*) \leftarrow 0, z(s) \leftarrow 1$ +\:$D(*) \leftarrow +\infty, D(s) \leftarrow 0$ +\:$Q \leftarrow {s}$ +\:while $Q \not= \emptyset$ +\::$v \leftarrow Get(Q)$ +\::for $\forall w: (v,w)\in E$ +\:::if $z(w) = 0$ then +\::::$z(w) \leftarrow 1$ +\::::$D(w) \leftarrow D(v) + 1$ +\::::$Put(Q, w)$ +\endalgo + +\noindent +Prùbìh tohoto algoritmu si mù¾eme ukázat na následujícím obrázku (,,praseèí graf``): + +\figure{praseci-graf.eps}{Praseèí graf}{75mm} + +\s{Definice:} {\I Vrstva} $ L_i\subseteq V $ : $ L_0 = \{s\} $ , $ L_{i+1} = $ +$ \{ w$ : $ w $ oznaèen pøi procházení vrcholu $ v \in L_i $$ \} $ + +\s{Lemma V (vzdálenosti):} Na konci BSF je $\forall v: D(v) = d(s,v)$. + +\proof + +\noindent +a) pro nedosa¾itelné vrcholy: OK (algoritmus je neoznaèí $\Rightarrow D(v) = \infty$ ) + +\noindent +b) pro dosa¾itelné vrcholy: Víme, ¾e pro vrchol $v \in L_i$ platí $D(v)=i$, +staèí tedy zjistit, zda $\forall i: \forall v \in L_i$ je $d(s,v)=i$. To ovìøíme matematickou indukcí +podle~$i$: + +pro $i=0$: evidentní, + +pro $i>0$: Pøi procházení vrstvy $L_{i-1}$ musí být vrchol $v$ takový, ¾e $d(s,v)=i$, oznaèen a tudí¾ patøí do $L_i$. +\qed + +\noindent +V¹imnìme si, ¾e v~grafu existují pouze tøi typy hran vzhledem k na¹emu algoritmu: +\itemize\ibull +\:dopøedu o jednu vrstvu +\:dozadu o jednu nebo víc vrstev +\:ve vrstvì +\endlist + +Abychom na¹li i samotné cesty, nejen jejich délky, modifikujeme ná¹ algoritmus tak, +abychom si pro ka¾dý vrchol, který oznaèíme, pamatovali jeho pøedchùdce: + +\algo +\:$z(*) \leftarrow 0, z(s) \leftarrow 1$ +\:$D(*) \leftarrow +\infty, D(s) \leftarrow 0$ +\:$p(*) \leftarrow$ ? +\:$Q \leftarrow {s}$ +\:while $Q \not= \emptyset$ +\::$v \leftarrow Get(Q)$ +\::for $\forall w: (v,w)\in E$ +\:::if $z(w) = 0$ then +\::::$z(w) \leftarrow 1$ +\::::$D(w) \leftarrow D(v) + 1$ +\::::$p(w) \leftarrow v$ +\::::$Put(Q, w)$ +\endalgo + +\s{Pozorování:} Pokud $p(v) \not=$ ? $\Rightarrow D(v) = D(p(v)) + 1$. + +\s{Lemma S (stromové):} Graf $(W,F)$, kde $W$ = dosa¾itelná èást $V$, $F = \{(v,p(v))\}$ +je strom orientovaný do~koøene $s$. Navíc ukazuje v¹echny nejkrat¹í cesty. + +\noindent +Nyní uva¾me, ¾e $l \not= const.$ : + +Uká¾eme si trik pro ohodnocené hrany: hranu délky $l$ +podrozdìlíme na $l$ hran délky 1 a pak spustíme BFS. Algoritmus pobì¾í s èasovou +slo¾itostí $O((m+n)l_{max})$. To není zrovna moc výhodné, a proto si uká¾eme tzv. {\I Budíkovou taktiku }: +Èasem $b(v)$ budíku vrcholu~$v$ rozumíme èas, kdy se do tohoto vrcholu vlna dostane, kdy¾ se bude ¹íøit po +dosud známých hranách. Na zaèátku nastavíme $\forall v \in V: b(v) = l(s,v)$ a pokud pøi bìhu +algoritmu objevíme hranu, která nám umo¾ní dostat se do $v$ rychleji, tak hodnotu $b(v)$ zmìníme. + +Tato taktika nás pøivede k Dijkstrovu algoritmu, kde se ze dvoustavového $z(v)$ stane tøístavové +( $z(v)) \in \{N, V, H\}$, kde N znamená nevidìn, V vidìn a H hotov ). Podle hodnoty $z(v)$ se +pak $D(v)$ rovná $+\infty$ pro $z(v) = N$, èasu budíku pro $z(v) = V$ nebo vzdálenosti $d(s,v)$ pro $z(v) = H$. + +\s{Algoritmus:} (Dijkstrùv algoritmus) + +\algo +\:$z(*) \leftarrow N, z(s) \leftarrow V$ +\:$D(*) \leftarrow +\infty , D(s) \leftarrow 0$ +\:$p(*) \leftarrow $? +\:while $\exists v : z(v)=V$ +\::$v \leftarrow $ vrchol, pro nìj¾ $z(v)=V$ a zároveò $D(v)$ je minimální +\::$z(v) \leftarrow H$ +\::for $\forall w : (v,w) \in E$: +\:::if $D(w)>D(v) + l(v,w)$ then +\::::$D(w) \leftarrow D(v) + l(v,w)$ +\::::$z(w) \leftarrow V$ +\::::$p(w) \leftarrow v$ +\endalgo + +\s{Vìta:} Pokud $\forall v,w: l(v,w) \in Z^+ \cup \{\infty\}$, pak Dijkstrùv algoritmus +najde nejkrat¹í cesty v èase $\O(n^2)$. + +\proof +na pøí¹tí pøedná¹ce +\qed + +Nahlédnìme nyní, zda by vedlo k~vylep¹ení èasové slo¾itosti, kdybychom pøi~implementaci +Dijkstrova algoritmu pou¾ili jako datovou strukturu pro ukládání vidìných vrcholù rùzné typy hald. +Provádìli bychom s~nimi operace DeleteMin (maximálnì $n$-krát) a Decrease (maximálnì $m$-krát). Zmínìné +operace mají pro rùzné typy hald následující èasové slo¾itosti: + +\medskip + +\vbox{\halign{# \quad \vrule \quad & # \quad \vrule \quad & # \quad \vrule \quad & #\cr +& halda & $k$-regulární halda & Fibonaciho halda\cr +\noalign{\medskip\hrule\bigskip} +DeleteMin & $\O(\log{n})$ & $\O(k.\log_k{n})$ & $\O(\log{n})$\cr +Decrease & $\O(\log{n})$ & $\O(\log_k{n})$ & $\O(1)$\cr}} + +\medskip + +Pou¾ijeme-li klasickou haldu, dostaneme celkovou èasovou slo¾itost $\O((m~+~n).\log{n})$, co¾ znamená, +¾e jsme si pomohli v pøípadech, kdy je graf ,,øídký``. U $k$-regulární haldy se celková èasová slo¾itost +rovná $\O(n.k.\log_k{n}+m.\log_k{n})$, ideálnì pro $k~=$~${m}\over{n}$~:~$\O(m.\log_{{m}\over{n}}{n})$. Prozkoumejme, +jak se nám v tomto pøípadì bude mìnit èasová slo¾itost pro rùznì ,,husté`` grafy: +\itemize\ibull +\:$m \approx n \rightarrow \O((m+n).\log{n})$ +\:$m \approx n^2 \rightarrow \O(m)$ +\:$m \approx n^{1+\epsilon} \rightarrow \O(m) \dots (k=$~${m}\over{n}$~$= n^\epsilon)$ +\endlist +\noindent +Pøi pou¾ití Fibonaciho haldy je pak celková èasová slo¾itost rovna $\O(n.\log{n}+m)$. + +\medskip + +Nyní si pøedvedeme trochu jiný algoritmus na prohledávání grafu. Mìjme matici sousednosti $A$ +ke grafu $G = (V, E)$: $ A_{ij} = 1 \Leftrightarrow (v_i, v_j) \in E $. Potom +$A^2_{ij} = \sum_{k=1}^n A_{ik}A_{kj} $. Tento souèet je nenulový právì tehdy, kdy¾ +vrcholy $i$,$k$,$j$ tvoøí sled délky 2. Jinými slovy $A_{ij}$ se rovná poètu sledù +délky 2 v $G$ z $i$ do $j$. Obdobnì $A^k_{ij}$ = poèet sledù délky $k$. Pokud +k matici $A$ pøièteme jednotkovou matici $E$ (èím¾ si pøimyslíme smyèky), +dostaneme po umocnìní: + +$ (A+E)^k_{ij} \neq 0 \Leftrightarrow \exists$ $i,j$-sled délky maximálnì $k$ + +Výstupem algoritmu tedy bude matice $(A + E)^n$. Mù¾eme si také v¹imnout, ¾e +pokud matici $(A + E)$ umocníme na èíslo vìt¹í ne¾ $n$, tak výsledek bude poøád +správný, jen bude výpoèet trvat déle. Tak¾e algoritmus mù¾e pracovat +v iteracích umocòováním matice na druhou: $M_0 = A + E$, $M_1 = M^2_0$, $M_{i+1} = M^2_i$, +tak¾e výstupní matice bude: + +$ M_{\lceil \log{n} \rceil (ij)} \neq 0 \Leftrightarrow \exists$ cesta z $i$ do $j$ + +Pokud pou¾ijeme Strassenùv vzorec na násobení matic, dostaneme +ve výsledku algoritmus na dosa¾itelnost v grafu se slo¾itostí +$\O(n^{\log_2{7}}.\log{n})$. + +\bye diff --git a/10-cesty/Makefile b/10-cesty/Makefile new file mode 100644 index 0000000..cc5ae84 --- /dev/null +++ b/10-cesty/Makefile @@ -0,0 +1,3 @@ +P=10-cesty + +include ../Makerules diff --git a/10-cesty/praseci-graf.eps b/10-cesty/praseci-graf.eps new file mode 100644 index 0000000000000000000000000000000000000000..e30f7e12122a61768c6a4f46d6afb37174016342 GIT binary patch literal 40201 zcmeHw2b>dS`u|LlnPf6aHv3MJ0kTR^6x*7f-GI`Is1yYh0l~1FT^6>ng(6@>J&GbW zEGS?B6~%fgHf#q7id~vw?-eU{{@>@FWZ65f?5y{@|J{Ag<6&mr_j#W8d7t(^?>iH2 z{qrwv*k2HY!ZCsn2JGyMhunXA_a4+`_=w^@<#iLY#qlE}p#j5345S;k^Pq$JHDohQ zbq(D^Lo#Izbv4=Ys!V8Lb*6DrC}tpxtZJ&xb`KrWulu9&tg5)OAyaW=w!ZPu z76w&ywf!?qgceDLBk6FYWon}C+-9_m+}&D56kt!g3; zee0TQ%d2WD`_|3q9*W?9@l;7D9!XH&fZFnYbu~oT$WgPERkgz#>Zgo{3ZVWYK8?z15vgJp*o#Bb)p;;5FYRg0A z*@`)#{2e-~(NSHO$#;~aX$G3IGs-6AaH(lfDBPHBf=XtFs_FSe{@hSGu?$i+7;O`d z3(bm$Fh+JpC{tb@s?Ao0%A4yk)#|3utol0K%?VXigyNxS2$QRZ7{uy0&Z?|t<`je1 z^hw!+cYOMYgRPW*gP?m$T0|EMB@)|TV%mN#sq1wY;|Lnrh#$FLg9w8 zX6U1-&XBhn4b@e(Ezd(j;hMUA-DUNma9MR-W41oiG|8YC7@Ad4)gt(a&@7Bg9Hv*5 z1EsO4p>9exH><(JL$k)7in#-&oE#0J8^~pu`h5?R>#AyV6eEuhg_{~OwT;#AF=M=b zBOyXvZCR$tcpfw&6s~N{Ov`l-f)y%ZWO#P2rEh4~kdR?IuK4`?cvHma$+wYtBB9(< zPKJJ9&^LscXY0zUtLkCG=`{OX?}!ltYRl@#i9;irGPUKIhVqt%STYsLG?0Ik!AA|1 zx5AI7!&95L&R2BXTk$A zWz9|5@X)5J>hf%OSPR;ymb(ncfVnfAVK`G(1*_LoRA*;|GyAX%1{u!1EYCe_aL;l| zus{}Qp@jfBk*W-=DuaJjE1aqpoLYl_U0#?v1G%mhGW3{ZSZ5$N8+@A$)aF*G&3RPF zRGz7<%r=C}A!IfiETFZEKGQ%-sGk%DMGfpVu^Q#Lg^YpQCS8^hJv#zq4Xg290sjE9-o+Hg%XiPBV+sV=Xos0cSU*VJT4PB5x(s4H(S zgQ!*D*+h!34%ao5S7gByaYgqvnZ~ka3bOF9nrvkzoIz_|j;YOXesC(Un_e4+k5^}E z_$?A=RavGQvWGD*x(!z#O;y!~GxZp9h9O)3Y;{v6T-glI%GT5&|5v~%_dW9@8qQWD z4#*Q5>oaB9a38}ueR2+%y9@}|WkH%nNHk6gXKVO{`#W?_d=2NvgTa({?Q1t0%d4hU z!Kth3PS4g>61$l#MmVMAuA(7h*ch3tAzNEElgrDaiu0q{@F#<3MHMCvR)*JL{BV7? zp{lN&{DynLzM!0lRj)-%{s7dbNp;PQ@Eow{)5;+Sw7TzOILv?+5eFD58f>%=ZiPCy z1!pkF0oP#$*05GsFi|y(ZEzW7^p9%QKg#GSCyO;UR)t%2adUuc4XyHsgNE!hxN==n z1|g0>F`_+}N+vbeR%RNSYpOHNP2sxAy4viNa9IXqf0me{vCS_+EQ;ZQgZm?;hGy|Kn6HR@vC1t| zb3zq$2mmZgEm^fyiUdu_FnSZ`4QHb)i@@MR=Th{5q5Fp8NgwjjXnds|F_15{9G|b^ z1JTeTJZ~8?uzzS)O=gP0l*`FUhYZAO*V2xajF{xc96b`Nb$L}|2z3LJQ3G8gw8Y^y zrwwD>o)xa5zT7P8vGg@@q$(h{R&e8_y6L%93|y||2HPmmU+c|i++u3^2ZuLZ~ zw%eJCltx0Scp?%S;&v7%W1-?`q%?$Zi-ZQbov}!0L@N@k`mLS}2FY|uGL(wO676PC zno5U~X^h%l2})A&P%@Q{wVOdISrSSnN>T=cgn1n#lhIHzmdYuy9SjnQWGER)(7d(FnMi@uQMh8uZCTw7v9^640kG z3(^1|zr@V=snR6qOJar-n3q45f(7EGh?th~P0c@*ApNDIh6}V~d~BvdiAXMt%+n)| zK_88@lHXh&D1rVkhxW>!Op*u3N(~Qghx~EqF98FzQ~$|GDd-a=`SD|TFylXo(o`~( zNT%}s1Nx*XdN=?=CYj914|-GnlSo8MLWz~97G_8wW2pSexwAePz+AgKKWy%NS(=eX+Hm% zl|Pn>VF^i;w4yg9e=HG!{*tM7(??67zf>}xf6dAtO@lO9l4wP5O8zJokWjL;CI4f5 zbM(mw^p}PbTkK~l{!w7ZLa9i!-SiQZ52+}GXy5pWc%n3v$}PXBg;33ysNxdQR3cOg z51_$KQ^(UNBFTPvYEvsmyd<3pA>kX5V}5WdTB0%3fceo)%{-1ZClsaRnI|_Vd<@G( zG?@!K65bp+SskuxSl#s8W2G>2v=ouoF5zQTG{+*jm@z*(*33{0!?%oXO7pQeHVr5{ z_u1W)>S9rBT4ITGJ5`5#lM2OBx%JYt;gId1y4De6O896Jg-$GueMjDKrc{TiC$PzD z6*A^VkD*MBw+ETQ0TQ!e(Z6QNH@7< z!o2)^j}uMjYc%unBUd3` zM;}Y0O2ZjVd-WHi?JeIZwsZVs9QrHG?@>(aKNd%MkBx47^%tY#l|-c7>qoQ{%NI)3 z_UbQ6izn*ceEgutkcN zVrSnj%||0~>@p&`GhNfdQ=uM<;;(kep2AUR4BrN|kDB5nM(L(qW5+O8ypCz7$0g&) zP}pAPmf0k|TtoQar3#!7_AEpEf`6zO2VV59C{)UuuqREl}?^KD46@1d>Sl2`;$ zh_)0`BrzUvUmCm*HUF#iPOq^aP|>4Xx25h2{@=8TlW=`;#IUb&K$qX09;i9?WB z?!+jC1*HTAF{`A3o1$hef5>7~6H2CbtKo`ISoZH69iMnh@%0EQ>mfc@bcxEi6y zeFFhZVQQph?oP#^g)4xboapcPORIzo&&VZY!-?SMM)dNCBSze{ zI9H5P3|Ga4``7Ob1v6lZ%6zQy97H2Hs-hqiT+a0(n9@NNI!bc%oE z*3dk;HRV%s>$WcL(Goi9P8xeosyXtj3vQ91O=ZD9a|qOBDO4dQauCWNdc}?R)c>p% z>OUwAnaLuEIeg2I&V9>}Kp|b6MrCV8)iJCu3Hl@gsz&V{$2x9`ytM!^%3?7by_w(; zCD%%%^G8*`GX?+40{U+x?0*!S2&L9bju~6ybqG#HQn~N{xT(0M@m`RWZYsc{C3Lrp%L(#ecV;VTe)N|i#nln?%x;RL+?ZR^5; zjSWl@F-lH)S(!%31z*aQ(QRgvvuJL60}B!p%#PO(riy5sY4G(UcYOQbnp2GZ5P3Y$ zDpBt3bfSS4@(3OTxF873cm@Bu6^jb@3VMfuGgMO!!E4)m8576rZ?n~8tI{|g$0pL; z_Lgrzj8Zg)0u(2j<`$#`HcYXIk!SI-7`=z)o=8_5PyOZkh_{3|ZfeOy2_BNDs9}IO z_CAz>jN>bCA_h3~Ff0YX=JkE9SR+Ma=``?Zm7wz^B7iAVyctHNaL3nM;Ehcb-xXnt zghdyO2oD#$xC9H-T$Id^nZX5TlW0N-gnR)kNI@HO&XZ>l+G2wq@^D04u_rJDpe{ow zB8M`OsQK<565P>Sk>~22+twJA9B*{jFU({o^kL;Q-jckZP88xQ4ku756TeIzQbhOKjq!GZ7J>C6UPS`y1Z?Aqx- z3(=5!YnMBg0$(T-*p$t=fVjb%1|HNTmGNl@^u=3f;<*+ICE$_^@ZyAI=Pht(xH`{C zG(JA&Lxj;QE2?I&d*VoV8-ZfjSVKziQibkXOPh?s1~`-BX%4!@{Gb||G7fNB0*)LJ zODp$M?md_@!kw6b0_w+68aY4r2YeUF&pObIz~fDL4HDuWPsgyNFc1+-9T&gJP`pC&4!O) zVDyk||HZ+7eH^rQLTtw1(`l@K z$e$6oD|vS=i&CIq@kI+3bmNMzuW5Cs@Btt?;L}Jq6sLI0#={|(zH&T}sVNiS?FD6a zyiYI2*F}^rhy;0tx)IoDH!2l08x<3U4&{toJfl6I5O8a(N{D^>!-L#tq^Kl`ARAm6 zIRZ4aj_0GCq937%(a>ikD1_j?h$eBsjuMO!uZReQ1tkWE!XvnZVi|4F8bY7Xg$F&v z;{^*!JR>V(AZoxGgH;JhlERBmr?vX|VOcbdL_o_IsSw(RmbkVd41ea61Pf9KE|^3< zbJH_qMF;-o;u#SPENsz%&L>VMvGnOV8Is0ID9!Y^l0YIxGHw6L`WZX-POD;U}D#A+7YpC2a48e8IX9hw{ zj!X$-K_ad!s%tPNLL-5{s6SuWWAP;y%wdtGNS)whs0yf%4?++UnrK#r_V7UJBg4|F ziK*p;gkA6lZMk4JtOa^d7##3--nA)M@c_1l2pk8rFakJoQR#QOc)$dx>W4u1;VfB% z%wiN7IW=HBq&_%jYY$7%$r7>=MI)ayi3<6UAHfvdcqxrx!HVi^BrW{5fZ9iXPGhe&2_KAzqb`qTv_d zfoX8V@mX=3<(w4~@HWyant(={2CH1{LvC(3Jz@s@;L0Qxkg-=FSzs2@7~awwYQ-`^ z%{ZJwtKt6mCX2Vx7+i1&L~`?iX?kElqJjY~5ETq)5S{~ReWSSIY=KBK!87zk6ThKWywu+}s8lJbn4RTGtAw{C+OQ|{1DE%@sUW&~rh%t}<_C@gD zpwwt>xoC=tlnDF{>W51sJjvEZiZn|9oa>QSQrN(SjCPoc{*XWNMv64Uv;Sqg3JN9) zb1oRNLT<4z7L@<(U|~??fPc>&Y-=aP52cWK(@4Lx{QS?Yj2PrA3aw*USZHDR-@yo9 z!~U5EBdwhfFW2ZNvbkSxQAXog%~+yaoyAgNfTV-98>FwL+Vt-|rtk|ouD!M%X_v%su8x0_h!>DhHr1`9K{yi> z3g_W_2)+a1yN$nlO!>cpg8Y(#H-Fgizaw$P>|Z?+ZyhrD?JZodD#DpJc{Qo>} z`#0EX{2y-UTB{%bvJke-xzDNo<4*c;`tg5#{MlMru_XP@HTN^w+>VZ~ISBiG2O^X} zX}S3?JOv_U#OOy?^d1Te^?&pU4lVv|JgI8!1o(&khT-kCC@6wpt?42NHo-5_zY{G1 zR7?KOW!a)XT10IYks2L2S$TZ!6j-R-89x})Nk^1)?YDAcUQn# z&@T`#Fe~RP{!Bro|02_LKlmOkSm^uAG~Ir_{k(T*$C>uC5^aumBfG^k-O20~?+1kz z)A2C9@W?`Y;W*QDS9li`cJtn6n(qFBcMAs8UnNx5s@Y`-6LfX*%8g z4ZFz|GM&##Ttl^u>TJ_=C#yGWA2_#~rkn1x`RvY!={$dhGTzrsxxh5t{f@Q1L5}xL z(`~c+{FV0Jrq{7Oa;^Ul@-?REbonX&P11L!=}M%ofsMA|rq}7wwle}BT34HzClf|o_JbXOOIEIkXVEoSN7_N=v>?~$!$=??RZv_9)zVVbVN{kb*Z z?rt+X-h-}rw(+j5rs*uM1Ef`Iy<~R0W7UVH&z%n0EZrr}k#fp;y=l6g%5M1#oVIKbg?)H}?Mcej0=<0QLNF-!NOe3G(EzR@&YUwOCkzSPrccDx1B z1Z2ec34@o!6*4E>HPA7x3@Fvoo1Tu zhl1Oj7Z$v2nyyPh2lZahP}BKru;*NLm-|7}bW`2CRmpv@={$IqYn-dtb%|-Z$JM7? zqtstb(|zPjxaT-0o6duU&K2&J%2v~KX~pH);^=ESe`XvrJm1=HH%+&|{;p?#dneQT z+q>oA1q0>tP1Eg^9xkYtzA{ZGONV%`v5hyqFOJzR^FC$WY?^MoRVe(*k}|!&ooA^o zEV5j0n(l6Kd*Lyn$MimRwet;OsPk~s`+%>M>EdO|lcwoXN`YmkW31`@!)(V*mXPCX z({z8b_p(;l7nZt_z0Cb+)ghhfLF5CfTKwG{SUUu+z3&nr-{UG~NET z68Q=1T+?+yx%D|&wgyeF)2l6&_Tw%0n5Nq;?zLYc9%p);PKj4IwhQl=rkgE+k=zPId0`d+ukeLL-G z-&T7M-^=!1zGvcz)5Mp50o~^RCvzvqS6ed0rdl*{qHA zY|tio)`RZ`ZLVjdHXm(^JH(f5;GM)6F^m<343Rd^KmSIm4|pBxU)JWzBCqqC zd`0fwpe6dY?phnT&P#;#fsM}l15Y_u2cB^*3%uyOH1Mi(LEwGoxq+{oX9e~;&kVTL zvjUyevjZXZ+(0+={J;_FfE4XJ^W%|UQf#+X&dJ1YTX_yX*(Z_oHo{y_@_b`Zoa&>xR4w zbnk-xL-6?+{6228osQtL`UIkBls|w>??JYAAmba5^)>rqc{}8O*?zVBto<7KY0P7j z{d$bO3NqXbSyn@))$$s^t$@|`TLCohw)zSF|C^z!!!druQvnz)M?J^MNl!1ihbJNT z_Z%({^Bg3P^>mRZc|!6uT<3ZYkmsXqv8S7SIr^6ZZ7@TfX0Ou6(cO0{M2&63|{Pukc(WU+Y;8Ue|-?D)7D;W30wl ztK~BRa{#kFw*qd13~ilT2R=6^{9qdBCxP!+j4=#j_V-*Q_w>w{yL;xy2~Pv&O!IFm z-+bQrRdTqA?s?hK=G>o;XR^1MG4t`9bqr@GJ5FH7I!3XcjR4CDEEaOi zW1SsKaJ_+baomEoJK4dGd(r<8@HVi%ju%0%v>GG1gmiOsj2 z$mZCNXHy|R&7-Y4%g4lOTS4I>&`pvm+N`&{ePhTWMBCOe^K=hs-xX}r9yaY4MDq(< z*5;FsynWyCXV}|-=lr#7gMTJ_%zqwx*nbIo$iD*DHS7`pJ!pH7J>h>8{p*4EJbT^$ z8hhXWCi~p~4%_2@kBNcz0q-#jzy@#tyn%O_7I>TKfwx%az#FVvU^|Njo@dFxW>yl| z$hrsCv!er#vOa+aS--$NY(QWQ;1=8DW-OnblyIF?a%F5VEz;%G-fMu*4kY!imegSai0DmgzE7&pYG}f1mV<~nLi-FT2 zm|fIT;~jrq;$y|dmP6&b-*BM*zxGXE-aFmW z2QtxJCyn^cIn2J%?cnk=|Nam+fA)Rhj}}SbpD4DpTlhDNrIJ-RRyaTi3U7Kd_^v0z zws_0fdT*9J>YdE~=xt`Vd(U92z4O^}?+kX8cPhKwTgw)BtJs;|Nvzg8g;jX#*#z%& zHX3-NynkRPdM^en1Kf<~yV)t;huCS}Ke0;h)2!b6Je%o#iJj|x8SoN25AX-TLJlvo z3%oC~MSx2HS9+ggOTAk#?lbHL{+-g}>>lr3>;dn?>|yU?>@n|p_JsE-$odT1=zW$w z1^mt47ufUOSJ+nXcDBpAlfCDCm3`*j!S;B!vc2fD7H(lu;nRT4Oa?dr1%;0>U*UaB zFI>$!6fVPcF`myu`|0R!V822S-$EZBdnYnOM^o8r-WvA4w;H^w(N_n)gnKq~A?6AS zFJ)fvDJZ;|xeM=NO5p>{R`@vk*}DO_n?bV$ay`qoL+&kT+vt6q{mJ_X=JFusbr)Of zy$RPV**fnf>~ZfRw9iNX`IzTi;GP4T>9EsOR_;BE)#3gO*yvoq0^DEZoeBHQVb=nG zrT22^?t18O4ZFg7FS`tSTZFOZL2u_kpR=L6W?bv=T#oT4c<*E5ymzoM-c^8Waeo2Y z&g0|c{c7*ty)FJ@ZTTMcANijVEf(Qm(3VOT!3D}{y(`NAJ`Sv8?*txThwBfpBK->% z1@yuFDS+|%O>7{5aHF_>ht=SC{aAi)@H8*OcF54xI$0R5?Q#v%-f<1lK6VY(cDn{? zU%CcrU%UEidt5!WA6;qfS68uSbMLP?+y$Bo;C1h(G53L*&wZHI!JW`LyN}WibNAMg z?!H<-Tt~Q%*2cPfXcOGswG5yfIFsE`t=b*d>fDEF4eo;hUA0DcM{TOxk2X!Kbu)km zI4W>utWNQJMCUs{(qP1pQTM+i-mj z&ri9=YmWf;e%FcGA6>_4cf0xm61YD^d&sq)w%*l2d&cG0UU7BOw&F{-Ev|0bMpsyS z(p928;pzeCt^EnQ-vC=|b{&WQq1uZsveECg^K<%K=O%rQ^GW@5=R^7o=RJUxxW7t2 z+qpRhN_u^k-+8k>&v_f*E`5RXUi|{+gZg6U!{~oh zztZ`*euMKd{TAms{Z6#s=Ul7b@4R1s0CTUW#>a93!x>Y|+U8zUZ>-CtrLQkq! z>!s=yfXnr?xQQx^ zp2D? zPhYisw69jiDYl&UHOi&FW;yAbDaQa2-|6xZzS;7@zB%%NfG)l>*Skdd?O`aD=!Bu#r+brEs&p=-&yyI$OUH_5&1g_*Up-{Z8m${Z`Ncet?E{ z2JiwD;LFzC!mpMugl_?#kUjp=ruj+&Cc}S5Z~kf#?nE0^2!{$s2x0LS zp-8+Bf=}EbqyPhOKSF#%7%#prOcFm8>cnq^ zCh=!sx+se?M6Wna>?AgdA+c6GM4TiZE|!a7F(a0UW5k}~P;sExS3F)!h$o5%i=#z5 zTE7>@iXRJO#J2!Dg_FfC;QoX#RD3`fDBdmf64wYN;%Y9ROMFT2icdk3$A$gHwZg&Z z4~uu9{~n>cc(2eCG`+=#g?^y#54-{53%KsY^Ls)caX0#Y5z=A@F^RFGVoEHAM2AD3 z!^Hl8L1I_&B(X@G2#iWGAXbTf4wG@M7TsdKD2WZ2XTA8XFa_K);upe5KtJ(IAqpMr zFa9VvMT_`}Ad9aqkxdK*3G2H-IBD${j=?LwCH_Co;?={a{2Z9Sx|?q1TX z;PIBbzx0870LJMr?ZLC?=_xrq-6fwVChg}rR64}dS&DmnQg4qe4e{);jq`k9o8sAO zn+-VIla|i*43SQN~KCq5)hXrdBW0U@SEZ}7|>O! z_Iz!t_Bf=IJo`!gJV#1VPcNy9XOI-|43%7-k&@Lz^Z&~zYpV|P)$l#i#q54*K6_A_ z%N~~Iut%inxYpr$61!VEmE9(t%vMPw*)r)wwgfN__p_z3Y^s!H)lxO9lA2kqG>tV$ zHEfnt$>vIBY@sxfT?DvHDrZ+p73^ARGFy)R>!k*EBgVJ^V_hdLK>K306ysklT?)J_ z*d@}{>_TZ7J6pPuHApwJGU+zJofzwGHeLE7J40HF@gHT2rOn{|3gmeQ*RR>d(oYy~ zFIyyu+9JuO&6Awkd6G+;D-~#SB&MAXm?3FejZ~;rp{-K#Xcd5oz?lHtF_K+7S(3F8 zlB5ljtlIH_f#A~*?Y$*c>m_+{^=kv9PTH|jk#>UASsN{dw2ah6%i=m2&?N1zogoD= zwyrG({*~anOtNSzr61WX(r&jdUGb zf%&hLt^wW>^j`+NOBvbd_uBb(WiY#0>Bp{Ddb6vQp6n99xwxO93}Q9P3Ha`CG|MU( zHd&d->XlR2bY%oPQyIqopbTXT0gIL4>@wvyzo1k0?xCUb_V~xrRcDiyS#=n(apxg)Ek3*j4 zaD9VasC6j>XnIJ6;(s*O}!+Np|L%ivl8 zs8^iY>55%DSFvgr0RJ-Zy;}L4U8lUyRw}OncCb~-Ht6#uwp!W5ZiW1}D0j0Pm6gDQ z4=eCzW%YRtO=w5MU-W1x?bnEMc12jTfB z@GHR_68;H#%zqMK2=0$UTM~T{;B?bZf-T1ZCgQ%*e<wWYO^ig`a!zew}VWFM`48Z-VfQcRY>Bj;HH;LXX4q>ZafX_4(i_>h|C$_08Z&^1g5%V0(7z{G zuKp0LQ@;;3tKS7@qx~FpcW|!yMesb}%~wANUZB1mT&!*lE>SlIuU6LvmjSLRN}khl7IaA;A5>`6F=e2>zhn7W`hlIk-o?G5D=|9bhT=T#5F}gTJVk z1ud@2gLc=|L6>WJ(BoPaEOf02GS_`U&GjIzj{-IYy{?ynZr84$;(8DGpMme!!Ee+b zgP*Fu2Hys}q3#XtQpKVjskfHx2Q z=L7FN)loE8brsE03yPZ6!lF8r6;?%90I+a ztUewbuab@0Yv+80_jItAbzSf{>%GBo)(3;*t&aysSvLiTSzinuZ+#8zZv#FG4zYfY zwr_$Xt=|VvvHldCVErYSwf-8c!L=FBXIl3J=UKlFUSj!ZPuTI+pIqZw_ATe|DNFM)^CGvV2rn{Uk2a9c<)(1 z4Zd&vF!&+(ePn$Duq*hn^)|rc!I!ODgO6K32;KpCmRp6Q%dGaI1y*;_*;ZCG)9Np( zvFb$`YoO?4t5!73T2M5|>MZJmF}p+75{#d)ehko)&r)ya3oL99^(e=uz;F(6L~&=r1@;)Cwxaf`X}{ zTF@lQ1v5ke@SW#$@f**XV()@8#Xbe6i%GOa3Z{w01r6d61vP*w+?S(mv`AyOSN_&J z!mQ#IPE{1)Bzy}sR1t-N_~#emid8sJ@d&!oQE)5W1e;PK{NgxP_|7p#_}Vc=*zLFw za1HKPqwQYwJt|n04T7pXEojQK!hXtgLN{fL5LGq{CCYlCm-494S9u7$*J6yjgi*>$ zjCqw%rYsbylsQ73GG3Uf3=DRtBMOq%d5m6OISpW0VVp{>tST`zoQ2vJ|jP=%K8^{2stprt5@a zzoSQ08HN%|fA)5jrY;F~=lybQtE@ aSvXwjAS9In;b`cQWc^FKSm7^%@c#gau<{Q8 literal 0 HcmV?d00001 diff --git a/all/Makefile b/all/Makefile index 610ec08..89aed23 100644 --- a/all/Makefile +++ b/all/Makefile @@ -1,5 +1,5 @@ P=ads -X:=$(shell for a in 1 2 3 4 5 6 8 12 ; do echo ../$$a-*/$$a-*.tex ; done) +X:=$(shell for a in 1 2 3 4 5 6 8 10 12 ; do echo ../$$a-*/$$a-*.tex ; done) %universe: all ChangeLog -- 2.39.2