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.

2743 vues Visites

Commentaires0

Veuillez vous connecter pour lire ou ajouter un commentaire

Articles suggérés

L'Actu des Ecoles

Dîner de collecte avec Jean Todt en faveur des étudiants des écoles de l’IMT

DC

David CHHEAN

14 septembre

L'Actu des Ecoles

Une étudiante de Télécom SudParis sillonne l’Atlantique pour enquêter sur les énergies renouvelables

DC

David CHHEAN

14 septembre

L'Actu des Ecoles

Rentrées 2020 : Institut Mines-Télécom Business school et Télécom SudParis

LL

Laura LANDES

23 juillet