WWW.PDF.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Разные материалы
 

«с/к “Эффективные алгоритмы” Лекция 4: Задача выполнимости А. Куликов Computer Science клуб при ПОМИ А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости ...»

с/к “Эффективные алгоритмы”

Лекция 4: Задача выполнимости

А. Куликов

Computer Science клуб при ПОМИ

http://logic.pdmi.ras.ru/infclub/

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 1 / 30

План лекции

Определение задачи

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 2 / 30

План лекции

Определение задачи

Сведения

Японские кроссворды

Eternity

Максимальный разрез

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 2 / 30

План лекции

Определение задачи Сведения Японские кроссворды Eternity Максимальный разрез Что мы узнали за сегодня А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 2 / 30 План лекции Определение задачи Сведения Японские кроссворды Eternity Максимальный разрез Что мы узнали за сегодня А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 3 / 30 Формула в КНФ Определение А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 4 / 30 Формула в КНФ Определение Пропозициональной или Булевой (propositional, Boolean) переменной называется переменная, принимающая значения true (1) и false (0).

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 4 / 30 Формула в КНФ Определение Пропозициональной или Булевой (propositional, Boolean) переменной называется переменная, принимающая значения true (1) и false (0).

Литералом (literal) называется Булева переменная x или ее отрицание ¬x.

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 4 / 30 Формула в КНФ Определение Пропозициональной или Булевой (propositional, Boolean) переменной называется переменная, принимающая значения true (1) и false (0).



Литералом (literal) называется Булева переменная x или ее отрицание ¬x.

Клозом (clause) называется дизъюнкция конечного множества литералов, не содержащего одновременно переменной и ее отрицания.

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 4 / 30 Формула в КНФ Определение Пропозициональной или Булевой (propositional, Boolean) переменной называется переменная, принимающая значения true (1) и false (0).

Литералом (literal) называется Булева переменная x или ее отрицание ¬x.

Клозом (clause) называется дизъюнкция конечного множества литералов, не содержащего одновременно переменной и ее отрицания.

k-клозом (k-clause) называется клоз, содержащий ровно k литералов.

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 4 / 30 Формула в КНФ Определение Пропозициональной или Булевой (propositional, Boolean) переменной называется переменная, принимающая значения true (1) и false (0).

Литералом (literal) называется Булева переменная x или ее отрицание ¬x.

Клозом (clause) называется дизъюнкция конечного множества литералов, не содержащего одновременно переменной и ее отрицания.

k-клозом (k-clause) называется клоз, содержащий ровно k литералов.

Формулой в конъюнктивной нормальной форме (КНФ) (formula in conjunctive normal form, CNF) называется конъюнкция конечного множества клозов.

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 4 / 30 Меры сложности формул А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 5 / 30 Задача выполнимости Определение А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 6 / 30 Задача выполнимости Определение Задача пропозициональной выполнимости (Boolean satisfiability problem, SAT): определить, выполнима ли данная формула в КНФ, то есть существует ли набор Булевых значений переменным формулы, выполняющий формулу. Такой набор называют выполняющим (satisfying assignment), а формулу, для которой такой набор существует, — выполнимой (satisfiable).





А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 6 / 30 Задача выполнимости Определение Задача пропозициональной выполнимости (Boolean satisfiability problem, SAT): определить, выполнима ли данная формула в КНФ, то есть существует ли набор Булевых значений переменным формулы, выполняющий формулу. Такой набор называют выполняющим (satisfying assignment), а формулу, для которой такой набор существует, — выполнимой (satisfiable).

Задача максимальной выполнимости (maximum satisfiability problem, SAT): по данной формуле определить, какое максимальное количество ее клозов может быть выполнено.

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 6 / 30 Задача выполнимости Определение Задача пропозициональной выполнимости (Boolean satisfiability problem, SAT): определить, выполнима ли данная формула в КНФ, то есть существует ли набор Булевых значений переменным формулы, выполняющий формулу. Такой набор называют выполняющим (satisfying assignment), а формулу, для которой такой набор существует, — выполнимой (satisfiable).

Задача максимальной выполнимости (maximum satisfiability problem, SAT): по данной формуле определить, какое максимальное количество ее клозов может быть выполнено.

k-SAT, MAX-k-SAT — частные случаи соответствующих задач, когда все клозы входной формулы содержат не более k литералов.

–  –  –

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 7 / 30 NP-трудность А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 8 / 30 NP-трудность Первая известная NP-полная задача (Кук, 1971).

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 8 / 30 NP-трудность Первая известная NP-полная задача (Кук, 1971).

3-SAT тоже NP-полна.

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 8 / 30 NP-трудность Первая известная NP-полная задача (Кук, 1971).

3-SAT тоже NP-полна.

2-SAT может быть решена за линейное время.

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 8 / 30 NP-трудность Первая известная NP-полная задача (Кук, 1971).

3-SAT тоже NP-полна.

2-SAT может быть решена за линейное время.

MAX-2-SAT NP-трудна, даже если каждая переменная встречается в формуле не более трех раз.

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 8 / 30 Важность задачи А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 9 / 30 Важность задачи http://www.satisfiability.org/ — The International Conferences on Theory and Applications of Satisfiability Testing.

–  –  –

http://www.satisfiability.org/ — The International Conferences on Theory and Applications of Satisfiability Testing.

http://www.satcompetition.org/ — The international SAT Competitions web page.

–  –  –

http://www.satisfiability.org/ — The International Conferences on Theory and Applications of Satisfiability Testing.

http://www.satcompetition.org/ — The international SAT Competitions web page.

http://www.isa.ewi.tudelft.nl/Jsat — Journal on Satisfiability, Boolean Modeling and Computation.

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 9 / 30 Важность задачи http://www.satisfiability.org/ — The International Conferences on Theory and Applications of Satisfiability Testing.

http://www.satcompetition.org/ — The international SAT Competitions web page.

http://www.isa.ewi.tudelft.nl/Jsat — Journal on Satisfiability, Boolean Modeling and Computation.

http://www.satlib.org/ — The Satisfiability Library.

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 9 / 30 Важность задачи http://www.satisfiability.org/ — The International Conferences on Theory and Applications of Satisfiability Testing.

http://www.satcompetition.org/ — The international SAT Competitions web page.

http://www.isa.ewi.tudelft.nl/Jsat — Journal on Satisfiability, Boolean Modeling and Computation.

http://www.satlib.org/ — The Satisfiability Library.

http://www.satlive.org/ — Up-to-date links for the Satisfiability Problem.

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 9 / 30 Важность задачи http://www.satisfiability.org/ — The International Conferences on Theory and Applications of Satisfiability Testing.

http://www.satcompetition.org/ — The international SAT Competitions web page.

http://www.isa.ewi.tudelft.nl/Jsat — Journal on Satisfiability, Boolean Modeling and Computation.

http://www.satlib.org/ — The Satisfiability Library.

http://www.satlive.org/ — Up-to-date links for the Satisfiability Problem.

http://www.qbflib.org/ — The Quantified Boolean Formulas Satisfiability Library.

–  –  –

Что мы узнали за сегодня А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 10 / 30 Сведения А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 11 / 30 Сведения Многие известные задачи из NP очень просто сводятся к SAT или MAX-SAT.

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 11 / 30 Сведения Многие известные задачи из NP очень просто сводятся к SAT или MAX-SAT.

Сведя задачу к SAT, на практике можно воспользоваться SAT-солвером.

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 11 / 30 Сведения Многие известные задачи из NP очень просто сводятся к SAT или MAX-SAT.

Сведя задачу к SAT, на практике можно воспользоваться SAT-солвером.

Такой подход иногда помогает, иногда — нет.

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 11 / 30 План лекции Что мы узнали за сегодня А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 12 / 30 Японские кроссворды Определение Решение японского кроссворда (japanese puzzle) заключается в восстановлении картинки по длинам блоков подряд идущих закрашенных клеток в строках и столбцах.

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 13 / 30 Сведение к SAT А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 16 / 30 Замечание если какой-то индекс “вылезает”, то соответствующим переменным просто присваиваем значение 0 А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 16 / 30 Замечание если какой-то индекс “вылезает”, то соответствующим переменным просто присваиваем значение 0 можно сводить более эффективно А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 16 / 30 Примеры решенных кроссвордов А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 17 / 30 План лекции Что мы узнали за сегодня А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 18 / 30 Игра Eternity Определение Нужно замостить квадрат заданным набором доминошек так, чтобы узоры на граничащих частях доминошек совпадали.

–  –  –

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 19 / 30 Сведение к SAT дан квадрат n n и n2 доминошек А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 20 / 30 Сведение к SAT дан квадрат n n и n2 доминошек перенумеруем все клетки и доминошки числами от 1 до n2 А. Куликов (CS клуб при ПОМИ) 4.

Задача выполнимости 20 / 30 Сведение к SAT дан квадрат n n и n2 доминошек перенумеруем все клетки и доминошки числами от 1 до n2 заводим два типа переменных:

А. Куликов (CS клуб при ПОМИ) 4.

Задача выполнимости 20 / 30 Сведение к SAT дан квадрат n n и n2 доминошек перенумеруем все клетки и доминошки числами от 1 до n2 заводим два типа переменных:

xij — в i-й клетке стоит j-я доминошка А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 20 / 30 Сведение к SAT

–  –  –

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 23 / 30 Не все так просто, тем не менее итак, мы записали игру Eternity в виде задачи выполнимости конкретной формулы при помощи полиномиального сведения

–  –  –

итак, мы записали игру Eternity в виде задачи выполнимости конкретной формулы при помощи полиномиального сведения осталось напустить на полученную формулу какой-нибудь эффективный SAT-солвер

–  –  –

итак, мы записали игру Eternity в виде задачи выполнимости конкретной формулы при помощи полиномиального сведения осталось напустить на полученную формулу какой-нибудь эффективный SAT-солвер но в чем же тогда подвох?

–  –  –

итак, мы записали игру Eternity в виде задачи выполнимости конкретной формулы при помощи полиномиального сведения осталось напустить на полученную формулу какой-нибудь эффективный SAT-солвер но в чем же тогда подвох?

давайте примерно оценим длину полученной формулы

–  –  –

Что мы узнали за сегодня А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 25 / 30 Задача о максимальном разрезе Определение Задача о максимальном разрезе (maximum cut, MAX-CUT) заключается в нахождении такого разбиения вершин графа на две части, при котором количество ребер, концы которых принадлежат разным частям, максимально.

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 26 / 30 Задача о максимальном разрезе Определение Задача о максимальном разрезе (maximum cut, MAX-CUT) заключается в нахождении такого разбиения вершин графа на две части, при котором количество ребер, концы которых принадлежат разным частям, максимально.

NP-трудность А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 26 / 30 Задача о максимальном разрезе Определение Задача о максимальном разрезе (maximum cut, MAX-CUT) заключается в нахождении такого разбиения вершин графа на две части, при котором количество ребер, концы которых принадлежат разным частям, максимально.

NP-трудность Одна из знаменитых 21-й NP-полной задачи Карпа.

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 26 / 30 Задача о максимальном разрезе Определение Задача о максимальном разрезе (maximum cut, MAX-CUT) заключается в нахождении такого разбиения вершин графа на две части, при котором количество ребер, концы которых принадлежат разным частям, максимально.

NP-трудность Одна из знаменитых 21-й NP-полной задачи Карпа.

Остается NP-полной даже на графах степени 3.

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 26 / 30 Сведение к MAX-2-SAT А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 27 / 30 Сведение к MAX-2-SAT каждой вершине u графа G (V, E ) поставим в соответствие переменную xu (xu = 1 — вершина u принадлежит первой части) А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 27 / 30 Сведение к MAX-2-SAT каждой вершине u графа G (V, E ) поставим в соответствие переменную xu (xu = 1 — вершина u принадлежит первой части) для каждого ребра (u, v ) запишем два клоза (xu xv ), (¬xu ¬xv )

–  –  –

каждой вершине u графа G (V, E ) поставим в соответствие переменную xu (xu = 1 — вершина u принадлежит первой части) для каждого ребра (u, v ) запишем два клоза (xu xv ), (¬xu ¬xv ) видно, что набор значений переменным u, v выполняет оба клоза, когда u и v в разных частях, и выполняет только один из них — когда в одной

–  –  –

каждой вершине u графа G (V, E ) поставим в соответствие переменную xu (xu = 1 — вершина u принадлежит первой части) для каждого ребра (u, v ) запишем два клоза (xu xv ), (¬xu ¬xv ) видно, что набор значений переменным u, v выполняет оба клоза, когда u и v в разных частях, и выполняет только один из них — когда в одной таким образом, максимальное количество одновременно выполнимых клозов полученной формулы равно |E | + |MAX-CUT(G )|

–  –  –

Что мы узнали за сегодня А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 28 / 30 Что мы узнали за сегодня?

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 29 / 30 Что мы узнали за сегодня?

Многие известные задачи из NP очень просто сводятся к SAT или MAX-SAT.

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 29 / 30 Что мы узнали за сегодня?

Многие известные задачи из NP очень просто сводятся к SAT или MAX-SAT.

Сведя задачу к SAT, на практике можно воспользоваться SAT-солвером.

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 29 / 30 Что мы узнали за сегодня?

Многие известные задачи из NP очень просто сводятся к SAT или MAX-SAT.

Сведя задачу к SAT, на практике можно воспользоваться SAT-солвером.

Сведения:

А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 29 / 30 Что мы узнали за сегодня?

Многие известные задачи из NP очень просто сводятся к SAT или MAX-SAT.

Сведя задачу к SAT, на практике можно воспользоваться SAT-солвером.

Сведения:

японские кроссворды, игра Eternity — к SAT А. Куликов (CS клуб при ПОМИ) 4. Задача выполнимости 29 / 30 Что мы узнали за сегодня?

–  –  –



Похожие работы:

«ОГЛАВЛЕНИЕ Номер раздела, Номер Название раздела, подраздела, приложения подраздела, страницы приложения Введение Основания возникновения обязанности осуществлять раскрытие информации в форме ежеквартального отчета. I. Сведения о банковских счетах, об аудиторе, оценщике и...»

«Европа Отечеств Биополитическая Цель Национал-Социализма СОДЕРЖАНИЕ Предисловие Мифотворчество и обывательские суждения Постановка проблемы Истоки Концепция Новой Европы Законы Великого пространства как основа построения Новой Европы Принципы построения Новой Европы Геополитические предпосылки Вредные факторы Рол...»

««УТВЕРЖДАЮ» Председатель закупочной комиссии В.В. Соколов «17» июня 2016 года ДОКУМЕНТАЦИЯ открытого запроса предложений на поставку труб в ППУ изоляции, компенсаторов ППУ ПЭ, скорлупы ППУ, термоусаживаемой ленты ТИАЛ для нужд филиала ПАО «ТГК-14» Генерация Бурятии Город Чита 2016 год Страница 1...»

«Контроль эффективности использования основных средств в казенных учреждениях БАРАНОВА В.А., СТАРОСТЕНКО И.А. Поволжский институт управления имени П.А.Столыпина – филиал РАНХиГС В соответствии со ст. 19 Федерального закона от 06.12.2011 № 402...»

«ФИЛОСОФИЯ Аннотация 1. Место дисциплины в структуре программы: Учебная дисциплина «Философия» входит в базовую часть общенаучного цикла ООП бакалавриата, соответствует требованиям Федерального государственного образовательного стандарта высшего профессионального образования по соо...»

«ОАО «Концерн ОАО «Концерн «МПО ОАО «ОСК» «Моринформсистема Гидроприбор» Агат» Заместитель Заместитель Руководитель генерального директора генерального директора Департамента по инновационному по науке инновационного развитию развития В.В.Кобылянский В.Е.Соколов А.Ф.Денисов Отчет о выполнении проекта реализа...»

«НЕКОММЕРЧЕСКОЕ ПАРТНЕРСТВО «ОБЪЕДИНЕНИЕ ПРОИЗВОДИТЕЛЕЙ ЖЕЛЕЗНОДОРОЖНОЙ ТЕХНИКИ» СТАНДАРТ СТО ОПЖТ 34 ОРГАНИЗАЦИИ РАМА БОКОВАЯ И БАЛКА НАДРЕССОРНАЯ ЛИТЫЕ ТЕЛЕЖЕК ЖЕЛЕЗНОДОРОЖНЫХ ГРУЗОВЫХ ВАГОНОВ Требования к процессам визуального и измерительн...»








 
2017 www.pdf.knigi-x.ru - «Бесплатная электронная библиотека - разные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.