Analyse multivariée d'algorithmes: au-delà des problèmes NP-difficiles
Publié par Adrien le 19/01/2019 à 08:00
Source: CNRS INS2I
Le Laboratoire de l'informatique du parallélisme (LIP - CNRS/ENS de Lyon/Inria/Université Claude Bernard Lyon 1) fête ses 30 ans. Focus sur une des thématiques du laboratoire: l'élaboration et l'analyse d'algorithmes efficaces pour des problèmes combinatoires difficiles, et plus particulièrement des problèmes de graphes.

Lorsqu'on résout un problème à l'aide d'un ordinateur (Un ordinateur est une machine dotée d'une unité de traitement lui permettant d'exécuter des programmes enregistrés. C'est un ensemble de circuits électroniques permettant de manipuler...), on souhaite généralement élaborer l'algorithme le plus efficace possible. Une manière classique de mesurer l'efficacité d'un algorithme est de compter le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) d'étapes maximum qu'il va devoir effectuer. C'est ce que l'on appelle la complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par...) temporelle dans le pire des cas. Elle s'exprime comme une fonction de la taille de l'entrée du problème. Prenons l'exemple d'une liste de n noms de personnes ainsi que leur âge.

Si je veux savoir s'il existe une personne ayant 50 ans, je peux tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) simplement parcourir ma liste et vérifier l'âge de chacune. Un tel algorithme devra parcourir (dans le pire des cas) la liste entière, et donc effectuer n tests. On dira qu'un tel algorithme a une complexité linéaire.

Si maintenant je veux tester s'il existe deux personnes dont la somme des âges vaut 100, je peux parcourir toutes les paires possibles de personnes. Dans le pire des cas, je devrai ainsi tester les n(n-1)/2 paires possibles. On dira qu'un tel algorithme a une complexité quadratique, car ce nombre de paires est “de l'ordre de” n^2.

Enfin, si je veux tester s'il existe un groupe (de taille quelconque) de personnes dont la somme des âges vaut 500, je peux énumérer la liste de tous les sous-ensembles possibles, et tester à chaque fois si la somme de leurs âges vaut 500. Je devrai ainsi, toujours dans le pire des cas, tester les 2^n ensembles de sous-ensembles possibles. On dira qu'un tel algorithme a une complexité exponentielle (La fonction exponentielle est l'une des applications les plus importantes en analyse, ou plus généralement en mathématiques et dans ses domaines d'applications. Il existe plusieurs définitions...).

Les deux premiers algorithmes se rangent dans la catégorie des algorithmes dits polynomiaux, car leur complexité est une fonction polynomiale (linéaire dans le premier cas, quadratique dans le second), alors que le troisième, en revanche, est un algorithme exponentiel. Les algorithmes exponentiels sont souvent impraticables lorsque la taille de l'entrée devient grande. Pour donner un ordre d'idée, avec une liste de 265 personnes, le nombre de paires de personnes est inférieur à 35 000, ce qui est un nombre d'opérations très raisonnable pour un ordinateur. En revanche, le nombre de sous-ensembles de personnes possibles (2^265) dépasse le nombre d'atomes (Un atome (du grec ατομος, atomos, « que l'on ne peut diviser ») est la plus petite partie d'un corps simple...) dans notre univers (L'Univers est l'ensemble de tout ce qui existe et les lois qui le régissent.): même si les processeurs de nos ordinateurs sont capables de faire plusieurs milliards de calculs par seconde ( Seconde est le féminin de l'adjectif second, qui vient immédiatement après le premier ou qui s'ajoute à quelque chose de nature identique. La seconde est une unité de...), il faudrait plusieurs millénaires pour pouvoir venir à bout de cette énumération.

La question centrale à laquelle doit répondre l'algorithmicien est la suivante: existe-t-il un algorithme polynomial qui résout mon problème ? Malheureusement, sous une conjecture (En mathématiques, une conjecture est une assertion qui a été proposée comme vraie, mais que personne n'a encore pu démontrer ou réfuter.) classique de l'informatique (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le traitement automatique de...) théorique (appelée P≠NP), certains problèmes (dits NP-difficiles) ne disposent pas de tel algorithme.

Un exemple de problème NP-difficile est le suivant: étant donné un réseau (Un réseau informatique est un ensemble d'équipements reliés entre eux pour échanger des informations. Par analogie avec un filet (un réseau est un « petit rets », c'est-à-dire un petit filet), on appelle nœud...) d'ordinateurs et un sous-ensemble (En mathématiques, un ensemble A est un sous-ensemble ou une partie d’un ensemble B, ou encore B est sur-ensemble de A, si tout élément du...) de ces ordinateurs que l'on appellera les terminaux, le but est de trouver le plus petit sous-réseau (Le mot sous-réseau a deux significations. Sa signification ancienne mais plus générale est un réseau (Réseau informatique) physique faisant parti d'un réseau plus global...) qui relie l'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être...) des terminaux, afin, par exemple, qu'ils puissent communiquer entre eux sans avoir à mobiliser tous les ordinateurs du réseau pour faire passer (Le genre Passer a été créé par le zoologiste français Mathurin Jacques Brisson (1723-1806) en 1760.) les messages.

La NP-difficulté de ce problème implique que n'importe quel algorithme aura un temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) d'exécution exponentiel en la taille du réseau (toujours sous l'hypothèse P≠NP). Cependant, il est intéressant ici de distinguer le nombre total ( Total est la qualité de ce qui est complet, sans exception. D'un point de vue comptable, un total est le résultat d'une addition, c'est-à-dire une somme....) d'ordinateurs du réseau et le nombre de terminaux. C'est l'objectif de la notion de complexité paramétrée d'un problème, qui offre un cadre théorique permettant l'analyse multivariée d'un algorithme.

Dans le cas ci-dessus, il est effectivement possible d'élaborer un algorithme dont le temps d'exécution sera exponentiel en le nombre de terminaux seulement (et polynomial en le nombre total d'ordinateurs du réseau). On dira alors que l'explosion combinatoire (On nomme explosion combinatoire en recherche opérationnelle, et en particulier dans le domaine de la programmation dynamique, le fait qu'un petit changement...) peut être restreinte au paramètre (Un paramètre est au sens large un élément d'information à prendre en compte pour prendre une décision ou pour effectuer un calcul.) “nombre de terminaux”. Si dans le pire des cas ce nombre peut être du même ordre de grandeur que le nombre total d'ordinateurs du réseau, il se peut qu'en pratique il soit bien inférieur (on peut par exemple imaginer 15 terminaux dans un réseau de plusieurs milliers d'ordinateurs), ce qui implique qu'un tel algorithme a de grandes chances d'être efficace dans ce cas.


Un exemple de réseau d'ordinateurs, avec les terminaux en rouge, et un sous-réseau reliant ces terminaux en vert (Le vert est une couleur complémentaire correspondant à la lumière qui a une longueur d'onde comprise entre 490 et 570 nm. L'œil humain possède un récepteur, appelé cône M, dont la bande passante est axée sur cette...)

La théorie de la complexité (La théorie de la complexité s'intéresse à l'étude formelle de la difficulté des problèmes en informatique. Elle se distingue de la théorie de la calculabilité qui s'attache à savoir si un...) paramétrée, née dans la fin des années 1990, a bâti un ensemble de classes de complexité permettant de distinguer les problèmes pouvant admettre des algorithmes efficaces avec certains paramètres, et ceux qui sont fortement soupçonnés de ne pas en admettre. Cette théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée ou une connaissance spéculative, souvent basée sur...) offre ainsi dans un certain sens (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine. Par une évolution progressive allant du ralentissement du...) un raffinement (En informatique, le raffinement consiste à avoir une approche de conception où on affine à chaque étape le niveau de détails ; le but étant d'atteindre le niveau de granularité. On appelle aussi...) du problème P ≠ NP et des classes de difficultés qui y sont liées.

Les paramètres considérés peuvent être de diverses natures, et correspondre parfois à des propriétés structurelles des instances d'entrée. Ceci permet de proposer une généralisation (La généralisation est un procédé qui consiste à abstraire un ensemble de concepts ou d'objets en négligeant les détails de façon à ce qu'ils puissent...) et une explication à un grand nombre de phénomènes algorithmiques bien connus. Par exemple, le problème mentionné précédemment se simplifie grandement si le réseau a une forme particulière, par exemple s'il n'a pas de cycle (on dira que c'est un arbre), ou s'il peut être représenté dans le plan sans que les liaisons entre les ordinateurs ne se croisent (on dira que c'est un graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) planaire). C'est ici qu'entre en jeu la théorie des graphes (Le terme de graphe désigne en mathématiques une opération d'application. Il possède deux acceptions :), qui utilise des outils mathématiques (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les nombres, les figures, les structures et les...) simples permettant de modéliser les réseaux ainsi que de nombreuses autres structures discrètes que l'on peut rencontrer en pratique.

L'un des liens entre la complexité paramétrée et les graphes est de considérer comme paramètre la distance qui sépare un graphe donné d'une classe de graphes pour laquelle un problème devient facile. Il est ainsi possible d'une part d'élaborer des algorithmes qui seront d'autant plus efficaces que la distance considérée est petite, et d'autre part de pouvoir généraliser des algorithmes connus pour des ensembles d'instances plus importants. Tout ceci fait appel à des outils puissants de la théorie structurale des graphes, tels que la notion de largeur (La largeur d’un objet représente sa dimension perpendiculaire à sa longueur, soit la mesure la plus étroite de sa face. En géométrie plane, la largeur est la plus petite des...) arborescente.

Cette stratégie (La stratégie - du grec stratos qui signifie « armée » et ageîn qui signifie « conduire » - est :) fait partie des recherches développées au sein de l'équipe MC2: étudier les propriétés structurelles des graphes dans le but de développer des outils algorithmiques permettant d'améliorer et de classifier la complexité de problèmes combinatoires difficiles.

Publications:

- Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, Rémi Watrigant: Parameterized Complexity of Independent Set in H-Free Graphs. CoRR abs/1810.04620 (2018)
- Nicolas Bousquet, Jean Daligault, Stéphan Thomassé: Multicut Is FPT. SIAM J. Comput. 47(1): 166-207 (2018)
- Stéphan Thomassé, Nicolas Trotignon, Kristina Vuskovic: A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs. Algorithmica 77(3): 619-641 (2017)
Page générée en 0.338 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique