C20. Machine de Turing - Vecteurs   Corrigé 

Soit un vecteur T[1..N] à valeurs numériques. Trier ce vecteur selon la méthode suivante:

1) Supposer T[1..K] trié (K<N), insérer l'élément T(K+1) dans le sous-vecteur T[1..K+1] à sa bonne position.

2) Faire varier K de 1 à N-1 dans 1)

Soit le polynôme suivant :

P(x) = a0xn + a1xn-1+ .... an.

(i) - Donner 2 façons de représenter le polynôme. L'une en représentant les termes nuls et l'autre sans les représenter.

(ii) - Ecrire les modules suivants:

Dérivé(P, P') : dérivé du polynôme P, résultat dans P',

Valeur(P, X) : valeur de P pour X donné

dans chacune des 2 représentations.

(iii) - Ecrire l'algorithme qui calcule la valeur P(X) pour X donné en utilisant la factorisation de Horner :

P(x) = (...( a0x + a1)x + ... aN-1)x + aN,

dans chacune des 2 représentations.