10 février 2006
Ce document est lié à :
info:eu-repo/semantics/reference/issn/0987-6936
Ce document est lié à :
info:eu-repo/semantics/reference/issn/1950-6821
All rights reserved , info:eu-repo/semantics/openAccess
Israël-César Lerman et al., « Segmentation de la sériation pour la résolution de #SAT », Mathématiques et sciences humaines, ID : 10.4000/msh.2793
Le problème général traité est celui de l'évaluation approchée du nombre de solutions d'une formule booléenne F sous forme normale conjonctive. En appliquant le principe "diviser pour résoudre", la méthode présentée permet de réduire de façon considérable la complexité algorithmique du problème. Elle est basée sur la segmentation d'une sériation établie sur la table d'incidence associée à F. Nous montrons, dans des cas aléatoires difficiles de génération d'une formule F, l'intérêt de la sériation et de sa meilleure coupure en deux parties connexes et de tailles comparables. De plus, nous définissons la notion d'indépendance en probabilité pour F. On propose ici et on valide théoriquement et par une vaste expérimentation la méthode.