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.

2609 vues Visites

Commentaires0

Veuillez vous connecter pour lire ou ajouter un commentaire

Articles suggérés

L'Actu des Ecoles

Retour sur les évènements T&MA du trimestre

LL

Laura LANDES

02 décembre

L'Actu des Ecoles

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

LL

Laura LANDES

25 novembre

L'Actu des Ecoles

Forum des Télécommunications le 03 décembre 2019

LL

Laura LANDES

22 novembre