Navigation – Plan du site

AccueilNuméros147Segmentation de la sériation pour...

Segmentation de la sériation pour la résolution de ­ #SAT

Cutting seriation for approximate #SAT resolution
Israël-César Lerman et Valérie Rouat

Résumés

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.

Haut de page

Pour citer cet article

Référence électronique

Israël-César Lerman et Valérie Rouat, « Segmentation de la sériation pour la résolution de ­ #SAT »Mathématiques et sciences humaines [En ligne], 147 | Automne 1999, mis en ligne le 10 février 2006, consulté le 22 juin 2025. URL : http://journals.openedition.org/msh/2793 ; DOI : https://doi.org/10.4000/msh.2793

Haut de page

Auteurs

Israël-César Lerman

Articles du même auteur

Valérie Rouat

Haut de page

Droits d’auteur

Le texte et les autres éléments (illustrations, fichiers annexes importés), sont « Tous droits réservés », sauf mention contraire.

Haut de page
Search OpenEdition Search

You will be redirected to OpenEdition Search