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
. In Encyclopædia Universalis []. Disponible sur : (consulté le )
Médias
Algorithmes de calcul de p
Encyclopædia Universalis France
Algorithmes de calcul de p
Comparaison des approximations fournies par les trois algorithmes de calcul de p
Encyclopædia Universalis France
Arbre binaire
Encyclopædia Universalis France
Arbre binaire
Un arbre binaire de recherche associé à la suite x = 12, 9, 23, 6, 3, 18, 7 et sa lecture en…
Encyclopædia Universalis France
Échelle de complexité
Encyclopædia Universalis France
Échelle de complexité
Échelle de complexité.
Encyclopædia Universalis France
Autres références
-
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, 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...
-
KOLMOGOROV ANDREÏ NIKOLAÏEVITCH (1903-1987)
- Écrit par Jean-Luc VERLEY
- 1 421 mots
- 1 média
Enfin Kolmogorov a fait d'importantes recherches en algorithmique. Ce sujet qui n'intéressait jusqu'alors que les logiciens (constructivistes) fit un immense bond en avant avec l'informatique et la théorie de l'information ; les outils comme l'entropie ou la complexité font dès lors l'objet de recherches... - Afficher les 10 références
Voir aussi
- CODAGE
- INFORMATION, informatique et télécommunications
- NOMBRES PREMIERS
- ALGORITHMES GÉNÉTIQUES
- COLORIAGE PROBLÈME DU
- POLYGONES
- INFORMATIQUE ET MATHÉMATIQUES
- PRIMALITÉ TESTS DE
- PROGRAMMATION MATHÉMATIQUE
- FOURIER DISCRÈTE TRANSFORMATION DE (TFD)
- FERMAT PETIT THÉORÈME DE
- PI CALCUL DE
- NEWTON ALGORITHME DE
- PROGRAMMATION EN NOMBRES ENTIERS
- SALAMIN ALGORITHME DE
- TRI MÉTHODES DE, mathématiques
- ALGORITHME
- FACTORISATION
- COOLEY JAMES WILLIAM (1926-2016)
- TUCKEY JOHN WILDER (1915-2000)
- FOURIER RAPIDE TRANSFORMÉE DE ou FTP (Fast Fourier Transform)
- P PROBLÈME, théorie de la complexité
- NP PROBLÈME, théorie de la complexité
