From 7571be795efaf5c473317b1ea0a85dd117a422c3 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 16 Jan 2012 00:18:02 +0100 Subject: [PATCH] Prechod na nova makra --- 2-toky/2-toky.tex | 4 +-- 3-dinic/3-dinic.tex | 10 ++----- 4-goldberg/4-goldberg.tex | 4 +-- 5-hradla/5-hradla.tex | 4 +-- 6-geom/6-geom.tex | 13 ++------ 7-fft/7-fft.tex | 62 +++++++++++++++++++++++---------------- 6 files changed, 47 insertions(+), 50 deletions(-) diff --git a/2-toky/2-toky.tex b/2-toky/2-toky.tex index aef1092..2345b84 100644 --- a/2-toky/2-toky.tex +++ b/2-toky/2-toky.tex @@ -133,9 +133,7 @@ Nenasycen Budeme tedy opakovanì hledat nenasycené cesty a tok po~nich zlep¹ovat. Postupnì doká¾eme, ¾e tento postup je koneèný a v~ka¾dé síti najde maximální tok. -\s{Algoritmus (Fordùv-Fulkersonùv)} - -\algo +\algo{FordFulkerson} \:$f \leftarrow$ libovolný tok, napø. v¹ude nulový. \:Dokud existuje nenasycená cesta~$P$ ze $z$ do $s$, opakujeme: \::$\varepsilon \leftarrow \min \{r(e) \mid e \in P\}$. diff --git a/3-dinic/3-dinic.tex b/3-dinic/3-dinic.tex index f639261..eac80f0 100644 --- a/3-dinic/3-dinic.tex +++ b/3-dinic/3-dinic.tex @@ -99,9 +99,7 @@ Proto se takov \figure{dinic-cistasit.eps}{Proèi¹tìná sí» rozdìlená do~vrstev}{0.4\hsize} -\s{Dinicùv algoritmus:} - -\algo +\algo{Dinic} \:$f \leftarrow \hbox{nulový tok.}$ \:Opakujeme: \::Sestrojíme sí» rezerv~$R$ a~sma¾eme hrany s~nulovou rezervou. @@ -112,9 +110,7 @@ Proto se takov \::Zlep¹íme tok~$f$ pomocí~$g$. \endalgo -\s{Èi¹tìní sítì} podrobnìji: - -\algo +\proc{Èi¹tìníSítì} \:Rozdìlíme vrcholy do~vrstev podle vzdálenosti od~$z$. \:Odstraníme vrstvy za~$s$ (tedy vrcholy vzdálenìj¹í ne¾~$\ell$). \:Odstraníme hrany do~pøedchozích vrstev a hrany uvnitø vrstev. @@ -147,7 +143,7 @@ Cel \nobreak -\algo +\proc{BlokujícíTok} \:$g \leftarrow$ nulový tok. \:Dokud v~$R$ existuje orientovaná cesta~$P$ ze~$z$ do~$s$, opakujeme: \::$\varepsilon \leftarrow \min_{e \in P} \left(r(e) - g(e)\right)$. diff --git a/4-goldberg/4-goldberg.tex b/4-goldberg/4-goldberg.tex index 8096cea..4326605 100644 --- a/4-goldberg/4-goldberg.tex +++ b/4-goldberg/4-goldberg.tex @@ -67,9 +67,7 @@ ne Získáme tak následující algoritmus: -\s{Algoritmus (Goldbergùv):} - -\algo +\algo{Goldberg} \:Nastavíme poèáteèní vý¹ky (zdroj ve~vý¹ce~$n$, ostatní ve~vý¹ce~0): \::$h(z)\leftarrow n$ \::$h(v)\leftarrow 0$ pro v¹echny $v\ne z$ diff --git a/5-hradla/5-hradla.tex b/5-hradla/5-hradla.tex index b096802..e9a949f 100644 --- a/5-hradla/5-hradla.tex +++ b/5-hradla/5-hradla.tex @@ -314,12 +314,12 @@ $\left< n/2,3/4\cdot n \right>$ dostane $c_{3/4\cdot n}$ atd. Obecnì v~$i$-tém kroku pou¾ívá chování blokù velikosti $2^{\log n - i}$. \s{Sèítací sí»} tedy bude vypadat takto: -\algo +\numlist\ndotted \:$\Theta(1)$ hladin výpoètu chování blokù velikosti~1. \:$\Theta(\log n)$ hladin poèítajících chování v¹ech pøirozených blokù. \:$\Theta(\log n)$ hladin dopoèítávajících pøenosy \uv{zahu¹»ováním}. \:$\Theta(1)$ hladin na samotné seètení: $\forall i: z_i = x_i \oplus y_i \oplus c_i$. -\endalgo +\endlist \figure{deleni_bloku.eps}{Výpoèet pøenosu}{2.5in} diff --git a/6-geom/6-geom.tex b/6-geom/6-geom.tex index 909d4f4..b70e9d4 100644 --- a/6-geom/6-geom.tex +++ b/6-geom/6-geom.tex @@ -83,10 +83,7 @@ $k$-t nejprve body z~obálky odebírat a $k$-tý bod pøidáme a¾ ve chvíli, kdy jeho pøidání smìr zatáèení neporu¹í. -\s{Algoritmus:} - -\algo - +\algo{KonvexníObal} \:Setøídíme body podle $x$-ové souøadnice, oznaème body $b_1, \ldots, b_n$. \:Vlo¾íme do horní a dolní obálky bod $b_1$: $H = D = (b_1)$. \:Pro ka¾dý dal¹í bod $b = b_2,\ldots,b_n$: @@ -95,8 +92,7 @@ p \::::Odebereme poslední bod $h_k$ z~obálky $H$. \:::Pøidáme bod $b$ do obálky $H$. \::Symetricky pøepoèteme dolní obálku (s orientací doprava). -\: Výsledný obal je tvoøen body v~obálkách $H$ a $D$. - +\:Výsledný obal je tvoøen body v~obálkách $H$ a $D$. \endalgo Rozebereme si èasovou slo¾itost algoritmu. Setøídit body podle $x$-ové souøadnice doká¾eme v~èase $\O(n \log n)$. Pøidání dal¹ího bodu do obálek @@ -244,10 +240,7 @@ beztak sma Algoritmus pro hledání prùnikù úseèek pak funguje následovnì: -\s{Algoritmus:} - -\algo - +\algo{Prùseèíky} \:$P \leftarrow \emptyset$. \:Do $K$ vlo¾íme zaèátky a konce v¹ech úseèek. \:Dokud $K \ne \emptyset$: diff --git a/7-fft/7-fft.tex b/7-fft/7-fft.tex index f453bf8..32941f9 100644 --- a/7-fft/7-fft.tex +++ b/7-fft/7-fft.tex @@ -100,8 +100,7 @@ po~slo ¾e souèin má vy¹¹í stupeò ne¾ jednotliví èinitelé, tak¾e si potøebujeme poøídit dostateèný poèet bodù. -\s{Algoritmus pro násobení polynomù:} -\algo +\algo{NásobeníPolynomù} \:Jsou dány polynomy $P$ a~$Q$ velikosti~$n$, urèené svými koeficienty. Bez újmy na obecnosti pøedpokládejme, ¾e horních $n/2$ koeficientù je u~obou polynomù nulových, tak¾e souèin $R=P\cdot Q$ bude také polynom @@ -282,8 +281,7 @@ $\Theta(n\log n)$ pro vyhodnocen s~vektory jejich koeficientù èi hodnot. Tomuto algoritmu se øíká FFT, vzápìtí prozradíme, proè. -\s{Algoritmus FFT:} -\algo +\algo{FFT} \algin Èíslo~$n=2^k$, primitivní $n$-tá odmocnina z~jednièky~$\omega$ a vektor $(p_0,\ldots,p_{n-1})$ koeficientù polynomu~$P$. \:Pokud $n=1$, polo¾íme $y_0\leftarrow p_0$ a skonèíme. @@ -418,7 +416,7 @@ Obvod z~p èím¾ získáme elegantní nerekurzivní algoritmus pro výpoèet FFT v~èase $\Theta(n\log n)$ a prostoru $\Theta(n)$: -\algo +\algo{FFT2} \algin $x_0,\ldots,x_{n-1}$ \:Pro $k=0,\ldots,n-1$ polo¾íme $y_k\= x_{r(k)}$, kde $r$ je funkce bitového zrcadlení. \:Pøedpoèítáme tabulku hodnot $\omega^0,\omega^1,\ldots,\omega^{n-1}$. @@ -463,25 +461,34 @@ V nejsou zatí¾eny zaokrouhlovacími chybami (komplexní odmocniny z~jednièky mají obì slo¾ky iracionální). To se hodí napøíklad ve~zmiòovaných algoritmech na násobení velkých èísel. -\h{Cvièení} +\exercises -\itemize\ibull -\:O~jakých vlastnostech vektoru vypovídá nultý a $(n/2)$-tý koeficient jeho - Fourierova obrazu (výsledku Fourierovy transformace)? -\:Spoèítejte Fourierovy obrazy následujících vektorù z~${\bb C}^n$: +\ex{O~jakých vlastnostech vektoru vypovídá nultý a $(n/2)$-tý koeficient jeho +Fourierova obrazu (výsledku Fourierovy transformace)? +} + +\ex{Spoèítejte Fourierovy obrazy následujících vektorù z~${\bb C}^n$: \itemize\ibull \:$(x,\ldots,x)$ \:$(1,-1,1,-1,\ldots,1,-1)$ \:$(\omega^0,\omega^1,\omega^2,\ldots,\omega^{n-1})$ \:$(\omega^0,\omega^2,\omega^4,\ldots,\omega^{2n-2})$ \endlist -\:Roz¹íøením výsledkù z~pøedchozího cvièení najdìte pro ka¾dé~$j$ vektor, jeho¾ - Fourierova transformace má na $j$-tém místì jednièku a v¹ude jinde nuly. Z~toho lze pøímo - sestrojit inverzní transformaci. -\:Uka¾te, ¾e je-li $\bf x$ reálný vektor z~${\bb R}^n$, je jeho Fourierova transformace ${\bf y}={\cal F}({\bf x})$ - {\I antisymetrická:} ${\bf y}_j = \overline{{\bf y}_{n-j}}$ pro v¹echna~$j$. -\:Podobnì uka¾te, ¾e Fourierova transformace ka¾dého antisymetrického vektoru je reálná. -\:Uva¾ujme reálnou funkci~$f$ definovanou na intervalu $[0,2\pi)$. Pokud její +} + +\ex{Roz¹íøením výsledkù z~pøedchozího cvièení najdìte pro ka¾dé~$j$ vektor, jeho¾ +Fourierova transformace má na $j$-tém místì jednièku a v¹ude jinde nuly. Z~toho lze pøímo +sestrojit inverzní transformaci. +} + +\ex{Uka¾te, ¾e je-li $\bf x$ reálný vektor z~${\bb R}^n$, je jeho Fourierova transformace ${\bf y}={\cal F}({\bf x})$ +{\I antisymetrická:} ${\bf y}_j = \overline{{\bf y}_{n-j}}$ pro v¹echna~$j$. +} + +\ex{Podobnì uka¾te, ¾e Fourierova transformace ka¾dého antisymetrického vektoru je reálná. +} + +\exx{Uva¾ujme reálnou funkci~$f$ definovanou na intervalu $[0,2\pi)$. Pokud její hodnoty {\I navzorkujeme} v~$n$ pravidelnì rozmístìných bodech, získáme vektor ${\bf f}\in {\bb R}^n$ o~slo¾kách ${\bf f}_j = f(2\pi j/n)$. Jak vypadá Fourierova transformace tohoto vektoru pro následující funkce? @@ -490,17 +497,22 @@ iracion \:$\cos kx$ \:$\sin kx$ \endlist - Nápovìda: sinus a cosinus mù¾ete zapsat jako lineární kombinaci dvou komplexních exponenciál. -\:Pomocí pøedchozího cvièení doka¾te, ¾e libovolnou reálnou funkci na $[0,2\pi)$ - existuje lineární kombinace funkcí $\sin kx$ a $\cos kx$, která pøi vzorkování - v~$n$ bodech není od zadané funkce rozli¹itelná. +} + +\hint{Sinus a cosinus mù¾ete zapsat jako lineární kombinaci dvou komplexních exponenciál.} - Pøesnìji øeèeno, pro ka¾dý vektor~${\bf f}\in {\bb R}^n$ existují vektory ${\bf a},{\bf b}\in {\bb R}^n$ - takové, ¾e platí: +\exx{Pomocí pøedchozího cvièení doka¾te, ¾e libovolnou reálnou funkci na $[0,2\pi)$ +existuje lineární kombinace funkcí $\sin kx$ a $\cos kx$, která pøi vzorkování +v~$n$ bodech není od zadané funkce rozli¹itelná. + +Pøesnìji øeèeno, pro ka¾dý vektor~${\bf f}\in {\bb R}^n$ existují vektory ${\bf a},{\bf b}\in {\bb R}^n$ +takové, ¾e platí: $$ {\bf f}_j = \sum_{k=0}^{n-1} {\bf a}_k \sin {2jk\pi \over n} + {\bf b}_k \cos {2jk\pi \over n}. $$ - Koeficienty $a_k$ a $b_k$ lze pøítom snadno získat z~Fourierova obrazu vektoru~${\bf f}$. -\endlist +Koeficienty $a_k$ a $b_k$ lze pøítom snadno získat z~Fourierova obrazu vektoru~${\bf f}$. +} + +\endexercises \bye -- 2.39.5