Оглавление
Введение
1 Основные понятия
1.1 Логическое программирование.
1.2 Сложностныс классы .
2 Обновления баз данных при динамических ограничениях целостности
2.1 Проблема наименьших достаточных изменений
базы данных
2.2 Базы данных со статическими и динамическими ограничениями целостности ОЦ.
2.2.1 Ограничения целостности
2.2.2 Допустимые состояния и переходы .
2.2.3 Обновления БД
2.3 Консервативные обновления и проблема наименьших достаточных изменений ИДИ.
2.3.1 Совместность обновлений и ограничений целостности
2.3.2 Консервативные операторы обновлений.
2.4 Консервативные обновления для статических ОЦ .
2.4.1 Сложность проблем разрешения.
2.4.2 Алгоритмы для проблем НДИ и ПНДИ в статическом
случае.
2.5 Проблемы ИДИ и ПНДИ для полных БД
с динамическими ОЦ
2.5.1 Недетерминированные алгоритмы и сложность проблемы НДИ
2.5.2 Алгоритм для проблемы ПНДИ
2.6 Задачи поиска НДИ для частичных БД
2.7 Операторы расширения обновлений.
2.7.1 Обобщенные обновления и их расширения
2.7.2 Упрощение ограничений целостности
2.7.3 Прямой и обратный операторы расширения обновлений
2.8 Максималыюе расширение обновлений для
частичных БД.
2.9 Максимальные расширения для полных БД
3 Анализ поведения дедуктивных баз данных
3.1 Поведение дискретных интерактивных систем
3.2 Дедуктивные базы данных с обновлениями
3.2.1 Логические программы с обновлениями синтаксис . .
3.2.2 Логические программы с обновлениями семантика .
3.2.3 Классы ДБД и алгоритмические проблемы.
3.2.4 Примеры
3.3 Сложность проблемы перспективности
3.4 Сложность проблемы стабильности
3.4.1 стабильность .
3.4.2 Уфстабильность
3.4.3 ЗУстабильность
3.5 Сложность проблемы гомеостатичности
3.6 Сложность тотальной гомеостатичности
4 Анализ поведения мультиагентных систем
4Л Агенты и мультиагентные системы
4ЛЛ Архитектура и семантика МАсистем типа I .
4Л.2 Логики для описания свойств МАсистем.
4.2 Пример МАсистемы распределение ресурсов .
4.3 Поведение детерминированных МАсистем
4.3.1 Алгоритм проверки для детерминированных МАсистем
4.3.2 Сложность верификации
4.4 Поведение недетерминированных МАсистем
4.5 Вероятностные МАсистемы.
4.5.1 Неопределенность в МАсистем ах.
4.5.2 Синтаксис вероятностных МАсистем
4.5.3 Семантика вероятностных МАсистем.
4.5.4 Вычисление вероятностей переходов.
4.5.5 Верификация динамических свойств .
5 Семантика логических программ с интервальными вероятностями
5.1 Введение.
5.2 Интервальные вероятностные логические программы
5.2.1 Синтаксис.
5.2.2 Семантика возможных миров
5.2.3 Пробпема совместности
5.2.4 Семантика неподвижной точки и ее недостаточность
5.3 Семантика возможных миров описание и вычисление
5.3.1 Модели программ
5.32 Простые программы характеризация моделей . .
5.3.3 Простые программы явное вычисление моделей .
5.4 Когда неподвижной точки достаточно.
6 Семантика и сложность языка Рефал
6.1 Синтаксис и операционная семантика Рефала .
6.2 Денотативная семантика Рефалпрограмм
6.2.1 Рекурсивные программы и правила вычисления неподвижной точки.
6.2.2 Когда неподвижная точка вычисляется вызовами по значению
6.2.3 Вложение Рсфала в рекурсивные программы
6.2.4 О доказательстве свойств Рефалпрограмм .
6.3 Сложность одного шага Рсфалмашины
7 Сложностные спектры рекурсивных множеств и аппроксимируемость начальных отрезков полных проблем
7.1 Аппроксимация как метод решения сложных проблем
7.2 Основные обозначения и определения.
7.3 Сложностные спектры рекурсивных множеств.
7.4 Сводимость и аппроксимируемость
7.5 Нижние оценки аппроксимируемости трудных
проблем
7.6 Приложение к сложности схем и логических
систем.
7.7 Плотность полных проблем и сводимость к редким множествам
7.8 Нижние границы аппроксимируемости и ускорение вычислений
Литература
- Київ+380960830922