Zaawansowane algorytmy i struktury danych/Ćwiczenia 4

Zadanie 1 (Obliczanie wartości wielomianu w $n$ punktach)

Zaproponuj algorytm obliczający wartość wielomianu stopnia $n$ w $n$ dowolnych punktach w czasie $O(n\log n^{2})$.

Wskazówka

Pomysłem na rozwiązanie jest sprowadzenie zagadnienia do dwóch mniejszych problemów. Można to zrobić wykorzystując algorytm dzielenia wielomianów. Niech $X=\{x_{0},\ldots ,x_{n-1}\}$ będzie zbiorem punktów w których chcemy obliczyć wartość wielomianu. Dla wielomianu $A(x)$ zdefiniujmy dwa nowe wielomiany:

$A^{[0]}(x)=A(x)\mod \prod _{i=0}^{{\frac {n}{2}}-1}(x-x_{i}),$

$A^{[1]}(x)=A(x)\mod \prod _{i={\frac {n}{2}}}^{n-1}(x-x_{i}),$

wielomiany te są stopnia ${\frac {n}{2}}$ i z własności dzielenia wynika, że

$A(x_{i})=A^{[0]}(x_{i})$ dla $i=0,\ldots ,{\frac {n}{2}}-1$

$A(x_{i})=A^{[1]}(x_{i})$ dla $i={\frac {n}{2}},\ldots ,n-1$

Zadanie 2 (Obliczanie wielomianu interpolacyjnego)

Dla danego zbioru $n$ par $X=\{(x_{0},y_{0}),(x_{1},y_{1}),\ldots ,(x_{n-1},y_{n-1})\}$ takiego, że wszystkie wartości $x_{i}$ są parami różne, znajdź wielomian interpolacyjny.

Wskazówka

Podobnie jak w Zadaniu 1 należy sprowadzić problem do dwóch mniejszych. Najpierw liczymy rekurencyjne wielomian $A^{[0]}(x)$ stopnia ${\frac {n}{2}}$ interpolujący zbiór punktów $X^{[0]}=\{(x_{0},y_{0}),(x_{1},y_{1}),\ldots ,(x_{{\frac {n}{2}}-1},y_{{\frac {n}{2}}-1})\}$. Następnie obliczamy wartości $A^{[0]}(x)$ dla zbioru punktów \{x_{\frac{n}{2}-1,\ldots, x_{n-1}}\}, korzystając z wyników Zadania 1. Musimy teraz skonstruować następujący wielomian:

$P(x)=\prod _{i=0}^{{\frac {n}{2}}-1}(x-x_{i}).$

Ponownie korzystając z wyników Zadania 1, obliczamy wartości $P(x)$ dla zbioru punktów \{x_{\frac{n}{2}-1,\ldots, x_{n-1}}\}. Szukany wielomian skonstruujemy jako:

$A(x)=A^{[0]}(x)+P(x)A^{[1]}(x),$

gdzie $A^{[1]}$ to nieznany wielomian stopnia ${\frac {n}{2}}$. Z konstrukcji wynika, że $A(x)$ jest wielomianem interpolacyjnym dla zbioru $X^{[0]}$. Zauważmy, że aby znaleźć musimy ponownie rozwiązać problem interpolacyjny. Dla $A^{[1]}(x)$ musi zachodzić

$A^{[1]}(x_{i})={\frac {y_{i}-A^{[0]}(x_{i})}{P(x_{i})}}$ dla $i={\frac {n}{2}},\ldots ,n-1$.

Musimy więc teraz ponownie rozwiązać problem rozmiaru ${\frac {n}{2}}$. Ostatecznie dostajemy algorytm o złożoności O(n \log^3 n).

Zadanie 3 (Obliczanie wartości wielomianu dwóch zmiennych)

Dla danych zbiorów $n$ punktów $X=\{x_{0},\ldots ,x_{n-1}\}$ i $Y=\{y_{0},\ldots ,y_{n-1}\}$, oraz wielomianu $A(x,y)$ dwóch zmiennych stopnia $n$, wyznacz wszystkie wartości $A(x_{i},y_{j})$ dla $i,j=0,\ldots ,n-1$.

Wskazówka

Zauważmy, że wielomian $A(x,y)$ jest postaci

$A(x,y)=\sum _{i=0}^{n-1}x^{i}B_{i}(y)$      (1)

gdzie wielomiany $B_{i}(y)$ mają także stopnie $n$. W celu wyznaczenia wartości wielomianu $A(x,y)$ najpierw wyznaczamy dla każdego $B_{i}(y)$ jego wartości w punktach $Y=\{y_{0},\ldots ,y_{n-1}\}$. Zajmuje nam to czas $O(n^{2}\log ^{2}n)$. Wartości te możemy wstawić do (1), otrzymując $n$ wielomianów $x$'a, których wartości musimy policzyć w $n$ punktach. Ponownie zajmuje nam to czas $O(n^{2}\log ^{2}n$.