Co może być ciekawego w wielomianach?

O wielomianach uczymy się w szkole dość dużo. Nie za bardzo wiadomo, po co aż tyle. Na wykładzie pokażę niezwykle ważne zastosowanie wielomianów. Aby z niego praktycznie korzystać, trzeba umieć wyznaczać wartości wielomianu w wielu punktach. To może być kosztowne, jeśli punktów jest naprawdę dużo. Pokażę kilka algorytmów, wśród których będzie prawdziwa perełka, która zainicjowała całą informatykę. Ciekawe, kto ze słuchaczy potrafi przebić ten algorytm w liczbie mnożeń, które trzeba wykonać, żeby dla przykładu obliczyć milion wartości dowolnego wielomianu dziesiątego stopnia - co jedną milionową w przedziale [0..1)?

Informacje o prowadzącym
Piotr Chrząstowski
Docent w Instytucie Informatyki Uniwersytetu Warszawskiego.