Exercice 7 - Polynômes

Nous représenterons un polynôme $$P(x) = p_0x^n + p_1x^{n-1} + \ldots + p_{n-1}x + p_n = \sum_{i=0}^{n}p_ix^{n-i}$$ de degré $n$ à l'aide d'un tableau $[p_0, p_1, \ldots, p_{n-1}, p_n]$ à $n+1$ éléments. Notez bien que ce tableau est indicé à partir de $0$.

1. Que fait la fonction suivante ?
   
   
   

2. Quelle est la complexité de $mystery$ ?
3. Écrire la procédure $derive([p_0, \ldots, p_n])$ remplaçant $p$ par sa dérivée.
4. Prouver que $$\sum_{i=0}^{k+1}p_ix^{k+1-i} = x\left(\sum_{i=0}^{k}p_ix^{k-i} \right) + p_{k+1}$$
5. Déduire de la relation ci-dessus une fonction $evalue([p_0, \ldots, p_n], x)$ prenant $P$ et $x$ en paramètres, et retournant $P(x)$.
6. Prouver la validité de la fonction d'évaluation, vous utiliserez les questions précédentes.
7. Quelle est la complexité de $evalue$ ?