Zaawansowane algorytmy i struktury danych/Ćwiczenia 4

From Studia Informatyczne

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.