dvorkin@rain.ifmo.ru
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Методы автоматизации доказательства NP-полноты двумерных локально зависимых задач презентация
Содержание
- 1. Методы автоматизации доказательства NP-полноты двумерных локально зависимых задач
- 2. Двумерные локально зависимые задачи Вход: поле h×w
- 3. Применение устройств «На языке задачи L» выражается
- 4. Постановка задачи Автоматизация построения устройств с заданной
- 5. Сведение 1-in-3 SAT к L Задача 1-in-3
- 6. Одинарные и двойные провода Провод придумывается человеком,
- 7. Набор устройств для двойных проводов «Создание» «Валидатор»
- 8. Динамическое программирование по профилю Профиль — вертикальный
- 9. Подход «перебор всех полей» Перебрать все поля,
- 10. Метадинамическое программирование Рассмотрим два поля после обработки
- 11. Метадинамическое программирование O(min(|A|hwnp|B|, |A||B|nphw2np)) Критична высота рассматриваемого
- 12. Задача (2,3)-замощения Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.
- 13. Задача 4-CROSS SUM (открытый вопрос) Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.
- 14. Задача 4-CROSS SUM (открытый вопрос) Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.
- 15. Спасибо за внимание
Двумерные локально зависимые задачи Вход: поле h×w Вопрос: существует ли заполнение? Корректность заполнения = проверка квадратов s×s Примеры: Головоломки Сапер Какуро (CROSS SUM) Замощение данным набором полимино (p,q)-замощение Автоматизация доказательства
Слайд 1Методы автоматизации доказательства NP-полноты двумерных локально зависимых задач
Дворкин М. Э.
Научный руководитель:
Корнеев
Г. А., к. т. н., доцент КТ СПбГУ ИТМО
Слайд 2Двумерные локально зависимые задачи
Вход: поле h×w
Вопрос: существует ли заполнение?
Корректность заполнения =
проверка квадратов s×s
Примеры:
Головоломки
Сапер
Какуро (CROSS SUM)
Замощение данным набором полимино
(p,q)-замощение
Автоматизация доказательства NP-полноты двумерных задач
Дворкин М. Э.
Слайд 3Применение устройств
«На языке задачи L» выражается известная NP-полная задача
Используются «устройства» (gadgets)
и провода, соединяющие их
Устройства могут быть сложны
Устройства могут быть сложны
Автоматизация доказательства NP-полноты двумерных задач
Дворкин М. Э.
Слайд 4Постановка задачи
Автоматизация построения устройств с заданной функциональностью
Описание наборов устройств, достаточных для
доказательства NP-полноты
Программная реализация
Применение для доказательства NP-полноты конкретных задач
N-CROSS SUM
Программная реализация
Применение для доказательства NP-полноты конкретных задач
N-CROSS SUM
Автоматизация доказательства NP-полноты двумерных задач
Дворкин М. Э.
Слайд 5Сведение 1-in-3 SAT к L
Задача 1-in-3 SAT:
Вход: конъюнкция из предикатов R(A,
B, C)
Вопрос: выполнима ли конъюнкция?
Удобна, поскольку истинность конъюнкций проверяется независимо
Вопрос: выполнима ли конъюнкция?
Удобна, поскольку истинность конъюнкций проверяется независимо
Автоматизация доказательства NP-полноты двумерных задач
Дворкин М. Э.
Слайд 6Одинарные и двойные провода
Провод придумывается человеком, зачастую — просто
Устройство «создание провода»
не всегда существует
Рассматриваются двойные провода:
«в фазе»
«в противофазе»
Рассматриваются двойные провода:
«в фазе»
«в противофазе»
Автоматизация доказательства NP-полноты двумерных задач
Дворкин М. Э.
Слайд 7Набор устройств для двойных проводов
«Создание»
«Валидатор»
«Одинарный
провод»
«Перекрещивание»
«1 из 3»
«2 из 3»
Автоматизация доказательства NP-полноты
двумерных задач
Дворкин М. Э.
Слайд 8Динамическое программирование
по профилю
Профиль — вертикальный «срез» поля, содержит всю необходимую информацию
для дальнейшей обработки поля
Прямой профиль
Проще для понимания
Громоздкий переход, большая таблица переходов
Изломанный профиль
Их число больше
Таблица переходов меньше
Автоматизация доказательства NP-полноты двумерных задач
Дворкин М. Э.
Слайд 9Подход «перебор всех полей»
Перебрать все поля, O(|A|hw)
Для каждого проверить, является ли
оно искомым устройством, O(nhwp|B|)
Итого: O(|A|hwnhwp|B|)
Улучшение: для разных полей не обрабатывать общие префиксы
Время работы: O(|A|hwnp|B|)
Итого: O(|A|hwnhwp|B|)
Улучшение: для разных полей не обрабатывать общие префиксы
Время работы: O(|A|hwnp|B|)
Автоматизация доказательства NP-полноты двумерных задач
Дворкин М. Э.
Слайд 10Метадинамическое программирование
Рассмотрим два поля после обработки первых i клеток. Что если
все совпадает?
Метапрофиль — множества достижимых профилей для каждого набора булевых значений входных проводов
После обработки i-й клетки все поля с одинаковыми метапрофилями можно отождествить
Метапрофиль — множества достижимых профилей для каждого набора булевых значений входных проводов
После обработки i-й клетки все поля с одинаковыми метапрофилями можно отождествить
Автоматизация доказательства NP-полноты двумерных задач
Дворкин М. Э.
Слайд 11Метадинамическое программирование
O(min(|A|hwnp|B|, |A||B|nphw2np))
Критична высота рассматриваемого поля
Если после обработки столбца то же
множество метапрофилей, что и до нее, можно остановиться
Для каждого метапрофиля хранится одно поле-представитель (самое «красивое»)
Для каждого метапрофиля хранится одно поле-представитель (самое «красивое»)
Автоматизация доказательства NP-полноты двумерных задач
Дворкин М. Э.
Слайд 13Задача 4-CROSS SUM (открытый вопрос)
Автоматизация доказательства NP-полноты двумерных задач
Дворкин М. Э.
Слайд 14Задача 4-CROSS SUM (открытый вопрос)
Автоматизация доказательства NP-полноты двумерных задач
Дворкин М. Э.
Слайд 15Спасибо за внимание
Есть ли вопросы?
Автоматизация доказательства NP-полноты двумерных задач
Дворкин М. Э.
