Représentation et manipulation de structures algébriques. Opérations d’addition, de multiplication, de division, d’extraction de racine carrée sur les ensembles : entiers longs, flottants multiprécision, nombres complexes, polynômes, Z/nZ ,corps finis :
Algorithmes algébriques élémentaires. Exponentiation (n a n, pour n N), algorithme d’Euclide étendu, tris. * Exemples d’algorithmes de multiplication rapide, de factorisation, de tests de primalité.*
Algèbre linéaire.
Sur un corps: réduction d’une matrice aux formes classiques (pivot de Gauss, LU, QR,...). Calcul du rang, du déterminant. *Exemples de codes correcteurs.* * Exemples d’algorithmes géométriques :enveloppe convexe, méthode du simplexe.*
Cas des matrices à coefficients entiers: opérations élémentaires sur les lignes et les colonnes (application aux systèmes linéaires sur Z ). Application aux groupes abéliens de type fini, en particulier au calcul des diviseurs élémentaires.
Polynômes.
Évaluation (Horner,...), interpolation (Lagrange, différences finies, splines), * transformation de Fourier discrète *. Localisation des racines. Résultants, élimination ; * intersection de courbes algébriques planes *.
Exemples d’évaluation de la complexité d’un algorithme : cas le pire, en moyenne ; en temps, en espace. Aucune formalisation d’un modèle de calcul n’est exigée.