Le problème de satisfiabilité propositionnelle : un aperçu des techniques de résolution et applications - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

Le problème de satisfiabilité propositionnelle : un aperçu des techniques de résolution et applications

Résumé

Le problème de satisfiabilité propositionnelle (SAT) est l'un des problèmes les plus étudiés en intelligence artificielle. Il consiste à déterminer s'il est possible d'assigner des valeurs de vérité aux variables d’une formule logique propositionnelle de sorte à la satisfaire. Etant le premier problème à avoir été démontré NP-Complet par Stephen Cook en 1971, SAT a attiré de nombreux chercheurs tant au niveau théorique que pratique. La preuve de la NP-complétude du SAT a jeté les bases de la célèbre théorie de la NP-complétude et est au cœur du problème du millénaire encore non résolu P = ? NP. Grâce à de nombreuses années d'efforts cumulés, les chercheurs ont apporté des améliorations constantes à la technologie SAT, au point qu'aujourd'hui, les meilleurs solveurs sont couramment utilisés pour résoudre des instances extrêmement grandes comportant des millions de variables et de clauses. Ces progrès impressionnants ont encouragé l'utilisation des solveurs SAT dans la résolution de nombreux autres problèmes d'intérêt pratique dans divers domaines de l'informatique, notamment la vérification de logiciels et du matériel, la cryptanalyse, l'ordonnancement, etc.Cet exposé vise à présenter le problème de satisfiabilité propositionnelle, les techniques de résolution ainsi que la manière dont la technologie SAT est utilisée en pratique pour résoudre d'autres problèmes. [Vidéo en ligne]
ClementinTayou-mai2021.pdf (790.04 Ko) Télécharger le fichier
Format : Présentation
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03589602 , version 1 (25-02-2022)

Identifiants

  • HAL Id : hal-03589602 , version 1

Citer

Clementin Tayou Djamegni. Le problème de satisfiabilité propositionnelle : un aperçu des techniques de résolution et applications. Séminaire du LIRIMA, May 2021, [En distanciel], Cameroun. ⟨hal-03589602⟩
26 Consultations
286 Téléchargements

Partager

Gmail Facebook X LinkedIn More