Методы автоматизации доказательства NP-полноты двумерных локально зависимых задач Дворкин М. Э. Научный руководитель: Корнеев Г. А., к. т. н., доцент КТ.

Презентация:



Advertisements
Похожие презентации
Применение методов решения задачи удовлетворения ограничениям для построения управляющих конечных автоматов по сценариям работы Владимир Ульянцев Научный.
Advertisements

Применение генетических алгоритмов для генерации тестов к олимпиадным задачам по программированию Буздалов М.В., СПбГУ ИТМО.
Применение генетического программирования для реализации систем со сложным поведением Санкт-Петербургский Государственный Университет Информационных Технологий,
NP-полнота Основные NP-полные задачи. Задача «Независимое множество» Условие. Задан граф G=(V,E) и целое число k. Вопрос. Существует ли независимое множество.
NP-полнота Теорема Кука. Полиномиальная сводимость Пусть Π 1 =(X 1,Y 1 ) и Π 2 =(X 2,Y 2 ) задачи распознавания. Будем говорить, что Π 1 полиномиально.
Разработка программного средства 3Genetic для генерации автоматов управления системами со сложным поведением Государственный контракт «Технология.
Вычислительная сложность Классы сложности P и NP. Сергей Казаков, аспирант каф. КТ, НИУ ИТМО.
Системы управления базами данных БД – это информационная модель, позволяющая в упорядоченном виде хранить данные о группе объектов, обладающих одинаковым.
Базовые логические элементы. Чтобы сконструировать устройство, мы должны знать: каким образом следует реализовать логические значения 0 и 1 в виде электрических.
Базы данных – это совокупность сведений (о реальных объектах, процессах, событиях или явлениях), относящихся к определенной теме или задаче, организованная.
Алгоритм называется частичным алгоритмом, если мы получаем результат только для некоторых d є D и полным алгоритмом, если алгоритм получает правильный.
Класс NP и NP-полные задачи. NP-полнота задачи выполнимости Задача выполнимости булевой функции: Вход: булева функция, заданная формулой Требуется определить,
Постановка задачи Описание алгоритма 1 Описание алгоритма 2 Математическая постановка задачи Сравнение алгоритмов Выбор оптимального алгоритма на примере.
Построение автоматов управления системами со сложным поведением на основе тестов с помощью генетического программирования Федор Николаевич Царев, СПбГУ.
Проверка эквивалентности срединной и линейной осей многоугольника Дипломная работа студента 545 группы Подколзина Максима Валериевича Санкт-Петербургский.
Введение Задачи с параметрами давно вошли в практику вступительных экзаменов по математике ведущих учебных заведений Задачи с параметрами давно вошли.
Системы управления базами данных (СУБД). Необходимо различать Базы данных, которые являются упорядоченным набором данных. Создание баз данных, а также.
Виды моделей данных. Ядром любой базы данных является модель данных. Модель данных представляет собой множество структур данных, ограничений целостности.
Приближенные схемы Задачи теории расписаний. Полиномиальная приближенная схема (PTAS) Семейство приближенных алгоритмов для задачи Π, {A ε } ε называется.
Технология хранения, поиска и сортировки информации в базах данных
Транксрипт:

Методы автоматизации доказательства NP-полноты двумерных локально зависимых задач Дворкин М. Э. Научный руководитель: Корнеев Г. А., к. т. н., доцент КТ СПбГУ ИТМО

Двумерные локально зависимые задачи Вход: поле h×w Вопрос: существует ли заполнение? Корректность заполнения = проверка квадратов s×s Примеры: Головоломки – Сапер – Какуро (CROSS SUM) Замощение данным набором полимино – (p,q)-замощение 2Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.

Применение устройств «На языке задачи L» выражается известная NP-полная задача Используются «устройства» (gadgets) и провода, соединяющие их Устройства могут быть сложны 3Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.

Постановка задачи Автоматизация построения устройств с заданной функциональностью Описание наборов устройств, достаточных для доказательства NP-полноты Программная реализация Применение для доказательства NP-полноты конкретных задач – N-CROSS SUM 4Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.

Сведение 1-in-3 SAT к L Задача 1-in-3 SAT: Вход: конъюнкция из предикатов R(A, B, C) Вопрос: выполнима ли конъюнкция? Удобна, поскольку истинность конъюнкций проверяется независимо 5Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.

Одинарные и двойные провода Провод придумывается человеком, зачастую просто Устройство «создание провода» не всегда существует Рассматриваются двойные провода: – «в фазе» – «в противофазе» 6Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.

Набор устройств для двойных проводов «Создание» «Валидатор» «Одинарный провод» «Перекрещивание» «1 из 3» «2 из 3» 7Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.

Динамическое программирование по профилю Профиль вертикальный «срез» поля, содержит всю необходимую информацию для дальнейшей обработки поля Прямой профиль Проще для понимания Громоздкий переход, большая таблица переходов Изломанный профиль Их число больше Таблица переходов меньше 8Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.

Подход «перебор всех полей» Перебрать все поля, O(|A| hw ) Для каждого проверить, является ли оно искомым устройством, O(nhwp|B|) Итого: O(|A| hw nhwp|B|) Улучшение: для разных полей не обрабатывать общие префиксы Время работы: O(|A| hw np|B|) 9Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.

Метадинамическое программирование Рассмотрим два поля после обработки первых i клеток. Что если все совпадает? Метапрофиль множества достижимых профилей для каждого набора булевых значений входных проводов После обработки i-й клетки все поля с одинаковыми мета профилями можно отождествить 10Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.

Метадинамическое программирование O(min(|A| hw np|B|, |A||B|nphw2 np )) Критична высота рассматриваемого поля Если после обработки столбца то же множество мета профилей, что и до нее, можно остановиться Для каждого мета профиля хранится одно поле-представитель (самое «красивое») 11Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.

Задача (2,3)-замощения 12Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.

Задача 4-CROSS SUM (открытый вопрос) 13Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.

Задача 4-CROSS SUM (открытый вопрос) 14Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.

Спасибо за внимание Есть ли вопросы? 15Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.