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,\dots ,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,\dots ,\frac{n}{2}-1$

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

Zadanie 2 (Obliczanie wielomianu interpolacyjnego)

Dla danego zbioru $n$ par $X=\{(x_0,y_0),(x_1,y_1),\dots ,(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),\dots ,(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źć ${\displaystyle }$ 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},\dots ,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,\dots ,x_{n-1}\}$ i $Y=\{y_0,\dots ,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,\dots ,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,\dots ,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$.