Approche probabiliste du dénombrement des solutions du problème de satisfiabilité

الموضوعات

علوم بحتة وطبيعية

الملخص

A l'origine, le travail consistait en 1 'étude des lois de répartition du nombre de solutions pour des de ,As r-SAT (n,k). On pensait que la détermination de la lo1 de probabilité du nombre N de pour certaines classes de données SAT , permettrait d'avoir· rapidement une réponse avec peu de risque d'erreur dans un grand nombre de cas, ~ la question: <<Cette donnée SAT est-elle ou ~ >>. On espérait par cette approche obtenir un gain de complexité de calcul contre une perte de certitude sur la solution du problème de .Cette approche est d'une complexité insurmontable, erronée et n'est pas susceptible d'application ni pour le problème de , ni pour le problème de dénombrement des solutions. Une approche p 1 us pr ag mat f que pout 1 e p r·ob 1 de dé de SAT est consiste~ approximer le nombre de d'une données SAT par un ~ de type Monté-Carlo . . Dans 1 e t r· sent des autour· du problème de dénombrement des solutions des instances de ~AT : En nous intéressant d'abord ~ la structure des données SAT dont 1 'analyse a donné des ~s. L'étude complète sur la classe des données r(S,O) et C(S) a donné le résultat suivant:les C(S,O) et ({S) ~ont constituées de trois catégories de données : 1 ~ des données , 1 'ensemble des données ~es qui en moyenne le minimum de solutions et des données à variables monotones qui possèdent en moyenne le maximum de solutions. Une méthode pour calculer le nombre de données équilibrées C(S,D) est donnée. Concernant le calcul du nombre , avons établi une formule combinatoire qui calcule ~e nombre.Avec cette formule on peut résoudre le problème de sans avoir ~ dénombrer toutes les solutions. l. a deuxième étude sur le dénombrement de SAT devait concerner 1 •exploration de la loi de du nombre de solutions pour une classe r-SAT (n,k) donnée.Pour ce fair·e,on a !'~ le modèle de génération de données r-SAT (n,k).Nous nous somme vite de la difficulté de cette étude. ,les ,> qu'on a effectué montrent que le de génération d'instances r-SAT (n,k) génère seulement des d'après lea résultats de notre première étude,que le · moyen de solutions des données ordinaires est compris entre celui des données équilibrées et celui des données à variables monotones. Par conséquent,i1 a été préférable et plus & certaines de dispersion comme 1' de et la variance de la classe C(S). Pour cela,on a étudié la ~ d'~ des formules théoriques de la moyenne pour lea • ,asses de données SAT équilibrées et des données SAT à variables 11e> .Ces formules devaient d'avoir une estimation de , 'étendue de variation des nombres de solution dans la classe C (S). Pour la ~e des données à variables monotones,une formule a été f( établie. Par contre la for·mule de la moyenne pl•Ur la classe des données équilibrées est très difficile a établir

روابط وملفات

التعريف والنوع

رقم الوثيقة

0a5a1502-484f-44d6-bcc6-ed9d726e7019

رقم العقد

0

نوع الوسائط

Crawler

نوع المحتوى

الرسائل العلمية

صيغة المصدر

رسائل ماجيستير

نوع الملف

pdf text

أسماء الملفات

1372989_1.pdf

بيانات النشر

ألقاب المؤلفين

[{"name_ar":" Ahmed Bensalma","title_ar":"اعداد","title_en":"Preparation"}]

اللغة

French

المصدر والدورية

اسم المصدر

Approche probabiliste du dénombrement des solutions du problème de satisfiabilité

المحتوى والصفحات

عدد الصفحات

0

كلمات الباحثين

,dénombrement Statistique, dénombrement, Mathématique Probabilité, Probabilité, statistique

إشراف وإعداد

الإعداد

Ahmed Bensalma

الاقتباسات الببليوغرافية