ALGORITHMIQUE
Algorithmes arithmétiques
La catégorie des algorithmes arithmétiques inclut les algorithmes des opérations fondamentales sur les entiers et les polynômes : dans le cas d'entiers de grande taille – de polynômes de degré élevé – des méthodes récursives ou fondées sur la transformation de Fourier discrète conduisent à des gains importants. Les algorithmes de factorisation et de test de primalité, liés à la théorie des nombres, ont permis de construire des systèmes de codage nouveaux (systèmes à clefs publiques).
Addition et multiplication classiques
À tout vecteur binaire a = (a0, a1, ..., an−1), où ai ∈ {0, 1}, se trouve associé l'entier :
Le produit p correspond dans l'algorithme classique au développement :
La mesure naturelle de complexité de ces algorithmes est le nombre d'opérations booléennes élémentaires effectuées. Les complexités respectives de l'addition et de la multiplication selon ces méthodes sont aussi respectivement :
Méthodes récursives
Soit à évaluer le produit de deux nombres x et y de longueur n = 2m donnés sous la forme :
L'utilisation répétée (pour le calcul des produits P1, P2, P3) de cette décomposition, qui ramène une multiplication d'entiers de taille 2m à trois multiplications en longueur m, conduit à un algorithme récursif dont le coût vérifie ainsi la récurrence :
Une méthode analogue s'applique au produit de polynômes (en remplaçant dans les équations (5) à (8), le nombre 2 par l'indéterminée x) et permet également de calculer le produit de deux polynômes de degré n en O(n1,585) opérations élémentaires sur les coefficients.
Il a été montré également par Strassen que le produit de deux matrices de dimension (2m) × (2m) se ramène au produit de sept matrices de dimension m × m. L'utilisation récursive de cette réduction conduit à un algorithme de multiplication matricielle pour des matrices de dimension n dont la complexité en nombre d'opérations sur les coefficients est égale à :
Les méthodes de conception récursives de ce type sont susceptibles d'applications très nombreuses, aussi bien dans le domaine des algorithmes arithmétiques (le calcul de transformées de Fourier), que dans celui du traitement de données non numériques.
Algorithme de Newton
L' algorithme de Newton consiste à approcher une solution de l'équation :
L'application de cette méthode aux fonctions :
Sous des conditions très larges sur les valeurs initiales y0 et z0, yn et zn convergent vers les zéros de g et h respectivement, soit :
La suite de cet article est accessible aux abonnés
- Des contenus variés, complets et fiables
- Accessible sur tous les écrans
- Pas de publicité
Déjà abonné ? Se connecter
Écrit par
- Philippe COLLARD : professeur des Universités
- Philippe FLAJOLET : ingénieur de recherche à l'Institut national de recherche en informatique et automatique (I.N.R.I.A.).
Classification
Médias
Algorithmes de calcul de p
Encyclopædia Universalis France
Arbre binaire
Encyclopædia Universalis France
Échelle de complexité
Encyclopædia Universalis France
Autres références
-
ALGORITHME
- Écrit par Alberto NAIBO et Thomas SEILLER
- 5 919 mots
- 4 médias
La notion d’algorithme a envahi nos discours et nos pratiques, en raison surtout de la diffusion massive d’applications informatiques dédiées à l’exécution automatisée de certaines tâches, ou à la résolution de certains problèmes. On trouve en effet les algorithmes non seulement dans de nombreux domaines...
-
PRIX ABEL 2021
- Écrit par Bernard PIRE
- 1 014 mots
- 2 médias
Le prix Abel, qui distingue chaque année un ou plusieurs mathématiciens pour leurs contributions exceptionnelles au développement des mathématiques, a été décerné en 2021 au Hongrois László Lovász et à l’Israélien Avi Wigderson. Dix-neuf ans après la création de ce « prix Nobel des...
-
CALCUL, mathématique
- Écrit par Philippe FLAJOLET
- 1 785 mots
L'algorithmique s'attache à l'élaboration d'algorithmes efficaces pour résoudre les problèmes reconnus comme calculables. Cette discipline s'organise selon quelques grands principes généraux. Par exemple, pour traiter efficacement des problèmes de recherche d'information de forme complexe, il s'avère... -
INDE (Arts et culture) - Les mathématiques
- Écrit par Agathe KELLER
- 5 429 mots
- 3 médias
À l’indépendance, la création de centres d’excellence pour les mathématiques et une école indienne très forte, notamment en algorithmique théorique, placent définitivement l’Inde nouvellement créée sur la carte mondiale des sciences mathématiques. Si un certain nombre de mathématiciens fameux... -
ITÉRATION, mathématique
- Écrit par Jean-Paul DELAHAYE et Encyclopædia Universalis
- 830 mots
Itérer signifie recommencer, faire à nouveau. Construire les nombres entiers peut être vu comme l'opération consistant à partir de zéro à itérer indéfiniment l'ajout d'une unité.
Plus généralement, en mathématiques, lorsqu'une fonction ou opération est disponible, il est fréquent...
- Afficher les 10 références
