Информационная технология минимизации функционалов, ассоциированных с задачей выполнимость

• Автор: Хныкин, Иван Геннадьевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Омск
• Количество страниц: 135 с. : ил.

Оглавление
Введение

Глава 1. Задача ВЫПОЛНИМОСТЬ и методы ее решения

1.1. Постановка задач

1.2. Математические модели задачи ВЫПОЛНИМОСТЬ

1.3. Алгоритмы поиска решения задачи ВЬШОЛНИМОСТЬ

1.3.1. Алгоритм БР (ПаУ18-Ри1пат)

1.3.2. Алгоритм ПРЬЬ (Davis-Putnam-Logemann-Loveland)

1.3.3. Методы локального поиска

1.3.4. Методы преодоления локальных экстремумов

1.3.5. Семейство алгоритмов локального поиска с обходом локальных минимумов
1.3.6. Семейство градиентных алгоритмов локального поиска
1.3.7. Методы глобальной оптимизации
1.3.8. Непрерывный метод Лагранжа
Глава 2. Описание гибридного метода последовательных приближений с «инерцией» в применении к задаче ВЫПОЛНИМОСТЬ
2.1. Переход от задачи ВЬШОЛНИМОСТЬ к задаче поиска глобального минимума
2.2. Построение метода последовательных приближений с «инерцией»
2.3. Модификации и гибридизации метода последовательных приближений с «инерцией»
2.3.1. Переход к задаче 3-ВЬШОЛНИМОСТЬ
2.3.2. Стратегия применения правил резолюции
2.3.3. Выбор начального приближения
2.3.4. Добавление весовых множителей
2.3.5. Сдвиг по антиградиенту
2.3.6. Туннелирование
2.3.7. Метод смены траектории
2.3.8. Рестарт
2.3.9. Выбор метода проектирования
2.3.10. Увеличение разрядности
2.3.11. Гибридный метод последовательных приближений с «инерцией»
2.3.12. Способы распараллеливания метода
Глава 3. Результаты численных экспериментов применения модифицированного метода последовательных приближений с «инерцией» к различным типам задач ВЫПОЛНТГМОСТЬ
3.1. Задачи для тестирования метода последовательных приближений с
«инерцией» и его модификаций
3.1.1. Тестовые примеры открытой библиотеки SATLib
3.1.2. Задачи криптографического анализа несимметричных шифров
3.2. Результаты численных экспериментов гибридного метода последовательных приближений с «инерцией»
3.2.1. Стратегия применения правил резолюции
3.2.2. Переход к задаче 3-ВЫПОЛНИМОСТЬ
3.2.3. Добавление весовых множителей
3.2.4. Сдвиг по антиградиенту
3.2.5. Метод смены траектории и туннелирование
3.2.6. Увеличение разрядности
3.2.7. Гибридный метод последовательных приближений с «инерцией»
3.2.8. Способы распараллеливания метода
3.3. Исследование применимости метода последовательных приближений с «инерцией» к задаче факторизации
3.3.1. Определение наиболее вероятных значений бит сомножителей
3.3.2. Выбор начального приближения
Заключение
Список обозначений
Литература
Приложение
Приложение

Введение
Задача ВЫПОЛНИМОСТЬ — одна из наиболее интересных задач информатики.
В 1936 году Эмиль Пост (Emil Leon Post), а в 1937 году - Алан Тьюринг (Alan Turing) независимо друг от друга разработали теоретическую модель вычислительной машины, которая легла в основу теории алгоритмов. Она представляет собой бесконечную в одну сторону ленту, по которой передвигается одна — единственная головка. Каждая ячейка ленты может находиться в одном из состояний: ноль, единица, а также в неопределенном состоянии. На каждом шаге выполнения алгоритма головка может сдвинуться влево, сдвинуться вправо либо записать в ячейку, над которой она находится, ноль или единицу. Программа для такой машины — это сколь угодно большой, но конечный набор состояний, каждому из которых соответствует некоторое действие, а также следующее состояние. Есть два выделенных состояния — исходное, в котором начинается работа программы, и специальное состояние СТОП, которое соответствует выходу из программы.
Эта модель вычислений, получившая название детерминированной машины Тьюринга, стала общепринятой (хотя Пост придумал свою модель на год раньше). В информатике широко известно нестрогое утверждение (так называемый тезис Чёрча), которое гласит, что любой объект, отвечающий нашему интуитивному понятию алгоритма, можно реализовать в виде пр01раммы на машине Тьюринга. Контрпримеров к этому утверждению пока не

Процедура. Методы глобальной оптимизации
ц *** Выбор наилучшего из всех соседних векторов, в качестве Ц*** следующего приближения
хк+1 := соседний с хк вектор, минимизирующий значение Е(х)
// *** Проекция непрерывного вектора на булево пространство
//***ВМ{0,1}
Если ( Хк+1 близко к решению ) То Хк+і Булева_проекция(хк+і)
Конец Если
// *** Эвристика преодоления локального минимума Если (локальный_минимум ) То
хк+1 := Метод_преодоления(хк+і)
Конец Если у* := хк+1 Конец Цикла
Рис. 1.3.5 Структура методов глобальной оптимизации для задачи
ВЫПОЛНИМОСТЬ
1.3.8. Непрерывный метод Лагранжа
Выше были рассмотрены в основном дискретные подходы к решению задачи ВЫПОЛНИМОСТЬ. Все они так или иначе перебирают точки дискретной сетки. При попадании траектории поиска в локальный минимум используются различные методы выхода, такие как туннелирование, случайные рестарты. Существуют методы выхода, которые вводят фиктивные граничные условия для вывода траектории поиска за пределы локального минимума. В основном подобные методы хорошо работают для непрерывных задач и имеют трудности в применении к задаче ВЫПОЛНИМОСТЬ в чистом виде. Более перспективным представляется метод Лагранжа.
Метод Лагранжа [47], [46], [58], [72] использует непрерывную модель. Задача ВЫПОЛНИМОСТЬ записывается в виде непрерывной дифференцируемой функции и набора ограничений, обеспечивающих условие выполнимости исходной КНФ: