ALGORITHMIQUE

Carte mentale

Élargissez votre recherche dans Universalis

Les problèmes algorithmiques du traitement de l'information

Méthodes de tri

Le problème du tri consiste, étant donné une suite x = (x1x2, ..., xn) d'éléments d'un ensemble totalement ordonné – par exemple N ou R –, à déterminer une permutation σ de 1, ..., n telle que :

soit triée, c'est-à-dire que :
(Il est clairement équivalent de déterminer la suite triée y ou la permutation triante σ.)

L'algorithme de tri par échanges consécutifs, TEC, est conceptuellement le plus simple. Il consiste en (n − 1) phases successives :

La première phase (j = n) propage ainsi le maximum de x1x2, ..., xn en dernière position ; la phase suivante j = (n − 1) amène le deuxième plus grand élément de la suite originale en position (n − 1)..., et à l'issue de l'algorithme, la suite x1x2, ..., xn se retrouve triée. Le placement d'un maximum partiel s'effectue par propagation de ce maximum vers la droite selon le schéma :
Par exemple, avec n = 5 et la valeur initiale x = (5, 3, 9, 4, 2), la suite des valeurs de x obtenues est :

La complexité d'un algorithme de tri tel que TEC se mesure par le nombre de comparaisons effectuées et par le nombre de déplacements d'éléments de la suite (sur l'exemple, dix comparaisons et sept échanges). Dans le cas de l'algorithme TEC appliqué à une suite de longueur n, le nombre de comparaisons vaut exactement :

le nombre d'échanges varie selon le type d'ordre de la suite x donnée entre les limites 0 (soit x initialement triée) et n(n − 1)/(2) (soit x triée en ordre inverse). La complexité de l'algorithme TEC vérifie donc :

De nombreux algorithmes de tri élémentaires possèdent une complexité en O(n2). Comme dans le cas des algorithmes arithmétiques, une conception récursive conduit à une réduction importante de complexité.

L'algorithme de tri-fusion est ainsi fondé sur le principe suivant : Supposons n pair, n = 2 m ; pour trier x1x2, ..., xn, on trie séparément x1x2, ..., xm et xm+1xm+2, ..., xn. Soit u = (u1u2, ..., um) et v = (v1, v2, ..., vm) les résultats de ces deux tris. On obtient la suite y correspondant au tri de x par la fusion (ou interclassement) des suites u et v, l'algorithme de fusion étant défini récursivement par :

Une programmation classique fondée sur ces équations montre que la fusion de u et v s'effectue en O(|u| + |v|) opérations élémentaires. Le tri de n éléments est aussi ramené à deux tris de n/2 éléments suivi d'une fusion de complexité O(n). Le coût du tri-fusion vérifie donc la récurrence :
dont la solution est :

Parmi les autres méthodes de tri récursif de complexité O(n log n), la plus connue est le tri-partition, encore appelé « tri rapide » (Hoare, 1962). Le tri-partition de x = (x1, x2, ..., xn) correspond à la suite de calculs :

(a) séparer x en deux sous-ensembles x′, x″ :

(b) trier séparément x′ et x″, avec pour résultats y′ et y″ ;

(c) retourner le résultat global y = y′ ( y″.

L'algorithme de tri-fusion est à la base des méthodes de tri externe appliquées aux fichiers sur disque. L'algorithme de tri-partition, convenablement optimisé, est le plus rapide pour les tris en mémoire centrale d'ordinateur.

Structures de données

Une autre approche du problème du tri repose sur la construction de structures de données : il s'agit de la superposition à l'ensemble des données (un simple vecteur dans le cas du tri) d'une structure plus riche permettant un accès plus rapide aux informations ainsi complétées.

La structure de donnée la plus importante en informatique est certainement la structure d'arbre (graphe connexe sans cycle). Étant donné une suite x = (x1x2, ..., xn), un arbre binaire de recherche construit sur x est un arbre binaire (chaque sommet possède deux descendants distingués) dont les sommets internes sont étiquetés par les éléments de x de telle manière que la lecture des étiquettes en projection donne la suite triée correspondant à x.

Arbre binaire

Dessin : Arbre binaire

Un arbre binaire de recherche associé à la suite x = 12, 9, 23, 6, 3, 18, 7 et sa lecture en projection. Chemins d'accès résultant de la recherche de 7 (A) et de la recherche de 20, non présent dans la suite x (B). 

Crédits : Encyclopædia Universalis France

Afficher

L'intérêt de cette structure est de permettre facilement les opérations de recherche (c'est-à-dire répondre à la question : a est-il égal à l'une des composantes de x ?), insertion ou suppression d'éléments. La recherche d'un élément a dans l'arbre A s'effectue en comparant a à la racine r de A. Si a est plus petit que r, on poursuit la recherche (récursivement) dans le sous-arbre gauche ; si a est plus grand que r, on la poursuit dans le sous-arbre droit. Il s'agit donc d'une généralisation de la recherche dichotomique classique.

Les arbres de recherche sont à la base de méthodes d'accès à des fichiers rangés en mémoire externe (disque) comme les arbres B dus à Bayer et McCreight (1970). Diverses autres catégories d'arbres sont utilisées en compilation (arbres de syntaxe), dans la programmation des systèmes informatiques (tris, gestion des files de priorité), ainsi que dans de nombreux algorithmes de graphes.

Méthodes de calcul d'adresses

Les structures de données précédemment décrites sont fondées sur des comparaisons entre les données. Une autre classe de méthodes, dites de calcul d'adresse ou de « hachage », consiste à calculer pour chaque donnée d une valeur h(d) qui détermine la position (« adresse ») de d dans une table. La fonction h est appelée fonction de hachage.

Un exemple de données x = {x1x2, ..., xn} sera représenté en stockant x1 à l'adresse h(x1), x2 à l'adresse h(x2)... Si la configuration particulière des données d'entrée de l'algorithme est telle que h(xi) ≠ h(xj) pour tout ≠ j, on dispose ainsi d'une méthode d'accès direct : un enregistrement peut être localisé en O(1) opérations. Dans le cas contraire, lorsque deux ou plusieurs données partagent une même adresse a, on dit qu'il y a collision sur l'adresse a.

Les méthodes de calcul d'adresses diffèrent par la manière dont sont traitées les collisions : on peut par exemple ranger une donnée qui entre en collision avec une autre à la première adresse non occupée dans la table (méthodes d'« adressage ouvert »), ou la stocker dans une zone séparée. Le choix d'un algorithme de hachage adapté permet dans la plupart des cas de garantir un accès quasi direct aux données, soit en mémoire centrale soit en mémoire secondaire.

L'analyse d'algorithmes

Les algorithmes de cette section présentent, à la différence de nombreux algorithmes arithmétiques (multiplication rapide, transformation de Fourier discrète) un comportement qui dépend fortement de la configuration particulière des données d'entrées. On a vu pour le tri TEC que le nombre d'échanges nécessaire au tri de n éléments pouvait varier entre 0 et n(n − 1)/(2). On obtient une mesure plus significative de la complexité des algorithmes en évaluant les valeurs moyennes (espérances) des coûts sous divers modèles probabilistes naturels (indépendance des xi, uniformité de distribution des valeurs de la fonction de hachage...).

Ces évaluations de complexité moyenne nécessitent le comptage de structures finies : permutations dans le cas du tri, suites d'adresses dans les cas des algorithmes de hachage. On utilise pour cela les méthodes de l [...]

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/