logo
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.

2627 vues Visites

Commentaires0

Veuillez vous connecter pour lire ou ajouter un commentaire

Articles suggérés

L'Actu des Ecoles

Alumni Télécom SudParis, Soutenez les étudiants de votre école

LL

Laura LANDES

25 novembre

L'Actu des Ecoles

Je soutiens les étudiants de mon école - Institut Mines-Télécom Business School

LL

Laura LANDES

20 novembre

L'Actu des Ecoles

Remise du Trophée Start-Up Numérique 2019

LL

Laura LANDES

06 novembre