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





Previous PDF Next PDF



A remark on a Note by Laguerre

Sa méthode repose sur l'assertion suivante où f est un polynôme de degré n ? 1 : « Il est clair que l'équation f (x) = 0 a également toutes ses racines réelles 



Chapitre 3 - Racines dun polynôme

Pour n = 0 un polynôme constant non nul poss`ede évidemment zéro racine. Soit n fixé



Equation générale de degré n

Théorème Le groupe de Galois G du polynôme f est isomorphe au groupe symé- trique Sn. Démonstration Il suffit de prouver que G est le groupe S. ¦. A§ de toute 



Chapitre 12 : Polynômes

07-Feb-2014 du polynôme P l'entier n degré de P (souvent noté d?(P))



ÉQUATIONS POLYNOMIALES

Partie 2 : Équations de degré n dans ?. 1) Définition. Définition : Une fonction polynôme (ou polynôme) est une fonction de ? dans ? de la.



Cours de mathématiques - Exo7

On continue avec un théorème fondamental de l'algèbre : « Tout polynôme de degré n admet n racines complexes. » On termine avec les fractions rationnelles 





Palindrome-Polynomials with Roots on the Unit Circle

of even degree n with real coefficients ?0?1



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

n est appelé le degré du polynôme p(x). Ce que l'on a vu. Evaluation de p(x) lorsque x = x0 avec un algorithme efficace de O(n).



The Divergence of Lagrange Interpolation for lxl* at Equidistant Nodes

at most n coinciding with f at the nodes of the (n+1)th row of X. One of Sur la limitation des valeurs d'un polynome Pn(x) de degre n sur tout un.



[PDF] Polynômes - Exo7 - Cours de mathématiques

Tout polynôme à coefficients complexes de degré n 1 a au moins une racine dans C Il admet exactement n racines si on compte chaque racine avec multiplicité



[PDF] Chapitre 3 Les polynômes - Institut de Mathématiques de Toulouse

L'entier d ? N s'appelle le degré de P et se note deg(P) Les polynômes de degré zéro sont dits constants ceux de la forme cdXd (avec cd ? K)



[PDF] 13 Polynômes - LAMA - Univ Savoie

On appelle degré d'un polynôme non nul A = (a0 a1 · · · ) le plus grand entier n tel que an = 0 Le coefficient an correspondant est appelé coefficient 



[PDF] Les polynômes

a est appelé le coefficient et n est appelé le degré du monôme Exemples : • 3x est un monôme de la variable x de degré 1 et de coefficient 3 •



[PDF] Chapitre 3 - Racines dun polynôme

Proposition 3 6 Un polynôme non nul de degré n de K[X] a au plus n racines distinctes Démonstration : Par récurrence sur n Pour n = 0 un polynôme constant 



[PDF] Polynômes

Exercice 1 1 Calculer par récurrence (1 + X)(1 + X2)(1 + X4) ··· (1 + X2n ) Exercice 1 2 Si P est un polynôme de degré n `a coefficients dans K et c un 



[PDF] Chapitre 12 : Polynômes - Normale Sup

7 fév 2014 · du polynôme P l'entier n degré de P (souvent noté d?(P)) le coefficient correspondant an est le coefficient dominant de P Si ce coefficient 



[PDF] Polynômes et fractions rationnelles - Résumé de résultats

Un polynôme P à coefficients dans K est une « suite (an)n?N indexée sur Si P n'est pas nul son degré deg(P) est le plus grand entier d tel que ad = 0



[PDF] Equation générale de degré n

Théorème Le groupe de Galois G du polynôme f est isomorphe au groupe symé- trique Sn Démonstration Il suffit de prouver que G est le groupe S ¦ A§ de toute 



[PDF] 3-Polynomes-Courspdf - Optimal Sup Spé

Soit ne N L'ensemble des polynômes à coefficients dans K de degré inférieur ou égal à n est noté K„[X] 3 Algorithme de Horner

  • Comment montrer qu'un polynôme est de degré n ?

    On suppose que pour tout polynôme B tel que deg(B) < n (n ? N? fixé) et pour tout polynôme A non nul, il existe Q, R ? K[X] tels que B = AQ + R avec deg(R) < deg(A). Soit B un polynôme de degré n. Si deg(A) > n = deg(B) alors l'écriture B = A × 0 + B permet de conclure.

  • Comment trouver les racines d'un polynôme de degré n ?

    Recherche de racine(s) et signe d'un polynôme : Un polynôme du second degré P(x) = ax² + bx + c admet au plus deux racines. Le nombre exact de ses racines est déterminé par le signe d'un expression notée ? qu'on appelle le discriminant. ? = b² - 4ac.

  • Comment trouver le degré d'un polynôme ?

    Pour des polynômes à deux variables ou plus, le degré d'un terme est la somme des exposants des variables dans le terme ; le degré (parfois appelé degré total) du polynôme est à nouveau le maximum des degrés de tous les termes du polynôme. Par exemple, le polynôme x2y2 + 3x3 + 4y est de degré 4, le degré du terme x2y2.
  • Corollaire 1 : Un polynôme est nul si et seulement si tous ses coefficients sont nuls.
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 ...

quotesdbs_dbs33.pdfusesText_39
[PDF] définition de la mobilisation

[PDF] factoriser un polynome de degré n

[PDF] polynome degré 2

[PDF] phyllotaxie spiralée

[PDF] définition société civile organisée

[PDF] comment expliquer l'abstention électorale

[PDF] mobilisation des civils première guerre mondiale

[PDF] implication des civils premiere guerre mondiale

[PDF] les civils victimes de la premiere guerre mondiale

[PDF] les conditions de vie des civils pendant la seconde guerre mondiale

[PDF] le fibroscope pour voir ? l'intérieur du corps correction

[PDF] exercice corrigé fibre optique ? saut d'indice

[PDF] composition géographie roissy

[PDF] l inégale intégration des territoires ? la mondialisation

[PDF] les mobilités humaines transnationales