ALGORITHMIQUE

Carte mentale

Élargissez votre recherche dans Universalis

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ù a∈ {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 :
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. 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 très rapide de la convergence (convergence quadratique) de l'algorithme de Newton entraîne que les coûts I(n) et R(n) de calcul d'inverse et d'extraction de racine carrée avec une précision de n bits sont du même ordre que le temps de la multiplication.

Transformation de Fourier discrète

La transformation de Fourier discrète (TFD) d'ordre n est une application Tn de Cn dans Cn :

définie par :
ωn = exp(2iπ/n) étant une racine n-ième de l'unité. Il s'agit donc d'un analogue discret de la transformation de Fourier classique. La transformation inverse (TFDI) s'exprime par les formules analogues :

Supposons n pair ; séparant les contributions des composantes d'indice pair et impair de x, on obtient :

Les formules (17) montrent que le calcul de Tn(x1, x2, ...) se décompose en celui de Tn/2 (x0, x2, x4, ...) et de Tn/2 (x1, x3, x5, ...) suivi de 2n opérations d'addition et de multiplication complexes. Si n est une puissance de 2, la même décomposition peut être appliquée récursivement : chaque TFD d'ordre n/2 se ramène au calcul de deux TFD d'ordre n/4 ...

Ce principe est à la base de l'algorithme dit de transformée de Fourier (discrète) rapide (TFR) explicité par Cooley et Tuckey en 1965. La complexité du calcul de Tn par l'algorithme TFR mesurée en nombre d'opérations élémentaires sur R ou C vérifie ainsi la récurrence :

dont la solution est :

L'algorithme TFR représente une réduction de complexité importante, puisqu'un calcul direct de (16) correspond à un nombre d'opérations élémentaires en O(n2). Il possède de nombreuses applications au calcul numérique de transformées de Fourier et de produits de convolution en traitement du signal et en traitement d'images.

L'intérêt de la TFR pour les algorithmes arithmétiques provient de ce que la TFD transforme les produits de convolution de vecteurs en produits composante par composante. On peut ainsi obtenir le produit de deux polynômes de degré inférieur à n/2 de la manière suivante : (a) calculer les TFR d'ordre n des vecteurs des coefficients ; (b) effectuer le produit composante par composante des transformées ; (c) appliquer à ce résultat une TFD inverse calculée par l'algorithme TFR.

La complexité, en nombre d'opérations sur R ou C, de l'algorithme obtenu vérifie donc la relation :

Schönhage et Strassen ont montré en 1971 que l'utilisation de la TFR permet de calculer le produit de deux entiers de n bits en un nombre d'opérations booléennes élémentaires égal à :

Cependant, la complexité de la mise en œuvre de cet algorithme n'en rend l'utilisation avantageuse que pour des valeurs de n relativement grandes (n >> 100). La méthode d'itération de Newton conduit alors à des algorithmes de division et d'extraction de racines de complexité analogue à (20).

Tests de primalité et de factorisation

Un entier m composite (non premier) possède nécessairement un facteur plus petit que m. Il en résulte que l'essai successif des divisions exactes de m par les nombres 2, 3, 4..., [m] constitue à la fois un algorithme de factorisation – qui détermine les diviseurs de m si m est composite – et un test de primalité – si aucun diviseur n'a été obtenu. Contrairement aux algorithmes précédemment étudiés, celui-c [...]

1  2  3  4  5
pour nos abonnés,
l’article se compose de 11 pages

Médias de l’article

Algorithmes de calcul de p

Algorithmes de calcul de p
Crédits : Encyclopædia Universalis France

tableau

Arbre binaire

Arbre binaire
Crédits : Encyclopædia Universalis France

dessin

Échelle de complexité

Échelle de complexité
Crédits : Encyclopædia Universalis France

tableau

Afficher les 3 médias de l'article


Écrit par :

Classification

Autres références

«  ALGORITHMIQUE  » est également traité dans :

CALCUL, mathématique

  • Écrit par 
  • Philippe FLAJOLET
  •  • 1 782 mots

Dans le chapitre « Calculabilité et algorithmique »  : […] Dans les années 1930 s'élabore, sous l'impulsion notamment du logicien Alan Turing, une théorie abstraite de la calculabilité, ce avant même l'avènement de l'ordinateur. Tout n'est pas calculable en mathématique et, par exemple, il ne saurait exister de procédé systématique permettant de distinguer par calcul, parmi l'infini des assertions mathématiques possibles, celles qui sont vraies : il s'agi […] Lire la suite

INDE (Arts et culture) - Les mathématiques

  • Écrit par 
  • Agathe KELLER
  •  • 5 560 mots
  •  • 3 médias

Dans le chapitre « Mathématiciens à l’échelle du monde »  : […] À 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 émigrent vers les États-Unis et le Royaume-Uni (notamment Harish-Chandra), des liens particuliers sont au […] Lire la suite

ITÉRATION, mathématique

  • Écrit par 
  • Jean-Paul DELAHAYE, 
  • Universalis
  •  • 876 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 d'en envisager l'itération, celle-ci conduisant soit à de nouvelles fonctions ou opérations, soit à des structures ou p […] Lire la suite

KOLMOGOROV ANDREÏ NIKOLAÏEVITCH (1903-1987)

  • Écrit par 
  • Jean-Luc VERLEY
  •  • 1 416 mots
  •  • 1 média

Dans le chapitre « Mathématiques appliquées »  : […] Kolmogorov a consacré de nombreuses publications aux équations aux dérivées partielles de la physique. Les équations de Navier-Stokes étaient le prototype des équations qui interviennent dans l'étude de la réaction-diffusion, la turbulence et la mécanique statistique. En 1931, Kolmogorov a introduit une vaste classe d'équations aux dérivées partielles dont le champ naturel est l'espace de Hilbert […] Lire la suite

NUMÉRIQUE ANALYSE

  • Écrit par 
  • Jean-Louis OVAERT, 
  • Jean-Luc VERLEY
  •  • 6 645 mots

Dans le chapitre « Le concept d'approximation »  : […] Dans toutes les questions de représentation des nombres et des fonctions, il faut distinguer la recherche de solutions « exactes » de celle d'algorithmes d'« approximation » d'une solution. Mais on notera que le champ du concept d'approximation recouvre non seulement les problèmes issus de l'analyse mais aussi certaines questions purement algébriques. Ainsi, en algèbre linéaire, les méthodes itéra […] Lire la suite

OPÉRATIONNELLE RECHERCHE

  • Écrit par 
  • Georges CULLMANN
  •  • 5 548 mots
  •  • 2 médias

Dans le chapitre « La théorie des graphes »  : […] La théorie des graphes s'introduit avec facilité dans la description de solutions concrètes où existent des combinaisons d'événements ou des successions temporelles (cf.  théorie des graphes ). Ses algorithmes sont de puissants auxiliaires pour l'analyste. D'abord parce que l'algorithme, prescription détaillée des opérations à réaliser pour obtenir avec certitude la solution d'un type de problème […] Lire la suite

PROGRAMMATION

  • Écrit par 
  • Jean-François MONIN
  •  • 7 832 mots

Dans le chapitre « Structures de contrôle et structures de données, systèmes de types »  : […] Un autre élément important en programmation se trouve dans la structuration des données à manipuler. L' algorithmique (science de la conception d'algorithmes) repose pour une bonne part sur la définition de structures de données efficaces et adaptées au problème ciblé. Les données élémentaires sont représentées par des mots mémoire de taille fixe : cela inclut les entiers (bornés), les caractères […] Lire la suite

RÉCURSIVITÉ, logique mathématique

  • Écrit par 
  • Kenneth Mc ALOON, 
  • Bernard JAULIN, 
  • Jean-Pierre RESSAYRE
  •  • 9 371 mots

Dans le chapitre « Définition logique »  : […] La définition arithmétique des fonctions récursives conduit à la définition logique. Soit L le langage de l'arithmétique, dont les symboles non logiques sont + pour désigner l'addition des entiers, × pour la multiplication, ≤ pour l'ordre, = pour l'égalité ; on ajoute, pour chaque entier n un symbole de constante n . Appelons formule de type Σ une formule dans laquelle n'apparaît ni négation, ni […] Lire la suite

RÉELS NOMBRES

  • Écrit par 
  • Jean DHOMBRES
  •  • 15 297 mots

Dans le chapitre « Une construction algorithmique »  : […] Voici enfin une autre construction de R qui ne passe pas par le corps des nombres rationnels, mais utilise une définition algorithmique de la soustraction sur le développement décimal illimité (cf. calcul infinitésimal  – Calcul à une variable, chap. 1). C'est un retour à Bombelli et à Stevin. Soit R l'ensemble de toutes les suites ( x n ) n ∈ Z (doublement infinies, c'est-à-dire indexées par Z […] Lire la suite

Voir aussi

Pour citer l’article

Philippe COLLARD, Philippe FLAJOLET, « ALGORITHMIQUE », Encyclopædia Universalis [en ligne], consulté le 01 décembre 2021. URL : https://www.universalis.fr/encyclopedie/algorithmique/