Metraipolis › archive › dc_2efe9e06317d

Algoritmo di Davis-Putnam — Wikipedia

Source
Wikipedia (it)
Original
https://it.wikipedia.org/wiki/Algoritmo_di_Davis-Putnam
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-15T16:25:02.205Z
SHA-256 of the archived text
d7d6968ee43d987516223cbfa62b6d85252d3584c20497231537388c9fbeb985
Stable URL of this page
https://metraipolis.com/documento/dc_2efe9e06317d

How to cite

Algoritmo di Davis-Putnam — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Algoritmo_di_Davis-Putnam (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_2efe9e06317d (Metraipolis archive dc_2efe9e06317d, sha256 d7d6968ee43d987516223cbfa62b6d85252d3584c20497231537388c9fbeb985)
BibTeX
@misc{dc2efe9e06317d,
  title = {Algoritmo di Davis-Putnam — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/Algoritmo_di_Davis-Putnam},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_2efe9e06317d; sha256 d7d6968ee43d987516223cbfa62b6d85252d3584c20497231537388c9fbeb985},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Algoritmo_di_Davis-Putnam. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

L'algoritmo di Davis-Putnam fu sviluppato da Martin Davis e Hilary Putnam allo scopo di verificare la soddisfacibilità booleana (SAT) di formule di logica proposizionale in forma normale congiuntiva (CNF). È un tipo di procedimento di risoluzione nel quale le variabili sono scelte iterativamente ed eliminate, risolvendo ogni clausola in cui questa compaia diretta con ogni clausola in cui compaia negata. L'algoritmo DP è stato il primo algoritmo per la risoluzione di problemi SAT. Ma questo in generale è molto inefficiente poiché richiede un uso esponenziale della memoria, quindi è adatto a problemi di piccole dimensioni. La sua evoluzione è un algoritmo di ricerca chiamato DPLL. A volte l'algoritmo di Davis–Putnam o DP è scorrettamente usato in riferimento DPLL, ma questi due sono ben distinti.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in italiano, in ordine alfabetico).
Fonte: Wikipedia in italiano, voce «Algoritmo di Davis-Putnam» — https://it.wikipedia.org/wiki/Algoritmo_di_Davis-Putnam
Wikidata Q1177898: «algoritmo per controllare la validità di una formula logica» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1177898
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Algoritmo_di_Davis-Putnam?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 151262581, consultata il 2026-10-15T16:00:19.571Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: a2619eea4e21818efb662b29772aa4739aa8c17621c151ea5c21ebe26ec87e57