Abstract FR:

Etude de la satisfiabilite de classes de donnees. Etablissement d'un theoreme de satisfiabilite et refutation de la conjecture de tovey. Proposition d'une conjecture sur une frontiere de satisfiabilite. Etude du calcul du nombre de solutions pour des donnees de satisfiabilite. Introduction d'une notion d'independance entre clauses. Etablissement de formules combinatoires perpmettant de calculer le nombre de solutions, presentation d'une methode algorithmique pour calculer le nombre de solutions, calcul de sa complexite experiences numeriques. Presentation d'un modele probabiliste, calcul de l'esperance mathematique du nombre de solutions, deduction d'une borne inferieure pour la probabilite de contradiction. Partition de l'ensemble des donnees definies par leur structure et leur distribution de variables. Calcul de la formule de la moyenne du nombre de solutions dans les classes, calcul d'une borne inferieure de la probabilite de contradiction d'une donnee aleatoire dans une classe. Commencement de l'etude de la dispersion des nombres de solutions dans les classes. Identification des donnees ayant le maximum de solutions dans une classe, caracterisation des classes de dispersion nulle