Zaawansowane algorytmy i struktury danych/Ćwiczenia 4: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 4: Linia 4:
 
w <math>n</math> dowolnych punktach w czasie <math>O(n \log n^2)</math>.
 
w <math>n</math> dowolnych punktach w czasie <math>O(n \log n^2)</math>.
  
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> '''Wskazówka'''  
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka'''  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
  
Linia 39: Linia 39:
 
Dla danego zbioru <math>n</math> par <math>X = \{(x_0, y_0), (x_1, y_1), \ldots, (x_{n-1},y_{n-1})\}</math> takiego, że wszystkie wartości <math>x_i</math> są parami różne, znajdź wielomian interpolacyjny.
 
Dla danego zbioru <math>n</math> par <math>X = \{(x_0, y_0), (x_1, y_1), \ldots, (x_{n-1},y_{n-1})\}</math> takiego, że wszystkie wartości <math>x_i</math> są parami różne, znajdź wielomian interpolacyjny.
  
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> '''Wskazówka'''  
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka'''  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
  
Linia 77: Linia 77:
 
dla <math>i,j = 0,\ldots, n-1</math>.
 
dla <math>i,j = 0,\ldots, n-1</math>.
  
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> '''Wskazówka'''  
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka'''  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
 
Zauważmy, że wielomian <math>A(x,y)</math> jest postaci
 
Zauważmy, że wielomian <math>A(x,y)</math> jest postaci

Wersja z 14:30, 28 wrz 2006

Zadanie 1 (Obliczanie wartości wielomianu w punktach)

Zaproponuj algorytm obliczający wartość wielomianu stopnia w dowolnych punktach w czasie .

Wskazówka

Zadanie 2 (Obliczanie wielomianu interpolacyjnego)

Dla danego zbioru par takiego, że wszystkie wartości są parami różne, znajdź wielomian interpolacyjny.

Wskazówka

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

Dla danych zbiorów punktów i , oraz wielomianu dwóch zmiennych stopnia , wyznacz wszystkie wartości dla .

Wskazówka