Informatyka MIMUW

Listy na przykładzie wielomianów

Celem tego laboratorium jest przećwiczenie operacji na listach.
Środkiem do tego celu będą operacje na wielomianach symbolicznych.

Wielomiany zwykłe

Wielomiany reprezentujemy jako listę współczynników (typu float) od końca,
np. lista [3.; 5.; 7.] oznacza wielomian $7x^2 + 5x + 3$.

Zanim przystąpimy do dalszego ciągu należy zdecydować, czy lista może być pusta, czy może kończyć się zerem itp.
Po podjęciu decyzji należy ją zapisać w komentarzu do definicji typu oraz się jej trzymać, tzn.:

• jeśli na coś pozwalamy, wszystkie funkcje powinny na to pozwalać (czyli muszą dobrze działać dla danych mających to coś);
• jeśli na coś nie pozwalamy, na wyjściu ze wszystkich funkcji nie mogą pojawić się dane mające to coś.

Należy zaimplementować następujące rzeczy:

 
      type wielomian = ... 
 
      val oblicz : wielomian -> float -> float 
      (** [oblicz w x] oblicza wartość wielomianu [w] w punkcie [x] *) 
 
      val suma : wielomian -> wielomian -> wielomian 
      (** Suma wielomianów *) 
 
      val iloczyn : wielomian -> wielomian -> wielomian 
      (** Iloczyn wielomianów *) 
 
      val pochodna : wielomian -> wielomian 
      (** Pochodna wielomianu *) 
 
      val stopien : wielomian -> int 
      (** Zwraca stopień wielomianu (czyli najwyższą potęgę argumentu, przy której wykładnik jest różny od 0.) *) 
 
      val calka : wielomian -> wielomian 
      (** Calka wielomianu. [calka w] ma wyraz wolny równy 0. *) 
 

Dobrze by było napisać też kilka generatorów większych wielomianów, np. jed n zwraca
$x^n + x^{n-1} + \dots + 1$, jed_zer n zwraca $x^{2n} + x^{2n-2} + \dots + x^2 + 1$ itp.

Należy zwrócić uwagę na złożoność operacji oraz czy implementacja jest ogonowa, czy nie
(o ile ma to wpływ na złożoność pamięciową) i zapisać te spostrzeżenia w komentarzu.

Wielomiany rzadkie

Wielomiany rzadkie, jak sama nazwa wskazuje, mają tylko niektóre współczynniki różne od zera, np. $x^{1000} + 5x^{50} + 2x^{10} + 1$.
Ponieważ szkoda byłoby miejsca na przechowywanie takich wielomianów w sposób przedstawiony powyżej, będziemy reprezentować
je jako listę par (wykładnik,współczynnik) posortowaną wg rosnących wykładników.
Nasz przykładowy wielomian reprezentowany będzie przez [(0,1.); (10,2.); (50,5.); (1000;1.)].
Dla tej reprezentacji należy zaimplementować osobny zestaw narzędzi, składający się z definicji typu:

 
      type rzadki = ...
 

i tych samych funkcji co powyżej, przy czym do wszystkich nazw należy dołączyć sufiks _rz (np. oblicz_rz),
a we wszystkich typach należy zastąpić wielomian przez rzadki.
W tym zadaniu również należy najpierw zastanowić się, czy (niektóre) współczynniki mogą być równe 0., jak
reprezentowany jest wielomian stale równy zero itp.

Konwersje

Należy zaimplementować funkcje konwertujące wielomiany zwykłe na rzadkie i z powrotem:

 
      val rozrzedz : wielomian -> rzadki 
      (** Konwertuje wielomian do postaci rzadkiej usuwając wszystkie współczynniki równe 0. *) 
 
      val zagesc : rzadki -> wielomian 
      (** Kowertuje wielomian do postaci zwyklej dodajac (o ile trzeba) wyrazy o współczynnikach równych 0. *) 
 

Dla ambitnych/znudzonych: Obliczanie miejsc zerowych

Do powyższych zestawów funkcji operujących na wielomianach dopisać funkcję przybliżającą miejsca zerowe wielomianu
(funkcja ta powinna zwracać listę wartości typu float).
Wskazówka: jak mają się miejsca zerowe wielomianu do miejsc zerowych jego pochodnej?