Xcas

Pourquoi utiliser Xcas à l'épreuve de modélisation de l'agrégation?

• Certaines fonctionnalités de Xcas sont plus faciles à utiliser ou plus puissantes que celles des autres logiciels de calcul formel, en particulier pour l'option C (par exemple en arithmétique, Xcas donne accès aux fonctionnalités du logiciel PARI/GP).
• Si vous connaissez bien maple (ou mupad ou la TI89/92), Xcas est un équivalent libre (donc gratuit) que vous devriez pouvoir utiliser sans trop avoir à changer vos habitudes (bien entendu il y a des différences avec les logiciels cités ci-dessus, mais dans les cas favorables, des feuilles de calcul maple s'ouvrent et s'exécutent à l'identique dans Xcas).
• La documentation de Xcas est entièrement rédigée en français. Elle comprend de plus un manuel d'algorithmique et des exemples faciles à adapter pour la présentation sur ordinateur en particulier pour l'option C (dans les manuels ou depuis le menu Exemples).
• Xcas affiche les zones de parenthèses, crochets ou accolades correspondantes, ce qui facilite la recherche d'erreurs de parenthèsage par exemple. De plus, dans un niveau de programme, les mots clefs du language sont affichés en couleur.
• Xcas possède un débuggueur interactif permettant l'exécution d'un programme ligne à ligne et la visualisation des variables, facilitant la mise au point d'une fonction bugguée.

Retour à la barre de navigation

Télechargement de Giac/Xcas

• la version Linux (debian sarge ou etch, le système d'exploitation le jour de l'oral), la version Xcas du site de l'agrégation sera mise à jour à la rentrée 2007.
• vous pouvez aussi charger sur le site de Francois Boisson une image CD permettant d'avoir sur un PC sans aucune installation la même configuration qu'à l'oral (naturellement ne sont présents que les dogiciels pouvant être redistribués, en particulier Xcas, mais aussi Pari, Maxima, Axiom, Scilab). Vous pouvez d'ailleurs recopier le CD sur une clef USB et avoir la configuration de l'agregation sur cette clef.
  N.B.: pour accéder à l'aide de Xcas sur la version de la clef, aller dans le menu Cfg->navigateur et indiquer dillo (ceci devrait etre corrigé dans la version 2.2 de la clef).
• Vous pouvez aussi l'installer en version pour Windows ou Mac OS X.4. Ces versions sont identiques à la version Linux à quelques détails près (il manque quelques fonctionnalités sous Windows et Mac OS X).

Retour à la barre de navigation

Option C (algèbre et calcul formel)

C1: représentations

• Entiers
  Les entiers longs utilisent la librairie GMP 4, les algorithmes utilisés y sont documentés (cf. aussi la doc en ligne gmp*info en tapant info gmp en ligne de commande ou Ctrl-H I dans emacs puis chercher gmp, puis aller dans Algorithms). Par exemple, diverses méthodes de multiplication rapide sont implémentéees (Karatsuba, Toom3, FFT).
• Flottants
  La base de représentation des flottants utilisée par Xcas est 2 (et non 10 comme maple, c'est d'ailleurs pour cette raison que les calculs en flottants sont relativements lents en maple, sauf si on utilise evalhf qui force l'utilisation de l'arithmétique flottante du processeur). On peut le vérifier en calculant 0.3-3*0.1. Le programme suivant, tiré de V. Lefèvre et P.Zimmermann, permet de déterminer la base utilisée pour la représentation des flottants (fonctionne avec maple et avec xcas en mode maple)
  Base:=proc()
  local A,B;
  A:=1.0; B:=1.0;
  while evalf(evalf(A+1.0)-A)-1.0=0.0 do A:=2*A; od;
  while evalf(evalf(A+B)-A)-B<>0 do B:=B+1; od;
  B;
  end;
  Si Digits est plus petit que 15, les objets nouvellement créés utilisent l'arithmétique hardware (double du standard IEEE en base 2, 52 bits de mantisse, 11 bits d'exposant, 1 bit de signe), Digits controle seulement l'affichage des flottants. Sinon, ce sont des flottants multiprécision utilisant la librairie MPFR. Digits qui est un nombre de chiffres significatifs en base 10 est alors arrondi en un nombre de bits en base 2. Certains calculs numériques utilisant la GSL (Gnu Scientific Library), par exemple l'algèbre linéaire numérique, convertissent les flottants longs en flottants hardware (avec évidemment des pertes de précision).
  Référence pour les erreurs: le livre de Demailly
• Polynômes en une variable
  On peut manipuler les polynômes comme dans maple (cf ici), mais aussi directement en représentation dense à une variable. La représentation est la liste des coefficients donnés par ordre décroissant, par exemple [1,0,3] pour le polynôme x^2+3. En cas de risque de confusion, remplacer le délimiteur ouvrant [ par poly1[. Les instructions arithmétiques de base s'appliquent sur les listes représentant des polynômes, par exemple rem([1,3,4,2],[1,1,1]) ou poly1[1,2.3]*poly1[1,1].
  On passe de la représentation symbolique à la représentation liste et inversement avec les fonctions symb2poly et poly2symb
  La multiplication des polynômes en une variable est implémentée par Karatsuba lorsque les arguments sont de degré supérieur à 17. Exemples: multiplication par Karatsuba et par FFT sur C ou par FFT sur Z/nZ
• Polynôme en plusieurs variables
  On peut utiliser une représentation récursive à partir des polynômes denses en une variable ci-dessus, mais ce type est mal adapté s'il y a beaucoup de coefficients nuls. Xcas utilise une représentation creuse, une liste de monomes dont on stocke le coefficient et un vecteur d'indices entiers (correspondant aux puissances des variables de ce monome). Le produit de polynômes est implementé en utilisant des tables de hachage pour regrouper dans la somme les termes de meme degré et lorsque cela est possible le vecteur d'indices entiers est compressé en un unique entier hardware (long ou long long, cf. les fichiers header /usr/include/giac/poly.h et monomial.h pour les programmeurs C++). Cf. R. Fateman pour une discussion sur les produits de polynômes à plusieurs variables.
• Z/nZ
  Xcas utilise les entiers modulo un premier petit dans de très nombreux algorithmes (par exemple le PGCD de polynôme par méthode modulaire). En mode xcas, on utilise le signe % (comme en C) pour indiquer un nombre de Z/nZ, par exemple 3 % 5. En mode maple, on utilise la même syntaxe qu'en maple (forme inerte de l'instruction suivie de mod). Xcas utilise la représentation symétrique des entiers modulo un nombre premier (on renvoie x % n avec x compris entre -n/2 et n/2), qui est la plus utile lorsqu'on veut reconstruire un entier dont on connait une majoration en valeur absolue à partir de son représentant modulo n (pour n assez grand).
  Pour obtenir un entier y == x % n à partir de x, son représentant modulo n en mode xcas, on utilise x % 0.
• Corps finis
  Xcas utilise la représentation polynomiale pour les corps finis. Cette session Xcas explique comment construire un polynome irréductible primitif.
  Pour définir un corps fini, on utilise l'instruction GF par exemple G:=GF(2,8,['a','G']) (GF pour Galois Field, ayant ici 2^8 éléments, G désigne le nom du corps et a la variable utilisée pour l'écriture polynomiale des éléments de G). Xcas renvoie alors la caractéristique du corps et un polynôme primitif irréductible. Les éléments du corps sont des restes de division euclidienne (modulo le nombre premier) de polynômes par le polynôme irréductible.
  On peut créer un élément du corps en tapant G(polynôme), par exemple g:=G(a) (c'est ici un générateur du corps car le polynôme minimal est primitif). On peut ensuite appliquer toutes les opérations arithmétiques sur g, par exemple calculer g^255 pour vérifier qu'il vaut 1, ou g^(255/3), g^(255/5) et g^(255/17) qui ne valent pas 1 (on vérifie ainsi que les puissances de g engendrent bien tout le corps).
  Pour vérifier qu'un polynôme est irréductible modulo un premier, utiliser en mode maple, Factor((x^8+x^6+x^5+x^4+1)) mod 2, en mode xcas factor((x^8+x^6+x^5+x^4+1) % 2).

  Pour travailler avec des polynômes à coefficients dans ce corps fini, vous pouvez utiliser la représentation symbolique habituelle ou dense expliquée ci-dessus. Par exemple rem(g*x^3+g^5*x^2+g*x,g*x+g^2) ou rem([g,g^5,g,0],[g,g^2]) calcule le reste d'un polynôme de degré 3 par un polynôme de degre 1 à coefficients dans le corps G (donnés par ordre décroissant dans le 2ème cas).

  La version actuelle de Xcas ne permet pas de factoriser un polynôme à coefficients dans un corps de Galois, on peut toutefois utiliser la fonction factorff de PARI, par exemple
  pari("factorff",x^2+a^2,5,a^4+2)
  factorise le polynôme x^2+a^2 modulo 5 où a a pour polynôme minimal a^4+2 (il n'existe pas encore de fonction réalisant de conversion automatique des GF de Xcas vers les arguments de la fonction factorff de PARI). Le résultat est une matrice, dont chaque ligne contient un facteur et sa puissance. Le facteur est un polynôme en x à coefficients dans le corps de Galois représenté polynomialement par un Mod (dont le 2ème argument est le polynôme minimal).

• Utilisation de PARI dans Xcas
  Les instructions de PARI (version 2.3) peuvent être exportées dans Xcas en tapant pari(). Les commandes de PARI sont alors utilisables soit par leur nom PARI, soit en leur ajoutant le préfixe pari_ lorsque le nom existe déjà dans Xcas (par exemple weber(1+i) et pari_gcd(x^2-1,x^3-1)). Une aide succinte sur les commandes de pari est accessible par ?pari_nom_de_commande_pari. Le manuel plus complet de PARI se consulte depuis le menu Aide->Manuels->PARI-GP.
  On peut aussi utiliser les commandes de PARI sans les exporter, en tapant la commande pari( puis le nom de commande pari en chaine de caractères, puis les arguments de la commande pari, par exemple pari("weber",1+i).
  Cette fonctionnalité venant d'être ajoutée, il est probable que certaines fonctions de PARI ne fonctionnent pas si on les appelle de cette façon depuis Xcas (ceci sera amélioré pour la version 0.7 de Xcas).
• Vecteurs, listes et matrices Xcs ne fait pas de différence entre listes et vecteurs, les matrices sont des listes de listes. L'affectation dans une liste, vecteur ou matrice se fait par création d'une copie de l'objet si on utilise := pour l'affectation, ou par référence si on utilise =<.

Retour à la barre de navigation

C2: algorithmes

• Puissance modulaire rapide
  Dans tous les modes, on peut utiliser powmod(a,b,n). En mode maple, on peut utiliser la syntaxe maple a &^ b mod n.
  Le manuel de programmation donne des versions de l'algorithme de puissance rapide comparé avec l'algorithme naif.
• Algorithme d'Euclide étendu
  (dit aussi algorithme de Bézout). La version pour les entiers est iegcd ou iabcuv, pour les polynômes egcd et abcuv.
  Le demi algorithme d'Euclide étendu (permettant par exemple de reconstruire une fraction par son représentant modulo un entier), est codé dans la fonction fracmod. La version polynômiale du demi algorithme d'Euclide est utilisée pour les approximants de Padé (fonction pade).
  Le manuel de programmation donne des versions itératives et récursives de l'algorithme d'Eculide étendu.
• Tri
  La fonction sort de Xcas effectue un tri par ordre croissant, d'une liste ou d'une séquence selon la fonction <. Si le premier argument est une liste, on peut passer en deuxième argument une fonction de tri, par exemple
  sort([[4,2],[3,5],[5,6]], (x,y)-> x[0] > y[0] )
  effectue un tri d'une matrice en utilisant la première composante de chaque ligne. Attention, la fonction de tri doit renvoyer faux en cas d'egalite, il doit s'agir d'un ordre strict faible. Plus precisement, un ordre strict faible est irreflexif (f(x,x) est faux), antisymetrique et transitif, et la relation definie par a R b si et seulement si f(a,b) et f(b,a) sont simultanement faux doit etre une relation d'equivalence (autrement dit f(x,y), f(y,x), f(y,z), f(z,y) faux doit entrainer f(x,z), f(z,x) faux).

  sort de Xcas utilise la fonction sort de la STL (C++ Standard Template Library). La complexité est garantie en O(N log(N)). Une recherche sur google de algorithmes de tri donne d'excellentes références...
  Earlier versions of sort used the quicksort algorithm (C. A. R. Hoare, Comp. J. 5, 1962), using a pivot chosen by median of three (R. C. Singleton, CACM 12, 1969). Quicksort has O(N log(N)) average complexity, but quadratic worst-case complexity. See section 5.2.2 of Knuth for a discussion. (D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching. Addison-Wesley, 1975.) The current implementation of sort, however, uses the introsort algorithm (D. R. Musser, "Introspective Sorting and Selection Algorithms", Software Practice and Experience 27(8):983, 1997.) whose worst case complexity is O(N log(N)). Introsort is very similar to median-of-three quicksort, and is at least as fast as quicksort on average.
  En gros, on combine un quicksort avec choix du pivot median parmi 3, et si le niveau de récursivité est plus grand que k log(n), on passe par exemple au tri tas. Une façon plus simple de trier en temps O(N log(N)) consiste à faire un algorithme récursif (divide and conquer): si la taille de la liste est 0 ou 1 on la laisse inchangée, si c'est 2 on modifie l'ordre si nécessaire, sinon on copie la première moitié que l'on trie (par appel récursif), puis la deuxième moitié que l'on trie (par appel récursif), puis on fusionne les deux listes triées par parcours (un index dans chaque liste, on copie depuis et on avance dans la liste dont l'élément est le plus petit). Il n'est pas évident de tester les temps de calcul de ce type d'algorithme avec un langage interprété d'autant qu'on ne connait pas forcément la facon dont sont implémentés les conteneurs listes (ainsi en Xcas, une affectation de type l[i]:= crée une nouvelle copie de la liste l et a donc un temps d'exécution proportionnel à la taille de la liste, il faut utiliser =< pour affecter par référence). En langage compilé, voici une implémentation (tri de liste d'entiers aléatoires) en C++ fusion et tas.

• Nombres premiers
  Les fonctions isprime et is_prime de Xcas effectuent, par l'intermédiaire de GP-PARI, un test de primalité et non un test de pseudo-primalité (instruction is_pseudoprime) mais Xcas ne renvoie pas de certificat de primalité (contrairement à ce qui est indiqué dans la documentation). Le manuel de programmation donne des exemples de code de tests de pseudo-primalité (Rabin et Miller-Rabin). Vous pouvez aussi pour avoir un certificat de primalité utiliser directement la fonction pari("isprime",) avec en 2ème argument l'entier à tester et en 3ème argument optionnel 0, 1 ou 2 (voir la documentation de PARI). Par exemple
  p:=nextprime(3*10^14)
  calcule le premier pseudo-premier supérieur à 3.10^14, puis
  pari("isprime",p,1)
  calcule un certificat de primalité de Selfridge-Pocklington-Lehmer (Cohen chapitre 8.3 ou Knuth section 4.5), voir aussi cette session. Si on remplace 1 par 2, on effectue le test APRCL (Adleman-Pomerance-Rumely-Cohen-Lenstra). Voici aussi un exemple de programme montrant la méthode de Pollard.
• Factorisation d'entiers
  La factorisation des entiers est faite dans Xcas par appel à GP/PARI et permet en général de factoriser relativement rapidement, par exemple ifactor(2^128+1).
  Voir le manuel de PARI/GP (depuis le menu Aide->Manuels->PARI-GP) pour des détails sur les algorithmes utilisés par PARI, ainsi que Cohen ou Knuth. Cette session illustre la méthode des fractions continues (cf. Knuth pour une implémentation plus efficace).
• RSA
  Les fonctions asc et char permettent de convertir une chaine de caractères en une liste de nombres (le code ASCII des caractères) et réciproquement (comme convert avec l'option bytes en maple). Par ailleurs, le menu Exemples->crypto->rsa.xws donne un exemple de programme de codage RSA et le manuel de programmation fournit de la documentation sur RSA. On peut illustrer graphiquement le choix des valeurs de clefs dans cette session.
  Quelques autres exemples (par Robert Rolland) échange de clefs de Diffie-Hellman, signature ombrée

Retour à la barre de navigation

C3: algèbre linéaire.

• Pivot de Gauss, déterminant
  Xcas utilise par défaut l'algorithme de Gauss-Bareiss (dans rref, det, etc.). Les éléments de matrice sont transformés en fractions rationnelles polynomiales par rapport aux variables (étendues), les relations algébriques entre variables étendues sont ignorées (par exemple entre le cosinus et le sinus d'un angle, vous pouvez utiliser les fonctions de réécriture, en particulier tsimplify, pour écrire une matrice en fonctions de variables étendues algébriquement indépendantes). Le ppcm des dénominateurs est ensuite retiré ligne par ligne, puis la réduction a lieu (réduction de Gauss habituelle mais avec division par le pivot utilisé pour la réduction de la colonne précédent la colonne actuelle).
  L'option rational_det impose l'utilisation de l'algorithme de Gauss (et non Gauss-Bareiss) et n'effectue pas la transformation en fractions rationnelles (ce qui peut créer des problèmes de non reconnaissance de 0 si des variables interviennent).
  L'option keep_pivot de rref n'effectue pas l'opération finale de division de la matrice réduite par le premier coefficient non nul de chaque ligne.
  On peut imposer le calcul du déterminant par l'algorithme de développement selon les mineurs en ajoutant le paramètre minor_det, par exemple det(A,minor_det) donnera des résultats bien plus rapides si A est une matrice avec beaucoup de variables symboliques.
  Les algorithmes de Gauss, de calcul du noyau, etc. sont explicités dans le manuel de programmation.
• Enveloppe convexe, simplexe
  L'instruction convexhull calcule l'enveloppe convexe d'une famille de points. Voici une session Xcas implémentant l'algorithme dit de Graham scan (voir l'explication sur le site de wikipedia en anglais).
  L'algorithme du simplexe est implémenté sous forme matricielle voir la documentation de simplex_reduce.
• Matrices à coefficients entiers
  Les fonctions ihermite et ismith calculent la forme normale de Hermite et de Smith d'une matrice à coefficients entiers. L'algorithme de réduction est expliqué rapidement dans le texte Algèbre linéaire sur les entiers. Le manuel de calcul formel donne un exemple d'application de ihermite au calcul d'une Z-base d'un noyau, voir par exemple Morandi pour l'utilisation de la forme de Smith.
• Codes correcteurs
  La session codelin.xws illustre quelques aspects des codes linéaires. Le menu Exemples->crypto->reed_s.xws donne une session de calcul xcas illustrant les codes correcteurs de Reed-Solomon (rédigé pour le master 2 crypto de Grenoble). Pour les explications, cf. PDF (TeX). Cf. par exemple Demazure pour une introduction plus complète aux codes correcteurs.

Retour à la barre de navigation

C4 Polynômes

• Évaluation
  La fonction horner de Xcas permet d'évaluer un polynôme (symbolique ou liste par ordre décroissant des coefficients) par la méthode de Horner. Voir aussi la session horner.xws de Exemples->poly et le manuel de programmation.
• Interpolation
  La fonction lagrange (ou interp) calcule par la méthode des différences divisées le polynôme d'interpolation de Lagrange.

  La fonction spline calcule des spline naturelle (cf. la doc). Voici comment Xcas la calcule sur un exemple de spline cubique naturelle (donc de degré 3), on se donne 2 listes d'abscisses x0 à xn et d'ordonnées y0 à yn, et deux liste d'inconnues à déterminer z[0], ..., z[n-1] (les coefficients dominants des polynômes sur chaque intervalle) et f la valeur de la dérivée première en x0 (la dérivée seconde est nulle aux extrémités pour une spline naturelle). La spline est donnée en x0 par le polynôme
  P=z[0]*(x-x0)^3+f*(x-x0) + y0 soit [z[0],0,f,y0] en représentation liste avec comme origine x0.
  On change d'origine, ce qui revient à calculer le développement de Taylor de P en x1. Il ne faut pas utiliser la fonction taylor (qui suppose une représentation symbolique des polynômes) mais la fonction ptayl, par exemple si x0=1 et x1=4, ptayl([z[0],0,f,y0],3) ou plusieurs applications de l'algorithme de Horner avec quotient (cf. menu Exemples->poly->horner.xws, la fonction hornerl(l,a) renvoie la valeur du polynôme l en a et le quotient de l par x-a). En répétant Horner avec le quotient précédent on obtiendra les coefficient de (x-a) et de (x-a)^2, ici il faut prendre a=x1-x0). On doit trouver y1 comme valeur si x=x1, ce qui donne une première condition pour le système linéaire. La régularité de la spline en x1 impose qu'elle a le même développement de Taylor au-delà de x1, sauf pour le coefficient dominant qui devient z[1], il suffit donc de changer le premier coefficient dans la liste représentant le polynôme. On change à nouveau d'origine de x1 à x2 (on applique à nouveau hornerl trois fois mais avec a=x2-x1) et on obtient une 2ème équation (la valeur en x2 doit être y2). On continue jusqu'à atteindre xn, où l'on aura comme dans la boucle, l'équation valeur en xn doit être yn, et en plus l'équation dérivée seconde nulle (donc le résultat de la 3ème évaluation de hornerl avec a=xn-xn-1 doit etre nul).
  On obtient ainsi un système de n+1 équations en n+1 inconnues (z[0],..., z[n-1],f), il ne reste alors qu'à le résoudre avec linsolve.
  Références: la doc en ligne de Xcas (Manuel->Algorithmes de calcul formel), le livre de Demailly, sur le web, le chapitre 2 du cours d'Analyse numérique de Ernst Hairer

• Transformée de Fourier discrète
  Xcas implémente uniquement la tranformée de Fourier rapide à coefficients flottants complexes simple précision, via les instructions fft et ifft.

  Exemple (cf. aussi le manuel décrivant la transformée de Fourier discrète, section Où interviennent ces sommes), multiplication de polynômes listes (à coefficients flottants) en temps O(N log(N)).
  On ajoute des zéros pour obtenir une liste de taille la puissance de 2 strictement supérieure au degré du produit au deux polynômes, on fait la fft de chacun puis on multiplie coefficient par coefficient et on effectue la ifft du résultat, on compare avec le produit des 2 polynômes. Par exemple
  P:=[1,2,1,2,0,0,0,0]; Q:=[1,0,1,2,0,0,0,0] ;
  p:=fft(P); q:=fft(Q);
  ifft(p .* q);
  poly1[1,2,1,2]*poly1[1,0,1,2]
  Voir aussi Karatsuba et par FFT sur C et FFT sur Z/nZ .

• Localisation de racines
  Les fonctions sturm et sturmab permettent de compter le nombre de racines réelles dans un intervalle. La fonction sturm commence par effectuer une factorisation sans racines multiples (sqrfree), puis calcule la suite des restes d'Euclide en utilisant l'algorithme du sous-résultant avec multiplication à chaque étape par un facteur pour tenir compte des signes.
  La fonction proot (et solve dans certains cas) permettent de calculer numériquement les racines d'un polynôme, par la méthode de Newton avec préfacteur adaptatif. Lorsqu'une racine est trouvée, elle est éliminée par l'algorithme de Hörner. Les racines suivantes sont calculées en recommançant la recherche de racine sur le polynôme quotient, puis améliorées en effectuant 2 ou 3 itérations de Newton avec le polynôme de départ.
• Résultant
  La fonction resultant permet de calculer le résultant de 2 polynômes par rapport à une variable, en utilisant l'algorithme du sous-résultant.
• Intersection de courbes algébriques planes
  L'instruction implicitplot de Xcas permet de représenter une courbe donnée par son équation cartésienne.
• PGCD, Bézout, factorisation
  Pour le calcul du PGCD de polynômes (instruction gcd), Xcas utilise l'algorithme du sous-résultant (psrgcd) lorsque les coefficients sont quelconques. Si les coefficients sont entiers, Xcas utilise l'un des algorithmes suivants: PGCD heuristique (heugcd), PGCD modulaire (modgcd) ou PGCD par remontée de type Hensel (ezgcd pour les polynômes à plusieurs variables uniquement).
  Le calcul de l'identité de Bézout polynomiale se fait par l'algorithme du sous-résultant uniquement (pas de modulaire pour l'instant).
  La factorisation des polynômes se fait par l'algorithme de Yun pour détecter les multiplicités de racines, puis (pour les polynômes à une variable) on sélectionne plusieurs entiers premiers tels que le polynôme reste square-free modulo ces entiers, on effectue la factorisation en degré distinct (distinct degree factorization), puis on casse les facteurs de même degré par l'algorithme de Cantor-Zassenhaus. La reconstruction se fait ensuite par remontée de Hensel puis recombinaison (avec appel des routines de PARI ou de NTL lorsqu'il y a beaucoup de facteurs modulaires afin d'éviter l'explosion combinatoire des tests à effectuer en utilisant l'algorithme de van Hoeij). Pour les polynômes ayant des coefficients vivant dans des extensions algébriques de Q, on utilise l'algorithme de Trager. Tous ces algorithmes sont décrits dans Cohen (sauf van Hoeij).
  Les sessions de Exemples->poly peuvent illustrer certaines fonctions de ce paragraphe, par exemple différents algorithmes de calcul de PGCD inefficaces avec des polynômes de grand degré pour expliquer l'intérêt de méthodes plus complexes que l'algorithme d'Euclide, la factorisation par la méthode de Berlekamp et la remontée de Hensel, l'algorithme d'élimination des racines multiples, la recherche modulaire des racines rationnelles d'un polynôme.

Retour à la barre de navigation

C5 Complexité

Retour à la barre de navigation

Textes de modélisation option C

• Représentation des objets mathématiques et algorithmes: latex, pdf
• Algèbre linéaire sur les entiers: latex, pdf
• Cryptographie: latex, pdf
  Référence pour ce texte Gilles Zemor, Cours de Cryptographie
• PGCD: latex, pdf
• Approximation des fonctions: latex, pdf
• Résultant et applications: latex, pdf
• Localisation de racines d'un polynome: latex, pdf
• Session Xcas illustrant le texte sur les carrés magiques.
• Session Xcas calcul des polynomes du texte Construction explicite de surfaces algébriques dont la projection est imposée.
• Session Xcas illustrant le texte sur les molecules a 6 atomes
• Correction du problème d'algèbre 2007, par R. De Graeve et B. Parisse, pdf, session Xcas, latex, figure 1, figure 2,

Retour à la barre de navigation

Liste des session Xcas

• Polynomes (texte 590)
• Problè Algèbre 2007
• Fraction continues
• Codes linéaires
• Cyclohexane
• Codes de Reed-Solomon
• Carrés magiques
• Multiplication par FFT
• Multiplication polynomes
• Approximant de Padé
• Methode de Pollard
• Primalité

Quelques références option C

• A Computational Introduction to Number Theory and Algebra par Victor Shoup: existe en livre (payant) ou en téléchargement gratuit
• A Course in Computational Algebraic Number Theory, de Henri Cohen
• Modern Computer Algebra, par J. Von zur Gathen et J. Gerhard
• The Art of Computer Programming, par D. Knuth, en particulier le volume semi-numerical algorithms et le volume searching and sorting
• Algorithms in C++, Third Edition, by Robert Sedgewick, Addison-Wesley, 1999.
• Cours d'algèbre, Demazure
• Calcul formel: Systèmes et algorithmes de manipulations algébriques, par Davenport, Siret, Tournier,
• Analyse numérique et équations différentielles, J.P. Demailly
• Les manuels de l'aide en ligne, ainsi que les sources de Giac/Xcas dans les répertoires /usr/share/giac/src et /usr/include/giac

ABC1 Modèles

(c) B. Parisse, 2007.
Si vous utilisez des données originales de cette page, je vous remercie de faire pointer un lien hypertexte vers cette page, afin que d'autres puissent la trouver plus facilement en utilisant un moteur de recherche.
Conditions d'utilisation:
La diffusion et l'utilisation des données de cette page est autorisée dans un but non commercial et vaut acceptation de ces conditions d'utilisation. Ces données sont fournies sans garantie aucune, le détenteur du copyright ne pourra en aucun cas être poursuivi pour quelque dommage que ce soit suite à l'utilisation des données ci-dessus, y compris s'il en a été averti.