ALGORITHMIQUE

Carte mentale

Élargissez votre recherche dans Universalis

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


L'objet de l'algorithmique est la conception, l'évaluation et l'optimisation des méthodes de calcul en mathématiques et en informatique. Un algorithme consiste en la spécification d'un schéma de calcul, sous forme d'une suite d'opérations élémentaires obéissant à un enchaînement déterminé.

Le terme d'algorithme tire lui-même son origine du nom du mathématicien persan Al Khwārizmī (env. 820) dont le traité d'arithmétique servit à transmettre à l'Occident les règles de calcul sur la représentation décimale des nombres antérieurement découvertes par les mathématiciens de l'Inde.

Divers algorithmes ont été en fait connus dès l'Antiquité dans le domaine de l'arithmétique ou de la géométrie, parmi lesquels, notamment :

– les règles de calcul de longueur d'arcs et de surfaces des civilisations égyptienne et grecque ;

– plusieurs méthodes de résolution d'équations en nombres entiers, à la suite des travaux de Diophante d'Alexandrie au ive siècle ;

– l'algorithme d'Euclide (env. 300 av. J.-C.) qui permet le calcul du plus grand commun diviseur de deux nombres ;

– le schéma de calcul du nombre π dû à Archimède.

Ensuite ont été étudiées les méthodes numériques de résolution d'équations algébriques (algorithme de Newton, méthode d'élimination de Gauss), puis d'équations différentielles. Enfin, l'avènement de calculateurs électroniques, à l'issue de la Seconde Guerre mondiale, a entraîné un renouvellement complet de l'algorithmique, appliquée désormais soit à des problèmes de taille bien supérieure à celle des problèmes traités manuellement (d'où la nécessité de méthodes nouvelles), soit surtout à des types de problèmes nouveaux, comme le tri, la recherche rapide d'informations non numériques (base de données) ou l'optimisation combinatoire.

L'exemple du calcul de π

La question du calcul du nombre π = 3,141 592 6... (rapport de la circonférence au diamètre d'un cercle), étudiée dès l'Antiquité, est caractéristique des problèmes généraux rencontrés en algorithmique.

Historiquement, une fois reconnue l'existence d'un rapport constant entre circonférenc [...]

1 2 3 4 5

pour nos abonnés,
l’article se compose de 11 pages




É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 »  : […] 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 utile de superposer aux données un type de […] Lire la suite☛ http://www.universalis.fr/encyclopedie/calcul-mathematique/#i_11962

INDE (Arts et culture) - Les mathématiques

  • Écrit par 
  • Agathe KELLER
  •  • 5 548 mots
  •  • 4 médias

Dans le chapitre « Mathématiciens à l’échelle du monde »  : […] 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 l’Angleterre (notamment Harish-Chandra), des liens particuliers […] Lire la suite☛ http://www.universalis.fr/encyclopedie/inde/#i_11962

ITÉRATION, mathématique

  • Écrit par 
  • Jean-Paul DELAHAYE, 
  • Universalis
  •  • 876 mots

En algorithmique et en informatique, l'itération est une structure de contrôle essentielle offerte sous des formes diverses par tous les langages de programmation évolués et permettant de demander à un programme d'opérer un traitement répétitif sur les données […] Lire la suite☛ http://www.universalis.fr/encyclopedie/iteration-mathematique/#i_11962

KOLMOGOROV ANDREÏ NIKOLAÏEVITCH (1903-1987)

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

Dans le chapitre « Mathématiques appliquées »  : […] 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 approfondies. […] Lire la suite☛ http://www.universalis.fr/encyclopedie/andrei-nikolaievitch-kolmogorov/#i_11962

NUMÉRIQUE ANALYSE

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

Dans le chapitre « Le concept d'approximation »  : […] L'aspect algorithmique. C'est une des originalités essentielles du point de vue numérique en analyse. On ne s'intéresse pas seulement à l'existence de suites d'approximation d'un nombre ou d'une fonction mais à la recherche d'algorithmes, c'est-à-dire de procédures explicites de calcul des termes successifs d'une […] Lire la suite☛ http://www.universalis.fr/encyclopedie/analyse-numerique/#i_11962

OPÉRATIONNELLE RECHERCHE

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

Dans le chapitre « La 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, peut être confié à l'ordinateur ; ensuite parce que la manifestation fondamentale de l'organisation chez l'homme […] Lire la suite☛ http://www.universalis.fr/encyclopedie/recherche-operationnelle/#i_11962

PROGRAMMATION

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

Dans le chapitre « Structures de contrôle et structures de données, systèmes de types »  : […] 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 […] Lire la suite☛ http://www.universalis.fr/encyclopedie/programmation/#i_11962

RÉCURSIVITÉ, logique mathématique

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

Dans le chapitre « Définition logique »  : […] dit récursif (on dit aussi décidable) si sa fonction caractéristique est récursive. Intuitivement, cela signifie qu'il existe un algorithme permettant de décider si un élément quelconque de Np appartient ou non à X. Ainsi, les ensembles finis, l'ensemble des nombres premiers, l'ensemble des nombres qui sont somme de deux […] Lire la suite☛ http://www.universalis.fr/encyclopedie/recursivite-logique-mathematique/#i_11962

RÉELS NOMBRES

  • Écrit par 
  • Jean DHOMBRES
  •  • 15 294 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 à […] Lire la suite☛ http://www.universalis.fr/encyclopedie/nombres-reels/#i_11962

Voir aussi

Pour citer l’article

Philippe FLAJOLET, Philippe COLLARD, « ALGORITHMIQUE », Encyclopædia Universalis [en ligne], consulté le 22 novembre 2018. URL : http://www.universalis.fr/encyclopedie/algorithmique/