Le forum de XCAS

Je commence un peu à fatiguer donc je vais m'arrêter là pour aujourd'hui, mais je vais peut-être poster des choses sur le forum dans la semaine (en reprenant un peu les deux problèmes).

A bientôt,
Thomas

Juste pour être sûr de ne pas avoir fait d'erreur, mon programme est le suivant : (où les notations sont les mêmes que l'énoncer, et j'ai rajouté un paramètre "p" pour le nombre d'itérations de Newton que je fais) fonction Racines(P,n,N,x,p) local xn,j,k,v,h,Q,Pt,t,l; h:=1/N ; Q:=x^n-1; v:=seq(evalf...

J'ai un petit soucis avec mon algorithme : je pars des racines de Q, mais en itérant les méthodes de Newton je converge parfois vers la même racine de P... Je vais y réfléchir un peu plus pour le modifier et je t'enverrai ça quand j'aurai amélioré mon algo.

Tu préfères qu'on fasse des illustrations sur Xcas de la méthode de division euclidienne, ou plutôt de passer aux racines de polynômes ?

Petite question concernant la complexité du calcul de c : comme on n'est pas intéressés par tous les coefficients de c (mais seulement ceux de degré 0 à (t-1)), est-ce que l'on garde la méthode naïve de multiplication de polynômes (pour ne calculer que les coefficients intéressants du produit b*b_t)...

On commence par regarder la division euclidienne. Je suis en vocal avec Anthony au fait.

Si j'arrive à trouver du temps ce weekend j'essaierai de préparer un texte et je vous tiendrai au courant. Sinon les exercices me conviennent très bien (et me semblent tout aussi utiles pour l'oral d'option).

Pour FIbonacci, on calcule une expression explicite des termes de la suite par résolution de l'équation caractéristique qui est : X^2-X-1=0. On trouve deux racines, dont une seule (qui s'avère être le nombre d'or) est plus grande que 1 en valeur absolue, et on a donc un équivalent de la forme : x_n ...

Après on peut améliorer le calcul de l'inverse avec la méthode de Strassen...

Oui pour le PGCD j'avais fait sur Fp (par GF(p,n)). Donc il faut reprendre le résultat pour ensuite calculer le PGCD de polynômes sur GF(p,n).

Pour calculer l'inverse d'une matrice, on procède par pivot de Gauss. A chaque étape de la descente, on calcul un inverse dans GF(p,n) (à savoir l'inverse du pivot). Si la matrice est de taille k*k, on a donc O(k*n^2) comme coût pour les inverses. Les coûts des autres opérations sont en O(k*n) (il s...

Le calcul d'inverse se fait par l'algorithme d'Euclide, puisque l'inverse d'un polynôme Q dans (F_p[X]/P) est donné par l'identité de Bezout appliquée à P et Q. Donc on a un coût en O(n^2) pour calculer l'inverse d'un élément de GF(p,n) (puisque c'est l'algorithme d'Euclide appliqué à P et Q, qui so...

Pour calculer le PGCD de deux polynômes, on répète la division euclidienne. Il faut calculer le nombre d'étape (c'est-à-dire le nombre de divisions euclidiennes à faire). Si on note R_n,Q_n le reste et le quotient obtenu à l'étape n, le coût de l'étape n est : (deg(Q_n)+1)*(deg(R_{n+1})+1) On utilis...

Pour le 4), le calcul de la division euclidienne du polynôme N par le polynôme M, tous deux à coefficients dans F_p, de degrés respectifs n,m (avec n\geq m) est : (n-m+1)*m où on considère que le calcul d'un inverse dans F_p est en tant constant, qu'on peut multiplier sans coût un polynôme par une p...

Petite question pour 3 et 4 : on considère que le corps fini GF(p,n) est représenté à l'aide d'un polynôme irréductible de degré n sur F_p ?
Si c'est le cas on devrait donc traiter en même temps les deux questions (et ça vaut même le coup de faire la 4 avant, non ?).