[PDF] Algorithmes efficaces pour les grands nombres et polynômes

Méthode Horner - Free

4 Utilisation de cet algorithme Nous avons démontré que P(x) = (x−x 0)Q(x)+P(x 0) où Q(x) est le polynôme obtenu avec l’algo- rithme de Hörner Si x 0 est une racine de P alors On trouve p(x

Algorithme de Horner (II) - SFR

Algorithme de Horner (II) Objectif: division euclidienne d’un polynôme par (X-z) Données: Les coefficients du polynôme, donnés sous la forme d’un tableau P indexé de 0 à n Description de l’algorithme La division euclidienne s’écrit : P(X)=(X-z)*Q(X)+P(z) L’algorithme de Horner permet de calculer P(z) par les

POLYNOMES : METHODE DE HORNER

void derivePolynome(Polynome P, Polynome * Pprim); void integralPolynome(Polynome P, Polynome * Pintegral); L'algorithme de la méthode Horner est implanté de la manière suivante pour un polynôme représenté par un tableau pour ses coefficients et un entier pour son degré: long double Horner(long double P[], long n, long double x) {long i;

Algorithme de Horner (I)

Algorithme de Horner (I) Objectif: calculer les valeurs d’un polynôme Exemple pratique: nombreux en mathématiques Données: Les coefficients du polynôme, donnés sous la forme d’un tableau P indexé de 0 à n Description de l’algorithme L’évaluation « naïve » d’un polynôme de degré n en un point x

Polynômes - Lycée privé Sainte-Geneviève

p roots ou roots(p) donne les racines (dans C ) de p p(a) ou polyval(p,a) évalue le polynôme p au point a (en utilisant l'algorithme d'Horner) 2 Algorithme de Horner Soient a 2K et P = Xn k=0 b kX k On souhaite calculer P(a) Naïvement, on calcule les puissances de a, on multiplie les résultats par les coe cients b k puis on additionne

TP Informatique 14 - Algorithme de Hörner 1 Calcul intuitif

de R 10[X] arp la liste de ses 11 e cientsoc (éventuellement les derniers étant nuls si le degré est < 10) 1 Programmer l'algorithme de Hörner en urbTo-Pascal Il faudra pour cela : créer un type POLYNOME pour représenter les polynômes de R 10[X] demander à l'utilisateur de rentrer le polynôme P et le réel x a cher la aleurv de P(x) 2

Algorithmes efficaces pour les grands nombres et polynômes

Entre deux points de coordonnees :´ (x0;p(x0))et (x1;p(x1))distincts on ne peut tracer qu’une et une seule droite qui passe par ces deux points Une droite = un polynomeˆ Une droite est au fait un polynome de degrˆ e 1 de la forme :´ p(x)=a0 +a1:x Il est tres facile de calculer` a0 et a1 si on connaˆıt les deux points (x0;p(x0))et (x1;p

3 Division polynomiale - Vaud

La disposition du schéma de Horner est la suivante : 3 −8 0 10 5 6 −4 −8 4 3 −2 −4 2 9 ·2 ·2 ·2 ·2 + + + + Les nombres de la première ligne sont les coefficients du dividende Le facteur de multiplication, ici 2, correspond au zéro du diviseur x −2 La dernière ligne fournit les coefficients du quotient 3x3 − 2x2 − 4x

NALYSE D ALGORITHMES Cas moyen vs Pire des cas: Temps d

Entrée Algorithme T(n) Sortie Analyse d’algorithmes 2 2 Cas moyen vs Pire des cas: Temps d’exécution d’un algorithme • Un algorithme peut être plus performant avec certains ensembles de données qu’avec d’autres, • Trouver le cas moyen peut s’avérer difficile, alors les algorithmes sont mesurés typiquement selon la

Interpolation pour l’ingénieur Méthodes numériques

3 0 0 2 0 4 0 6 0 8 1 1 2 1 4 1 6 1 8-4-3-2-1 0 1 2 Approximation de fonctions • Il faut se restreindre à une famille de fonctions – polynômes, – exponentielles,

[PDF] modele quantique de bohr

[PDF] polynome scindé a racines simples

[PDF] modèle quantique de l'atome wikipedia

[PDF] modèle quantique de l'atome exercices corrigés

[PDF] modele planetaire schrodinger

[PDF] modèle plum pudding

[PDF] modèle atomique bohr

[PDF] modele atomique rutherford bohr

[PDF] modèle atomique simplifié potassium

[PDF] modèle atomique simplifié lithium

[PDF] modèle atomique simplifié calcium

[PDF] périodicité des propriétés

[PDF] modèle atomique simplifié hydrogène

[PDF] notation de lewis

[PDF] protocole infirmier medecine du travail

Algorithmes efficaces pour les grands nombres et

polyn

ˆomes : Partie 2

Salem BENFERHAT

Centre de Recherche en Informatique de Lens (CRIL-CNRS) email : benferhat@cril.fr 1/61

Ce que nous avons vu dans la premi

`ere partie ... Gr ˆace`a la d´ecomposition d"un grand nombre et grˆace`a une simple reformulation du calcul du produit, nous avons un algorithme en :

O(n1:584)

2/61

Peut-on encore mieux faire?

3/61

Retour sur les polyn

ˆomes

4/61 Polyn

ˆomesD

´efinitionp(x)=n

i=0a ixi=a0+a1x+a2x2+a3x3+⋯+anxn; o `u : aisont des r´eels (positifs ou n´egatifs ou nuls) anest diff´erent de z´ero nest appel´e le degr´e du polynˆomep(x).Ce que l"on a vu Evaluation dep(x)lorsquex=x0, avec un algorithme efficace deO(n)5/61 Polyn

ˆomesD

´efinitionp(x)=n

i=0a ixi=a0+a1x+a2x2+a3x3+⋯+anxn; o `u : aisont des r´eels (positifs ou n´egatifs ou nuls) anest diff´erent de z´ero nest appel´e le degr´e du polynˆomep(x).Ce que l"on a vu Evaluation dep(x)lorsquex=x0, avec un algorithme efficace deO(n)5/61 Repr

´esentatation d"un polynˆomeTableau

Un polyn

ˆome :

p(x)=n i=0a ixi=a0+a1x+a2x2+a3x3+⋯+anxn; sera tout simplement repr

´esent´e par un tableau de r´eels :a

0a 1a

2::::a

n-1a n012::::n-1n 6/61

Addition et produit de deux polyn

ˆomesExercice

Ecrire une fonction qui calcule la somme de deux polynˆomes. Ecrire une fonction qui calcule le produit de deux polynˆomes.7/61

Addition de deux polyn

ˆomes

1

2double*addition(doubleA[], double B[], int N)

3{

4inti;

5double*res=(double*) malloc ((N+1)*sizeof(double));

6for(i=0; i<=N; i++)

7{

8res[i]=A[i]+B[i];

9}

10returnres;

11} 8/61

Produit de deux polyn

ˆomes

1

2double*multiplicaion(doubleA[], double B[], int N)

3{

4inti, j;

5double*res=(double*) calloc ((2*(N+1))*sizeof(double), 0);

6for(i=0; i<=N; i++)

7{

8for(j=0; j<=N; j++)

9res[i+j]=res[i+j]+(A[i]*B[j]);

10}

11returnres;

12} 9/61

Complexit

´e sur les op´erations de baseR

´ecapitulatifs•

Addition :O(n)

Multiplication :O(n2)

Evaluation d"une valeur donn´ee :O(n)(Algorithme de Horner).10/61

Une autre repr

´esentation

des polyn

ˆomes

a base de points 11/61

Commenc¸ons par le point

D ´efinition d"un type enregistrement qui repr´esente un point : typdef struct float abscisse; float ordonn

´ee;

}point; 12/61

La droite

Une droite

Entre deux points de coordonn

´ees :(x0;p(x0))et(x1;p(x1))distincts

on ne peut tracer qu"une et une seule droite qui passe par ces deux points.Une droite = un polyn

ˆomeUne droite est au fait un polyn

ˆome de degr´e 1 de la forme :

p(x)=a0+a1:xIl est tr `es facile de calculera0eta1si on connaˆıt les deux points (x0;p(x0))et(x1;p(x1)).13/61

La droite

Une droite

Entre deux points de coordonn

´ees :(x0;p(x0))et(x1;p(x1))distincts

on ne peut tracer qu"une et une seule droite qui passe par ces deux points.Une droite = un polyn

ˆomeUne droite est au fait un polyn

ˆome de degr´e 1 de la forme :

p(x)=a0+a1:xIl est tr `es facile de calculera0eta1si on connaˆıt les deux points (x0;p(x0))et(x1;p(x1)).13/61

La droite

Une droite

Entre deux points de coordonn

´ees :(x0;p(x0))et(x1;p(x1))distincts

on ne peut tracer qu"une et une seule droite qui passe par ces deux points.Une droite = un polyn

ˆomeUne droite est au fait un polyn

ˆome de degr´e 1 de la forme :

p(x)=a0+a1:xIl est tr `es facile de calculera0eta1si on connaˆıt les deux points (x0;p(x0))et(x1;p(x1)).13/61

Avec trois points ...

Un peu plus loin qu"une droite

Avec trois points de coordonn

´ees :(x0;p(x0)),(x1;p(x1))et

(x2;p(x2))distincts on peut repr´esenter un (et un seul) polynˆome de degr

´e 2 de la forme :

p(x)=a0+a1:x+a2:x2Il est tr `es facile de calculera0,a1eta2si on connaˆıt les trois points : nous disposons de trois ´equations pour trois variables inconnues.14/61

Avec trois points ...

Un peu plus loin qu"une droite

Avec trois points de coordonn

´ees :(x0;p(x0)),(x1;p(x1))et

(x2;p(x2))distincts on peut repr´esenter un (et un seul) polynˆome de degr

´e 2 de la forme :

p(x)=a0+a1:x+a2:x2Il est tr `es facile de calculera0,a1eta2si on connaˆıt les trois points : nous disposons de trois ´equations pour trois variables inconnues.14/61

Avec n+1 points ...

Polyn ˆome de degr´e nAvec (n+1) points de coordonn

´ees :(x0;p(x0)), ...,(xn+1;p(xn+1))

distincts on peut repr ´esenter un (et un seul) polynˆome de degr´e n de la forme : p(x)=a0+a1:x+:::+an:xnIl est facile de calculera0, ...,ansi on connaˆıt lesn+1 points : nous disposons den+1´equations pourn+1 variables inconnues.15/61

Avec n+1 points ...

Polyn ˆome de degr´e nAvec (n+1) points de coordonn

´ees :(x0;p(x0)), ...,(xn+1;p(xn+1))

distincts on peut repr ´esenter un (et un seul) polynˆome de degr´e n de la forme : p(x)=a0+a1:x+:::+an:xnIl est facile de calculera0, ...,ansi on connaˆıt lesn+1 points : nous disposons den+1´equations pourn+1 variables inconnues.15/61 Premi `ere conclusion...Polyn

ˆome de degr´e nUn polyn

ˆome de degr´enpeut-ˆetre repr´esent´e : Soit par un vecteur de degr´es (a0, ...,an), c"est-`a-dire p(x)=a0+a1:x+:::+an:xn• Soit par (n+1) points de coordonn´ees distinctes : (x0;p(x0));:::;(xn+1;p(xn+1))• Ces deux repr´esentations sont´equivalentes16/61 Premi `ere conclusion...Polyn

ˆome de degr´e nUn polyn

ˆome de degr´enpeut-ˆetre repr´esent´e : Soit par un vecteur de degr´es (a0, ...,an), c"est-`a-dire p(x)=a0+a1:x+:::+an:xn• Soit par (n+1) points de coordonn´ees distinctes : (x0;p(x0));:::;(xn+1;p(xn+1))• Ces deux repr´esentations sont´equivalentes16/61 Premi `ere conclusion...Polyn

ˆome de degr´e nUn polyn

ˆome de degr´enpeut-ˆetre repr´esent´e : Soit par un vecteur de degr´es (a0, ...,an), c"est-`a-dire p(x)=a0+a1:x+:::+an:xn• Soit par (n+1) points de coordonn´ees distinctes : (x0;p(x0));:::;(xn+1;p(xn+1))• Ces deux repr´esentations sont´equivalentes16/61 Deuxi `eme conclusion...Impact sur la complexit

´e ...•

Comme les deux repr´esentations sont´equivalentes, si nous disposons d"algorithmes efficaces pour la repr

´esentation`a partir

de coordonn ´ees distinctes alors nous disposerons´egalement d"algorithmes efficaces pour les polyn

ˆomes repr´esent´es par des

vecteurs de degr

´es•

Enfin presque c¸a ... Car les transformations doivent rester efficaces ... 17/61 Deuxi `eme conclusion...Impact sur la complexit

´e ...•

Comme les deux repr´esentations sont´equivalentes, si nous disposons d"algorithmes efficaces pour la repr

´esentation`a partir

de coordonn ´ees distinctes alors nous disposerons´egalement d"algorithmes efficaces pour les polyn

ˆomes repr´esent´es par des

vecteurs de degr

´es•

Enfin presque c¸a ... Car les transformations doivent rester efficaces ... 17/61

Addition de polyn

ˆomes`a base de points ...

Supposons que les polyn

ˆomes sont repr´esent´es`a base de points (coordonn ´ees). Soitp1(x)etp2(x)deux polynˆomes repr´esent´es par (x0;p1(x0));:::;(xn+1;p1(xn+1))et (x0;p2(x0));:::;(xn+1;p2(xn+1))Addition de deux polyn ˆomesIl se fait enO(n). En effet, le polynˆomep1(x)+p2(x)sera tout simplement repr ´esent´e par :(x0;p1(x0)+p2(x0));:::;(xn+1;p1(xn+1)+p2(xn+1))18/61

Addition de polyn

ˆomes`a base de points ...

Supposons que les polyn

ˆomes sont repr´esent´es`a base de points (coordonn ´ees). Soitp1(x)etp2(x)deux polynˆomes repr´esent´es par (x0;p1(x0));:::;(xn+1;p1(xn+1))et (x0;p2(x0));:::;(xn+1;p2(xn+1))Addition de deux polyn ˆomesIl se fait enO(n). En effet, le polynˆomep1(x)+p2(x)sera tout simplement repr ´esent´e par :(x0;p1(x0)+p2(x0));:::;(xn+1;p1(xn+1)+p2(xn+1))18/61

Addition de polyn

ˆomes`a base de points ...

Supposons que les polyn

ˆomes sont repr´esent´es`a base de points (coordonn ´ees). Soitp1(x)etp2(x)deux polynˆomes repr´esent´es par (x0;p1(x0));:::;(xn+1;p1(xn+1))et (x0;p2(x0));:::;(xn+1;p2(xn+1))Addition de deux polyn ˆomesIl se fait enO(n). En effet, le polynˆomep1(x)+p2(x)sera tout simplement repr ´esent´e par :(x0;p1(x0)+p2(x0));:::;(xn+1;p1(xn+1)+p2(xn+1))18/61

Addition de polyn

ˆomes`a base de points ...

Supposons que les polyn

ˆomes sont repr´esent´es`a base de points (coordonn ´ees). Soitp1(x)etp2(x)deux polynˆomes repr´esent´es par (x0;p1(x0));:::;(xn+1;p1(xn+1))et (x0;p2(x0));:::;(xn+1;p2(xn+1))Addition de deux polyn ˆomesIl se fait enO(n). En effet, le polynˆomep1(x)+p2(x)sera tout simplement repr ´esent´e par :(x0;p1(x0)+p2(x0));:::;(xn+1;p1(xn+1)+p2(xn+1))18/61

Produit de polyn

ˆomes`a base de points ...

Supposons que les polyn

ˆomes sont repr´esent´es`a base de points (coordonn ´ees). Soitp1(x)etp2(x)deux polynˆomes repr´esent´es par (x0;p1(x0));:::;(xn+1;p1(xn+1)) et (x0;p2(x0));:::;(xn+1;p2(xn+1))Produit de deux polyn ˆomesIl se fait enO(n). En effet, le polynˆomep1(x)?p2(x)sera tout simplement repr

´esent´e par :

Produit de polyn

ˆomes`a base de points ...

Supposons que les polyn

ˆomes sont repr´esent´es`a base de points (coordonn ´ees). Soitp1(x)etp2(x)deux polynˆomes repr´esent´es par (x0;p1(x0));:::;(xn+1;p1(xn+1)) et (x0;p2(x0));:::;(xn+1;p2(xn+1))Produit de deux polyn ˆomesIl se fait enO(n). En effet, le polynˆomep1(x)?p2(x)sera tout simplement repr

´esent´e par :

Evaluationt de polyn

ˆomes`a base de points ...

Supposons que les polyn

ˆomes sont repr´esent´es`a base de points (coordonn ´ees). Soitp1(x)un polynˆome repr´esent´e par (x0;p1(x0));:::;(xn+1;p1(xn+1))Evaluer en x=a Aie ... Calculerp1(a)n´ecessite d"abord de transformer la repr ´esentation`a base de points vers une repr´esentation`a base de coefficients, puis appliquer l"algorithme de Horner• La transformation na¨ıve d"une repr´esentation`a base de points vers une repr ´esentation`a base de coefficients se fait enO(n2)20/61

Evaluationt de polyn

ˆomes`a base de points ...

Supposons que les polyn

ˆomes sont repr´esent´es`a base de points (coordonn ´ees). Soitp1(x)un polynˆome repr´esent´e par (x0;p1(x0));:::;(xn+1;p1(xn+1))Evaluer en x=a Aie ... Calculerp1(a)n´ecessite d"abord de transformer la repr ´esentation`a base de points vers une repr´esentation`a base de coefficients, puis appliquer l"algorithme de Horner• La transformation na¨ıve d"une repr´esentation`a base de points vers une repr ´esentation`a base de coefficients se fait enO(n2)20/61

Evaluationt de polyn

ˆomes`a base de points ...

Supposons que les polyn

ˆomes sont repr´esent´es`a base de points (coordonn ´ees). Soitp1(x)un polynˆome repr´esent´e par (x0;p1(x0));:::;(xn+1;p1(xn+1))Evaluer en x=a Aie ... Calculerp1(a)n´ecessite d"abord de transformer la repr ´esentation`a base de points vers une repr´esentation`a base de coefficients, puis appliquer l"algorithme de Horner• La transformation na¨ıve d"une repr´esentation`a base de points vers une repr ´esentation`a base de coefficients se fait enO(n2)20/61

Evaluationt de polyn

ˆomes`a base de points ...

Supposons que les polyn

ˆomes sont repr´esent´es`a base de points (coordonn ´ees). Soitp1(x)un polynˆome repr´esent´e par (x0;p1(x0));:::;(xn+1;p1(xn+1))Evaluer en x=aquotesdbs_dbs33.pdfusesText_39