Thèmes abordés : problèmes de satisfaction de contraintes, algorithmes stochastiques, problèmes de satisfaction d'expressions booléennes, procédures de Davis - Putnam, algorithme du recuit simulé, recherche Tabu, échange de Nogoods. ©Electre 2025
Les problèmes NP-complets recouvrent un très large spectre de domaines de recherche : SAT (satisfaction d'expressions booléennes), CSP (problèmes de satisfaction de contraintes), Programmation Linéaire, Recherche Opérationnelle, Théorie des Graphes, Combinatoire, Programmation par Contraintes, etc.
Théoriquement intraitables, du moins tant que la conjecture P=NP n'a pas reçu de réponse positive, ces problèmes sont au cœur de la théorie de la complexité. En pratique cependant, des progrès constants et encourageants ont été accomplis ces dernières années pour résoudre ces problèmes fondamentaux et stratégiques pour nombre d'applications industrielles. Plusieurs méthodes proposées récemment s'avèrent particulièrement prometteuses : les méthodes de simplification, la réparation locale, la recherche tabou, les heuristiques, le recuit simulé, l'évolution artificielle, les réseaux neuronaux, etc.
Pour comprendre "pourquoi" et "quand" certaines de ces méthodes marchent "mieux" ou "moins bien", d'autres travaux se sont intéressés d'une part à l'identification d'instances difficiles dans l'espace des problèmes et d'autre part à la proposition de bancs d'essais sur des instances de problèmes NP-complets générés aléatoirement.
Cette conférence annuelle, organisée par le CRID et le groupe de recherche "Aspects Algorithmiques de la Résolution de Problèmes exprimés à l'aide de Contraintes" du PRC-IA est destinée à faire le point sur l'état actuel des connaissances. Elle se veut un lieu de rencontre et d'échange entre les chercheurs travaillant sur cette problématique.
Le présent volume réunit les actes des communications présentées lors des trois journées de la conférence. Les thèmes des différentes sessions sont les suivants :
Paru le : 15/06/1996
Thématique : Langages de programmation
Auteur(s) : Auteur : Conférence nationale sur les problèmes complets (02 ; 1996 ; Dijon)
Éditeur(s) :
Teknea
Collection(s) : Non précisé.
Contributeur(s) : Auteur : CENTRE DE RECHERCHE EN INFORMATIQUE (Dijon)
Série(s) : Non précisé.
ISBN : Non précisé.
EAN13 : 9782877170550
Reliure : Broché
Pages : 302
Hauteur: 23.0 cm / Largeur 16.0 cm
Poids: 0 g
Carte fidélité
Mollat Radio
