Pridana kapitola o NP-uplnosti.

[ads2.git] / 8-fft / 8-fft.tex

diff --git a/8-fft/8-fft.tex b/8-fft/8-fft.tex
index 55aac083fbd3e900cbb5b89256e4c46a80d3e200..9f182dccafc5abb446fc8a51fe03934dd49e4d40 100644 (file)
--- a/8-fft/8-fft.tex
+++ b/8-fft/8-fft.tex
@@ -35,8 +35,8 @@ Polynom $P$ rozlo
 
 $P(x) = p_{0}x^{0} + p_{2}x^{2} + \ldots + p_{n-2}x^{n-2} + p_{1}x^{1} + p_{3}x^{3} + \ldots + p_{n-1}x^{n-1}$
 
-$S(x^{2}) = p_{0}x^{0} + p_{2}x^{2} + ... + p_{n - 2}x^{n - 2}$,
-$L(x^{2}) = p_{1}x^{1} + p_{3}x^{3} + ... + p_{n - 1}x^{n - 1}$
+$S(x^{2}) = p_{0}x^{0} + p_{2}x^{2} + \ldots + p_{n - 2}x^{n - 2}$,
+$L(x^{2}) = p_{1}x^{1} + p_{3}x^{3} + \ldots + p_{n - 1}x^{n - 1}$
 
 \>Tak¾e obecnì $P(x) = S(x^{2}) + xL(x^{2})$ a $P(-x) = S(x^{2}) - xL(x^{2})$.
 Jinak øeèeno, vyhodnocování $P(x)$ v $n$ bodech se nám smrskne na vyhodnocení $S(x)$ a $L(x)$ (oba mají polovièní stupeò ne¾ $P(x)$) v $n/2$ bodech (proto¾e $(x_{i})^{2} = (-x_{i})^{2}$).