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 :
également noté a et dont le vecteur constitue la représentation binaire de longueur (taille) n. Étant donné deux entiers a, b, donnés par leurs représentations de longueur n, un problème de base consiste à déterminer la somme et le produit :sous forme de représentations binaires de longueur n + 1 et 2n respectivement. L'algorithme classique calcule les bits si de s par les relations :où ri représente la retenue entrante correspondant à la position i.Le produit p correspond dans l'algorithme classique au développement :
L'évaluation de (4) correspond seulement à n additions d'entiers de longueur 2 n, puisque les multiplications par 2i s'obtiennent en représentation binaire par simple décalage.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 :
Le produit xy vaut :et, sous cette forme, le calcul nécessite quatre multiplications de nombres de taille m. On peut se ramener au calcul de trois produits seulement :en observant la relation :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 :
(les termes en O(m) représentent le coût des additions). La solution de (10) est :Ce qui représente par rapport à (5) un gain substantiel lorsque n est grand.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 :
par la récurrence :la valeur initiale x0 étant choisie suffisamment proche de la racine x de (12).L'application de cette méthode aux fonctions :
conduit à deux suites récurrentes :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 :
Les relations (14) et (15) ramènent donc le calcul de l'inverse et de la racine carrée d'un entier aux seules opérations d'addition et de multiplication. Le caractère[...]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
Autres références
-
ALGORITHME
- Écrit par Thomas SEILLER et Alberto NAIBO
- 5 919 mots
- 3 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