ALGORITHMIQUE

Carte mentale

Élargissez votre recherche dans Universalis

Algorithmes combinatoires

Entrent dans la catégorie des problèmes combinatoires, en informatique, les problèmes qui consistent à déterminer, pour une donnée d, si est satisfaite une condition :

où : (a) S(d) est l'espace de recherche (l'espace des solutions potentielles) de taille exponentielle en la taille de d ; (b) Q est une condition facilement vérifiable algorithmiquement (c'est-à-dire en un temps polynomial en la taille de ses arguments).

L'exemple le plus simple est le problème du sac à dos. Sous sa forme la plus élémentaire, il consiste, pour une donnée d = (d1, d2, ..., dm ; M) où di, M ∈ N, à déterminer s'il existe des s∈ {0 ; 1} tels que :

En termes concrets : Peut-on remplir exactement un sac de capacité M avec un sous-ensemble d'objets de taille d1, d2, ..., dn ? L'analogie avec (1) est immédiate : S(d) est l'ensemble {0, 1}n (de taille 2n) et la condition Q(ds) est la condition (2) trivialement vérifiable par addition lorsque d et s sont connus.

On reconnaîtra de même comme appartenant à cette catégorie les problèmes suivants :

– Le problème du voyageur de commerce. La donnée est constituée d'un ensemble V de villes, pour chaque paire v, v′ ∈ V d'une distance d(v, v′) ∈ N, et d'une borne B ∈ N. Le problème consiste à déterminer s'il existe une « tournée » de V de longueur bornée par B : soit m la cardinalité de V ; il s'agit de déterminer s'il existe une permutation vσ(1), vσ(2), ..., vσ(m) de V telle que :

– Le problème du coloriage de graphes. Étant donné un graphe G et un entier m, déterminer si G est m-coloriable, c'est-à-dire s'il existe une fonction f de l'ensemble des sommets de G dans {1, 2, ..., m} telle que, pour toute arête {ss′} du graphe :
– La programmation en nombres entiers. La donnée est un ensemble de formes linéaires M, L1, L2... de Zm dans Z (à coefficients entiers) et un ensemble d'entiers B, b1, b2... Il s'agit de déterminer si le système d'inégalités :
possède une solution entière ȳ ∈ Zm.

Convenablement formalisée par référence à un modèle de calcul (par exemple le modèle de la machine de Turing), et à un codage standard des données, la relation (1) définit la notion de problème NP – c'est-à-dire résoluble en temps polynomial par une machine non déterministe. Les problèmes NP sont résolubles algorithmiquement en un temps 2p(n) pour un certain polynôme p : il suffit pour cela d'organiser une recherche exhaustive sur l'espace de recherche S(d).

Il a été montré, à la suite de travaux de Cook et Karp vers 1970, que plusieurs centaines de problèmes de la classe NP, d'origine très variée en théorie des graphes, ordonnancement, théorie des jeux, optimisation combinatoire..., sont algorithmiquement équivalents : on entend par là qu'ils sont inter-réductibles au moyen de réductions algorithmiquement « efficaces », c'est-à-dire calculables en temps polynomial. Malgré l'ampleur des recherches algorithmiques, aucun algorithme n'a été trouvé qui permette de résoudre l'un quelconque de ces problèmes en un temps polynomial en la taille des données d'entrées. Ce fait donne lieu à la célèbre conjecture :

dans laquelle P désigne la classe des problèmes résolubles en temps polynomial.

Étant donné le caractère hautement plausible de cette conjecture, la recherche concernant les problèmes combinatoires s'oriente soit vers la découverte de sous-problèmes algorithmiquement résolubles rapidement (par un algorithme dans P), soit vers la découverte d'heuristiques permettant de trouver des solutions approchées rapidement.

Dans le cas des quatre problèmes précédemment cités, on a en particulier obtenu les résultats suivants :

– Problème du sac à dos : Étant donné un taux d'erreur fixé ε > 0, le problème SAC(ε) est obtenu en remplaçant la condition (2) par la condition plus faible :

On montre que, pour chaque ε fixé, il existe un algorithme polynomial permettant de résoudre SAC(ε). Le problème du sac à dos est donc « polynomialement approximable ».

– Problème du voyageur de commerce : Lorsque les distances vérifient l'inégalité triangulaire classique :

la construction polynomiale d'un arbre de recouvrement permet de déterminer une tournée qui soit dans un rapport à la tournée optimale d'au plus 1,5. Le problème du voyageur de commerce est donc partiellement polynomialement approximable pour des distances vérifiant l'inégalité triangulaire.

– Problème du coloriage de graphes : La situation du problème du coloriage de graphes est différente de celle des deux cas précédents. On montre en effet que le problème de détermination d'un coloriage qui soit dans un rapport α de l'optimum est, pour α < 2, de complexité comparable au problème général. Donc, moyennant la conjecture P ≠ NP, il n'existe pas d'algorithme polynomial permettant la détermination approchée du nombre chromatique d'un graphe dans un rapport inférieur à 2.

Il a été montré, en revanche, que tout graphe planaire est coloriable avec au plus quatre couleurs.

– Programmation en nombres entiers : On doit à Lenstra (1981) un algorithme qui, pour un nombre fixé de variables, permet de résoudre la programmation en nombres entiers en un temps polynomial (le degré du polynôme étant fonction du nombre de variables).

Le problème dans lequel on cherche aux équations (5) une solution réelle ȳ ∈ Rm, et non plus entière, est connu sous le nom de programmation linéaire. Il est résolu pratiquement par la méthode du simplexe due à Dantzig, et un résultat récent de Khatchian montre qu'il s'agit en fait d'un problème polynomial.

Ces quelques exemples donnent une idée de la diversité des approches à la réduction de complexité des problèmes d'optimisation combinatoire.

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/