From 51ad5c462f6f00c67cfe3944023a840fe0c5b8c6 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 7 Jan 2008 10:20:48 +0100 Subject: [PATCH] Opravy drobnych preklepu (s diky Ondrovi Mocnemu). --- 10-prevody/10-prevody.tex | 2 +- 8-fft/8-fft.tex | 6 +++--- 9-geom/9-geom.tex | 10 +++++----- 3 files changed, 9 insertions(+), 9 deletions(-) diff --git a/10-prevody/10-prevody.tex b/10-prevody/10-prevody.tex index b4fc61b..53abdb2 100644 --- a/10-prevody/10-prevody.tex +++ b/10-prevody/10-prevody.tex @@ -62,7 +62,7 @@ $$ \phi(x, y, \ldots) = (x \lor \lnot y \lor \ldots) \land (\ldots\lor\ldots\lor \s{Definice:} 3-SAT je takový SAT, kde ka¾dá klauzule obsahuje nejvý¹e tøi literály. \s{Pøevod 3-SAT na SAT:} -Platí identita, 3-SAT splòuje vlastnosti SATu, proto 3-SAT = SAT (3-SAT je alespoò tak tì¾ký, jako SAT) +Platí identita, 3-SAT splòuje vlastnosti SATu, proto 3-SAT = SAT (3-SAT je alespoò tak tì¾ký jako SAT) \s {Pøevod SAT na 3-SAT:} Musíme formuli pøevést tak, abychom neporu¹ili splnitelnost. diff --git a/8-fft/8-fft.tex b/8-fft/8-fft.tex index 9f182dc..8df8e23 100644 --- a/8-fft/8-fft.tex +++ b/8-fft/8-fft.tex @@ -26,7 +26,7 @@ D \>Je asi vidìt, ¾e klíèové jsou kroky 2 a 4. Vybrání bodù jistì stihneme pohodlnì v~lineárním èase a vynásobení samotných hodnot té¾ (máme $2n+2$ bodù a $C(x_{k}) = A(x_{k}) \cdot B(x_{k}), k = 0,1,2, \ldots , 2n+1$, tak¾e na to nepotøebujeme více ne¾ $2n+2$ násobení). -Celý trik spoèívá v~chytrém vybrání onìch bodù, ve kterých budeme polynomy vyhodnocovat. Je na to potøeba vìdìt pár zajímavostí o~komplexních èíslech, na stránce Matrina Mar¹e jsou k dispozici slajdy, zde to bude zapsáno o~trochu struènìji. +Celý trik spoèívá v~chytrém vybrání onìch bodù, ve kterých budeme polynomy vyhodnocovat. Je na to potøeba vìdìt pár zajímavostí o~komplexních èíslech, na stránce Matrina Mare¹e jsou k dispozici slajdy, zde to bude zapsáno o~trochu struènìji. \ss{Vyhodnocení polynomu metodou rozdìl a panuj (algoritmus FFT):} Mìjme polynom $P$ øádu $n$ a chceme jej vyhodnotit v $n$ bodech. Vybereme si body tak, aby byly spárované, èili $\pm x_{0}, \pm x_{1}, \ldots , \pm x_{n/2-1} $. To nám výpoèet urychlí, proto¾e pak se druhé mocniny $x_{i}$ shodují s~druhými mocninami $-x_{i}$. @@ -75,14 +75,14 @@ Te Máme tedy algoritmus, který \uv{pøevede} koeficienty polynomu na hodnoty tohoto polynomu v~námi zadaných bodech. Ale potøebujeme také algoritmus, který doká¾e reprezentaci polynomu pomocí hodnot pøevést zpìt na koeficienty polynomu. Tedy nìjaký inverzní algoitmus. -Definuje me si algoritmus DFT, která vyu¾ívá maticovou reprezentaci a s~jeho¾ pomocí získáme hledaný algoritmus. +Definujeme si algoritmus DFT, která vyu¾ívá maticovou reprezentaci a s~jeho¾ pomocí získáme hledaný algoritmus. \s{Definice:} \>{\I Diskretní Fourierova transformace} $(DFT)$ je funkce $f: { {\bb C} ^n} \rightarrow { {\bb C} ^n}$, kde $y=f(x) \equiv \forall j \ y_{j} = \sum \limits ^{n-1}_{k=0} x_{k} . \omega ^{jk}$. \s{Poznámka:} -Vezmeme polynom, který má $x_{kj}$ jako koeficienty a vyhodnotíme ho v~bodì $\omega ^{j} [y_{j} = x(\omega^{j})] \Rightarrow {f}$ je linearní $\Rightarrow$ mù¾eme napsat $f(x) = \Omega_{x} ,\ \Omega _{jk} =\omega ^{jk}$, kde $\Omega$ je matice. +Vezmeme polynom, který má $x_{kj}$ jako koeficienty a vyhodnotíme ho v~bodì $\omega ^{j} [y_{j} = x(\omega^{j})] \Rightarrow {f}$ je linearní $\Rightarrow$ mù¾eme napsat $f(x) = \Omega x ,\ \Omega _{jk} =\omega ^{jk}$, kde $\Omega$ je matice. \s{Jak najít inverzní matici?} Víme, ¾e $\Omega =\Omega ^{T}$ proto¾e $\omega ^{jk} = \omega ^{kj}$. diff --git a/9-geom/9-geom.tex b/9-geom/9-geom.tex index c91adbd..6ca2f60 100644 --- a/9-geom/9-geom.tex +++ b/9-geom/9-geom.tex @@ -8,7 +8,7 @@ Budeme se tedy zab \h{Hledání konvexního obalu} Ptáte se o co pùjde? Zkusme si to pøiblí¾it na problému ledních medvìdù :) -{\I Lední medvìdi si po dlouhé dobì zmapovaly vody severního moøe a zjistili pøesnì místa, kde se nacházejí jejich oblíbené ryby. No a proto¾e to jsou medvìdi chytøí tak se rozhodli v¹echny tyto rybky pochytat najednou do jedné veliké sítì. A problém, který tady mají je takovýto: Jaký nejmen¹í obvod mù¾e mít taková sí», aby se dovnitø ve¹ly je¹tì v¹echny rybky?!} +{\I Lední medvìdi si po dlouhé dobì zmapovali vody severního moøe a zjistili pøesnì místa, kde se nacházejí jejich oblíbené ryby. No a proto¾e to jsou medvìdi chytøí, tak se rozhodli v¹echny tyto rybky pochytat najednou do jedné veliké sítì. A problém, který tady mají, je takovýto: Jaký nejmen¹í obvod mù¾e mít taková sí», aby se dovnitø ve¹ly je¹tì v¹echny rybky?!} Neboli budeme øe¹it, jak nìjakou zadanou mno¾inu bodù v~rovinì obalit co nejkrat¹í uzavøenou køivkou, do které by se je¹tì v¹echny body ve¹ly. @@ -73,7 +73,7 @@ Set \h{Voroného diagramy} -Pøed tím, ne¾ vás vystra¹ím nìjakou definicí, si øekneme, co jsi pod tímto, na první pohled ne zøejmým pojmem, pøedstavit. Mìjme mno¾inu teèek T rozmístìných náhodnì po papíru. Ke ka¾dému bodu nakreslíme okraje tak, aby vniklá plo¹ka obsahovala body, které jsou nejblí¾e právì té na¹í vybrané teèce. Samozøejmì "sousední" teèky budou mít tyto hranice spoleèné. Výsledkem na¹eho dlouhého sna¾ení pak bude právì Voroného diagram. V dal¹ích odstavcích se budeme zajímat o to, jak takový útvar správnì popsat, jak ho sestrojit a jaké datové struktury k tomu pou¾ít. +Pøed tím, ne¾ vás vystra¹ím nìjakou definicí, si øekneme, co si pod tímto, na první pohled ne zøejmým pojmem, pøedstavit. Mìjme mno¾inu teèek $T$ rozmístìných náhodnì po papíru. Ke ka¾dému bodu nakreslíme okraje tak, aby vniklá plo¹ka obsahovala body, které jsou nejblí¾e právì té na¹í vybrané teèce. Samozøejmì "sousední" teèky budou mít tyto hranice spoleèné. Výsledkem na¹eho dlouhého sna¾ení pak bude právì Voroného diagram. V dal¹ích odstavcích se budeme zajímat o to, jak takový útvar správnì popsat, jak ho sestrojit a jaké datové struktury k tomu pou¾ít. \s{Definice:} Voronoi diagram pro koneènou mno¾inu $M = \{m_1, \dots, m_n\} \in {\bb R}^2$ míst je systém mno¾in $1..M_n$ takových, ¾e pro v¹echny $i$ a $j$ a pro v¹echny $x \in M_i$ je vzdálenost $x$ a $m_i$ men¹í nebo rovna vzdálenosti $x$ a $m_j$ a zároveò sjednocení $M_i$ pøes v¹echna $i$ je celý prostor ${\bb R}^2$, neboli: @@ -83,7 +83,7 @@ Voron \s{Pozorování:} \itemize\ibull -\:Pro v¹echny $i$ je $M_i$ ohranièena konvexní lomenou èarou, tak¾e oblasti mají tvar konvexních mnohoúhelníkù, ale je mo¾né, ¾e jsou oteveøené do nekneèna. +\:Pro v¹echny $i$ je $M_i$ ohranièena konvexní lomenou èarou, tak¾e oblasti mají tvar konvexních mnohoúhelníkù, ale je mo¾né, ¾e jsou oteveøené do nekoneèna. \:Pro ka¾dou hranu $h$ ve Voroného diagramu existuje $i$ a $j$ takové, ¾e kdy¾ $x \in H$, pak vzdálenost $d(x,m_i) = d(x,m_j)$. Øekneme, ¾e vrchol je takové místo, kde se potkávají alespoò dvì hrany. @@ -178,9 +178,9 @@ sou \s{Slo¾itost:} Poèet místních událostí je roven $n$ a poèet kru¾nicových událostí není vìt¹í ne¾ $n$ (s ka¾dou místní událostí zanikne kru¾nicová), neboli velikost $P$ není vìt¹í -ne¾ $2n$ a tedy je v¾dy lineární. Zároveò velikost $H$ není vìt¹í ne¾ $2n$, +ne¾ $2n$, a tedy je v¾dy lineární. Zároveò velikost $H$ není vìt¹í ne¾ $2n$, proto¾e aèkoliv~poèet místních událostí je $n$, tak v~$H$ je záznam pro ka¾dou -trojici a tedy v~$H$ je maximálnì $2n$ událostí najednou. Zbývá nám tedy zjistit +trojici, a tedy v~$H$ je maximálnì $2n$ událostí najednou. Zbývá nám tedy zjistit velikost diagramu $D$, ale ten se urèitì vejde do $\O(n)$ pamìti. Pokud tedy shrneme v¹echny na¹e odhady, pak èasová slo¾itost algoritmu je -- 2.39.2