ALGORITHMIQUE
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 :
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 si ∈ {0 ; 1} tels que :
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 :
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 :
É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[...]
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é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.).
Classification
Médias
Algorithmes de calcul de p
Encyclopædia Universalis France
Arbre binaire
Encyclopædia Universalis France
Échelle de complexité
Encyclopædia Universalis France
Autres références
-
ALGORITHME
- Écrit par Alberto NAIBO et Thomas SEILLER
- 5 919 mots
- 4 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 Bernard PIRE
- 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 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 et Encyclopædia 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...
- Afficher les 10 références
