Abonnez-vous à Universalis pour 1 euro

ALGORITHMIQUE

Échelle de complexité

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

É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

  • : professeur des Universités
  • : ingénieur de recherche à l'Institut national de recherche en informatique et automatique (I.N.R.I.A.).

Classification

Médias

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

Algorithmes de calcul de p

Arbre binaire - crédits : Encyclopædia Universalis France

Arbre binaire

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

Échelle de complexité

Autres références

  • ALGORITHME

    • Écrit par et
    • 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
    • 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
    • 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
    • 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 et
    • 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