Содержание
13 отношения: Communications of the ACM, Journal of the ACM, NP-полная задача, Правило резолюций, Патнэм, Хилари Уайтхолл, Поиск с возвратом, Автоматическое доказательство, Автоматическое планирование и диспетчеризация, Алгоритм CDCL, Алгоритм DPLL, Задача выполнимости булевых формул, Вычислительная сложность, Логика первого порядка.
- Автоматическое доказательство теорем
Communications of the ACM
Communications of the ACM (CACM) — ведущий ежемесячный журнал Ассоциации вычислительной техники (ACM).
Посмотреть Алгоритм DPLL и Communications of the ACM
Journal of the ACM
Journal of the ACM — главный научный журнал Ассоциации вычислительной техники, посвящённый информатике в целом, в особенности теоретическим аспектам.
Посмотреть Алгоритм DPLL и Journal of the ACM
NP-полная задача
NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных).
Посмотреть Алгоритм DPLL и NP-полная задача
Правило резолюций
Пра́вило резолю́ций — это правило вывода, восходящее к методу доказательства теорем через поиск противоречий; используется в логике высказываний и логике первого порядка.
Посмотреть Алгоритм DPLL и Правило резолюций
Патнэм, Хилари Уайтхолл
Хи́лари Па́тнэм (Hilary Whitehall Putnam; 31 июля 1926 — 13 марта 2016) — американский логик и философ.
Посмотреть Алгоритм DPLL и Патнэм, Хилари Уайтхолл
Поиск с возвратом
Поиск с возвратом, бэктрекинг (backtracking) — общий метод нахождения решений задачи, в которой требуется полный перебор всех возможных вариантов в некотором множестве М.
Посмотреть Алгоритм DPLL и Поиск с возвратом
Автоматическое доказательство
Автоматическое доказательство (Automated Theorem Proving, ATP, а также Automated deduction) — доказательство, реализованное программно.
Посмотреть Алгоритм DPLL и Автоматическое доказательство
Автоматическое планирование и диспетчеризация
Автоматическое планирование и диспетчеризация (Automated planning and scheduling, APS) — область задач искусственного интеллекта, касающаяся выполнения стратегии или последовательности действий, обычно для интеллектуальных агентов, автономных роботов и беспилотных аппаратов.
Посмотреть Алгоритм DPLL и Автоматическое планирование и диспетчеризация
Алгоритм CDCL
Алгоритм CDCL (conflict-driven clause learning — «управляемое конфликтами обучение дизъюнктам») — основанный на алгоритме DPLL эффективный решатель (NP-полных) задач выполнимости булевых формул (SAT-решатель).
Посмотреть Алгоритм DPLL и Алгоритм CDCL
Алгоритм DPLL
Алгоритм Дэвиса-Патнема-Логемана-Лавленда (DPLL) — это полный алгоритм поиска с возвратом для определения выполнимости булевых формул, записанных в конъюнктивной нормальной форме, то есть для решения задачи CNF-SAT.
Посмотреть Алгоритм DPLL и Алгоритм DPLL
Задача выполнимости булевых формул
Зада́ча выполни́мости бу́левых фо́рмул (SAT или ВЫП) — важная для теории вычислительной сложности алгоритмическая задача.
Посмотреть Алгоритм DPLL и Задача выполнимости булевых формул
Вычислительная сложность
Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных.
Посмотреть Алгоритм DPLL и Вычислительная сложность
Логика первого порядка
Логика первого порядка, называемая иногда логикой или исчислением предикатов — формальное исчисление, допускающее высказывания относительно переменных, фиксированных функций и предикатов.
Посмотреть Алгоритм DPLL и Логика первого порядка
См. также
Автоматическое доказательство теорем
- DPLL
- Автоматическое доказательство
- Доказательные вычисления
- Доказательство
- Логика Бэрроуза — Абади — Нидхэма
- Правило резолюций
- Частный случай формулы
Также известен как DPLL, DPLL-алгоритм, Алгоритм Дэвиса-Патнема.