Введение
ГЛАВА 1. Задачи выполнимости и удовлетворения ограничений, генерация конечных автоматов 15
1.1. Задачи выполнимости и удовлетворения ограничений 15
1.1.1. Методы решения задач выполнимости и удовлетворения ограничений 16
1.1.2. Программные средства решения SAT и CSP
1.2. Конечные автоматы 26
1.3. Методы генерации конечных автоматов
1.3.1. Эвристические методы генерации конечных автоматов 34
1.3.2. Методы генерации, основанные на метаэвристических алгоритмах 39
1.3.3. Методы генерации, основанные на сведении к задачам из класса трудных в NP 43
1.4. Задачи, решаемые в диссертационной работе 49
Выводы по главе 1 52
Глава 2. Теоретическая оценка сложности поставленных задач генерации управляющих автоматов 53
2.1. Доказательство принадлежности поставленной задачи классу np-трудных 53
2.2. Условие принадлежности рассматриваемой задачи классу np 56
Выводы по главе 2 57
ГЛАВА 3. Генерация детерминированных конечных автоматов по обучающим словарям 58
3.1. Метод генерации по безошибочным обучающим словарям 58
3.1.1. Структура метода 58
3.1.2. Предикаты нарушения симметрии 60
3.2. Метод генерации по зашумленным обучающим словарям 65
3.2.1. Структура метода 66
3.2.2. Предикаты обработки ошибочных пометок 67
3.3. Реализация и экспериментальные Исследования разработанных
методов генерации 70
3.3.1. Реализация разработанных методов генерации ДКА 70
3.3.2. Экспериментальные исследования метода генерации ДКА по безошибочным обучающим словарям 73
3.3.3. Экспериментальные исследования метода генерации ДКА по зашумленным обучающим словарям 77
вывоДы по главе 3 79
ГЛАВА 4. Генерация управляющих конечных автоматов по сценариям работы 81
4.1. Метод генерации управляющих конечных автоматов по безошибочным сценариям работы 81
4.1.1. Структура метода 82
4.1.2. Построение дерева сценариев и графа совместимости 83
4.1.3. Ограничения на целочисленные переменные 89
4.1.4. Предикаты нарушения симметрии 92
4.2. Метод генерации по зашумленным сценариям работы 95
4.2.1. Структура метода 95
4.2.2. Ограничения на целочисленные переменные 97
4.3. Реализация и экспериментальные исследования методов 100
4.3.1. Программное средство генерации конечных управляющих автоматов 100
4.3.2. Экспериментальные исследования метода генерации управляющих автоматов по безошибочным сценариям работы 102
4.3.3. Экспериментальные исследования метода генерации управляющих автоматов по зашумленным сценариям работы 106
Выводы по главе 4 108
ГЛАВА 5. Внедрение результатов работы 110
5.1. Внедрение разработанных предикатов нарушения симметрии в
Средство dfasat 110
5.2. Внедрение в образовательный процесс 111
Выводы по главе 5 111
Заключение 112
Список источников 113
Печатные издания на русском языке 113
Печатные издания на английском языке 114
Ресурсы сети интернет 120
Публикации автора 122
Статьи в рецензируемых изданиях из перечней ВАК или Scopus 122
Другие публикации по теме 123
Приложение 1. Свидетельства о регистрации программ
Для эвм 125
Приложение 2. Акт, подтверждающий внедрение и
Использование результатов диссертационной работы в
Программное средство dfasat
