Discussion:Algorithme de Davis-Putnam
Cet article est indexé par les projets Informatique théorique, Logique et Mathématiques.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Ébauche | À évaluer |  | Informatique théorique (discussion • critères • liste • stats • hist. • comité • stats vues) |
 | Logique (discussion • critères • liste • stats • hist. • comité • stats vues) | ||
 | Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues) | ||
Cet article comporte une liste de tâches suggérées :
Votre aide est la bienvenue pour corriger les liens, présents dans l'article, vers les pages d'homonymie Disjonction , Littéral ⇒ Quelques explications pour effectuer ces corrections. -- 20 janvier 2014 à 18:16 (CET)
Évaluation
modifierBonjour,
J'ai supprimé l'évaluation informatique. Bien à vous,
Heuristique
modifierIl s'agit d'un problème NP-Complet et cet algorithme est donc une heuristique, il faudrait le mentionner.
Non, cette algorithme n'est pas heuristique, il cherche la solution en faisant une recherche systématique.
Par contre, j'ai modifié un peu la description de l'algo mais j'ai des doutes:
- comme dans la version que j'ai modifier j'ai utiliser union entre les deux recherche, mais ça ne serais pas plutôt un ou ?
- il n'y a pas une méthode pour choisir la variable ?
- dans le première algorithme, je ne suis pas sur de comprendre ce qu'on veux dire par "résoudre C et N"
Vanicat (d) 7 mai 2008 à 10:36 (CEST)
- Alors pour le premier algorithme, en fait je l'avais directement traduit de l'article anglophone quand j'avais créé l'article ici, mais je dois reconnaître que je n'ai pas plus attention que ça à la manière dont il fonctionne. Pour le reste, n'ayant plus utilisé l'algorithme de Davis-Putnam depuis un certain temps, je ne me rappelle plus vraiment des détails de cet algo. À l'occasion, si j'ai le temps, je reprendrai mes notes sur le sujet pour apporter des précisions à l'article. PieRRoMaN 8 mai 2008 à 01:21 (CEST)
Algorithme récursif
modifierCet algorithme récursif ne ressemble pas du tout à l'algorithme de Davis-Putnam mais plutôt à l'Algorithme de Davis-Putnam-Logemann-Loveland. L'algorithme DP est une simple boucle (ou n'a qu'un appel récursif terminal) et n'a pas de backtracking comme l'algorithme DPLL.