Forum de mathématiques - Bibm@th.net

agrega_sarrachles_tif

Membre

Inscription : 26-01-2022

Messages : 16

algorithme d'euclide polynome, complexité entre autres

Bonjour, dans le cadre d'une préparation à l'agregation de mathématique, plus précisément de l'option C "algèbre et calcul formel", je dois commenter un texte de mathématique, càd le présenter et faire qq démo.
Voici le texte en question : https://drive.google.com/file/d/1iwUpye … sp=sharing

Dans le premier théorème, il est dit que la complexité de l'algorithme d'euclide est en $\mathcal{O}(n^3m\delta^2log(nA))$ (je précise que $m$ est le degré du polynôme de plus bas degré, même si ça n'est pas mentionné dans le texte) opérations sur les mots. Déjà je suis pas sûr de ce que ça signifie (quels opérations sur quels mots?), mais j'ai l'impression qu'il y a quelque chose qui cloche et je sais pas si c'est moi ou le texte, donc j'aimerai votre avis:

D'abord, si je cherche à évaluer par moi même la complexité de l'algo d'euclide pour les polynômes , je trouve un $\mathcal{O}(n^2)$, je ne vais pas détailler comment je fais mais en gros je trouve qu'il n'y a pas plus de $2n$ multiplication nombre*polynôme , $2n$ soustraction de polynômes et $n$ division de polynôme par nombre, les polynômes étant au plus de degré $n$, ça fait une borne sup de $5n^2$ opérations.

$\delta$ est l'écart maximum entre deux restes consécutifs, je ne comprends pas comment cette donnée a autant d'impact sur la complexité. Par exemple, si $\delta = 10$ et $n = 1000$, le nombre de division euclidienne est entre 100 et 990... c'est pas une fourchette c'est un rateau! On est sensé avoir un facteur 100 entre le nombre de calculs lorsque $\delta = 1$ et $\delta = 10$...

Je passe sûrement à côté de quelquechose, et je me demande si c'est pas:
- la definition d'opération sur les mots que je ne comprends pas bien
- ce que c'est l'algo d'euclide

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 348

Re : algorithme d'euclide polynome, complexité entre autres

Bonjour,

  Je viens de lire le début du texte, qui est très mal écrit (comment peut-on savoir ce que signifie un mot par exemple.....).
J'ai regardé en parallèle la référence citée (Modern Computer Algebra). La complexité est bien, comme tu l'expliques, en $O(n\times m)$ opérations... Je ne comprends pas plus que toi!

F.