ALGORITHMIQUE

Échelle de complexité

L' étude précédente permet de situer divers problèmes algorithmiques sur une « échelle de complexité » présentée dans le tableau. Les diverses mesures de coût utilisées (opérations booléennes, opérations élémentaires sur les nombres réels, comparaisonséchanges) n'étant pas strictement équivalentes, la définition d'une telle échelle se précise par l'introduction d'un modèle de la notion de calculabilité.

Il existe enfin de nombreux autres domaines de l'informatique où ont été découverts des algorithmes efficaces. Outre l'analyse numérique, on peut citer le traitement de données textuelles, la traduction des langages de programmation, le calcul formel, les problèmes « géométriques » concernant des données multidimensionnelles... La conception d'algorithmes efficaces combine habituellement l'utilisation de propriétés spécifiques au domaine du problème et des méthodes générales d'algorithmique (récursivité, structures de données, tris, calculs d'adresses...).

— Philippe FLAJOLET

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écouvrez nos offres

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.).

Carte mentale
Élargissez votre recherche dans Universalis

Classification

Pour citer cet article

Philippe COLLARD, Philippe FLAJOLET, « ALGORITHMIQUE », Encyclopædia Universalis [en ligne], consulté le . URL :

« ALGORITHMIQUE ». Dans Encyclopædia Universalis [en ligne]. Consulté le sur

Encyclopædia Universalis, s.v. « ALGORITHMIQUE », Consulté le ,

Médias

Algorithmes de calcul de p

Encyclopædia Universalis France

Arbre binaire

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

Rejoignez-nous

Inscrivez-vous à notre newsletter

ALGORITHMIQUE

Échelle de complexité

CALCUL, mathématique

INDE (Arts et culture) - Les mathématiques

ITÉRATION, mathématique

KOLMOGOROV ANDREÏ NIKOLAÏEVITCH (1903-1987)