Retour aux actualités
Article suivant Article précédent

L'enseignant-chercheur Denis Berthier publie "Constraint Resolution Theories"

L'Actu des Ecoles

-

10/10/2011

La résolution des Problèmes finis de Satisfaction de Contraintes
expliqué par Denis Berthier
 
Le livre, publié en anglais, met l'accent sur la recherche de la solution la plus simple (titre du livre : Constraint Resolution Theories).


Relevant de la logique constructive, le paradigme de résolution repose sur la notion de règle de résolution : une formule logique du type condition-action, où la condition est un motif qui doit être présent dans l'état courant de résolution pour justifier l'élimination d'un candidat (i.e. d'une valeur possible d'une variable) par la partie action.
Définissant une théorie de résolution comme un ensemble fixe de règles de résolution, le livre introduit plusieurs suites croissantes de telles théories. A chacune est associée sa propre notion de simplicité ainsi qu'une mesure de la complexité des instances du CSP.
 
Chacune satisfait deux principaux théorèmes :
  • La propriété de confluence (garantissant que la mesure de complexité associée a de bonnes propriétés calculatoires)
  • Une correspondance avec une procédure de recherche structurée sans succès par hasard (Essais-et-Erreurs).
 
Ce livre comprend une étude de cas détaillée du Sudoku avec :
  • Des contre-exemples à des questions de subsomption entre règles
  • Des statistiques et résultats de classification sans biais pour la mesure de complexité des instances
  • Des comparaisons de portée entre plusieurs théories de résolution
  • D'autres exemples issus du problème des n-Reines montrent que le même motif abstrait peut apparaître dans différents CSP sous des allures variées.

2551 vues Visites

Commentaires0

Veuillez vous connecter pour lire ou ajouter un commentaire

Articles suggérés

L'Actu des Ecoles

Les candidatures pour notre Trophée Start-up Numérique 2019 sont désormais ouvertes !

MM

Mehdi MALKI

10 juillet

L'Actu des Ecoles

Le campus d'Evry a fêté ses 40 ans !

MM

Mehdi MALKI

02 juillet

L'Actu des Ecoles

Diplômés et étudiants de Télécom SudParis, nous souhaiterions votre avis.

MM

Mehdi MALKI

20 mai