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





Previous PDF Next PDF



[PDF] 1 Polynômes 2 Algorithme de Horner

Pour représenter les polynômes avec Python on peut utiliser le module numpy évalue le polynôme p au point a (en utilisant l'algorithme d'Horner)



[PDF] POLYNOMES : METHODE DE HORNER - efreidocfr

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 



[PDF] I Méthode Horner

Appliquer cet algorithme avec les polynômes suivants f(x)=4x3 ? 8x2 ? 7x ? 1 Sorties : Q qui est égal à P(x) sous la forme d'un polynôme de Horner



[PDF] La méthode de Hörner - Mathwebfr

1 sept 2018 · Considérons un polynôme P dont une racine est égale à a On schématise l'algorithme de HÖRNER à l'aide d'un tableau :



[PDF] Évaluation dun polynôme - IGM

Schéma de Horner et dérivées Évaluation parall`ele Racines de polynômes Schéma de Horner Algorithme : Soit P(x) un polynôme de degrés n ? n + 1 



[PDF] Chapitre 4 Polynômes : évaluation et interpolation

Algorithme 1: Evaluation de Horner L'algorithme est de complexité linéaire en n Exercice 4 1 1 Programmez l'évaluation d'Horner en Python et en xcas verifiez 



[PDF] Algorithme de Horner compensé en précision finie et applications

Plan de l'exposé 1 Motivations 2 Évaluation précise de polynômes 3 Applications S Graillat (Univ Paris 6) Algorithme de Horner compensé



[PDF] Puissances et polynômes

d] 12 Algorithme de Horner-Ruffini Soit f0 une fonction polynomiale à coefficients entiers On suppose que d0 est un entier tel que



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

Ecrire une fonction qui calcule la somme de deux polynômes Evaluation d'une valeur donnée : O(n) (Algorithme de Horner)



[PDF] La méthode de Hörner - Mathwebfr

1 sept 2018 · Considérons un polynôme P dont une racine est égale à a La méthode de HÖRNER va nous permettre de trouver les coefficients du polynôme Q 



[PDF] POLYNOMES : METHODE DE HORNER - efreidocfr

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 



[PDF] I Méthode Horner

4 Utilisation de cet algorithme Nous avons démontré que P(x)=(x ? x0)Q(x) + P(x0) où Q(x) est le polynôme obtenu avec l'algo- rithme de Hörner



[PDF] Calcul dune image dun polynôme par la méthode de Horner

4 nov 2015 · par la méthode de Horner Soit la polynôme P1 défini par : P1(x) = 3x On souhaite automatiser le procédé par un algorithme



[PDF] Schéma de Hörner - Amiens Python

On admet que l'écriture précédente de P(x) nommée schéma de Hörner se généralise `a un pôlynome de dégré quelconque 1 2 Présentation pratique En pratique 



[PDF] Lalgorithme de Hörner

1 mai 2010 · L'algorithme de Hörner intervient dans de nombreuses situations : 1 évaluation d'un polynôme en un point 2 traduction binaire - décimal



[PDF] Algorithme de Horner compensé en précision finie et applications

Plan de l'exposé 1 Motivations 2 Évaluation précise de polynômes 3 Applications S Graillat (Univ Paris 6) Algorithme de Horner compensé



Méthode Horner PDF Polynôme Mathématiques discrètes - Scribd

Sorties : Q qui est gal P(x) sous la forme dun polynme de Horner Algorithme 1 : Algorithme de Horner n:=size(C)-1; // Le degr du polynome P Q:=C[0];



[PDF] Analyse et implantation dalgorithmes rapides pour lévaluation

16 jui 2006 · La méthode de Horner est l'algorithme le plus classique pour évaluer un polynôme en un point Son comportement numérique sur les nombres 

  • Comment faire la méthode de Horner ?

    qui est appelée méthode de Horner. Un élément de la ligne inférieure s'obtient en multipliant l'élément qui le préc? par le nombre figurant dans la première colonne, en pla?nt le résultat dans sa colonne et en effectuant la somme de deux premiers nombres de la colonne.

  • Comment utiliser la méthode Horner ?

    La méthode de Horner consiste à combiner les deux itérations précédentes en une seule en effectuant le calcul comme suit : . Le nombre de produits est alors réduit à n et l'on peut montrer que ce nombre est minimal : il n'est pas possible d'évaluer une fonction polynomiale en moins de n produits en toute généralité.

  • Comment évaluer un polynôme ?

    La méthode de Horner est l'algorithme le plus classique pour évaluer un polynôme en un point. Son comportement numérique, sur les nombres flottants en tenant compte des erreurs d'ar- rondi, est relativement bien compris, et il s'av`ere qu'en termes de précision, ce schéma semble satisfaisant.16 jui. 2006
  • Cette méthode permet de calculer l'image d'un polynôme P en un point x o x_o xo. En outre, elle permet d'obtenir la division euclidienne de P ( x ) P(x) P(x) par ( x ? x o ) (x-x_o) (x?xo), utile pour la factorisation des polynômes.
[PDF] Algorithmes efficaces pour les grands nombres et polynômes : Partie 2

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
[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