Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО
Дудаков, Сергей Михайлович
01.01.06
Кандидатская
2000
Тверь
139 с.
Стоимость:
499 руб.
Оглавление
Введение
1 Основные понятия и определения
1.1 Классы сложности и типы сводимости
1.2 Логические программы
2 Сложность параллельности для хорновского фрагмента линейной логики
2.1 Основные понятия линейной логики
2.2 Перестановочность, параллельность и сильная параллельность
2.3 Максимальная параллельность
3 Сложность обновлений моделей логических программ
3.1 Постановка задачи
3.2 Определения
3.3 Сложность задач при фиксированной сигнатуре
3.3.1 Вспомогательная конструкция: 1 и Т
3.3.2 Алгоритм построения обновления для хорновских ЛП
3.3.3 Ф — хорновская, Д положительно
3.3.4 Ф — хорновская, Д произвольно
3.3.5 Общий случай
3.4 Случай нефиксированной сигнатуры
4 Сложность совершенных моделей пропозициональных логических программ
4.1 Совершенные модели логических программ
4.2 Определения
4.3 Структура совершенных моделей
4.4 Нижняя оценка сложности совершенных моделей
5 О структуре полных множеств для NP и EXP
5.1 Основные понятия и определения
5.1.1 Структурная теория сложности
5.1.2 Информационная сложность проблем
5.2 Алгоритмическая сложность и плотность
NP-трудных множеств
5.3 О множествах, сводимых к множествам с большой колмого-
ровской сложностью
Заключение
Литература
Список иллюстраций
2.1 Алгоритм FINDMAX
4.1 Алгоритм PERFCONS
4.2 Алгоритм PERFC0NS1
5.1 Алгоритм RESTORE
символов у в и) равняется
к + (ах — За) +
А так как у > к + 1, то применима предпоследняя импликация.
4 случай. Предположим, применены все импликации, соответствующие числам задачи, и получена конъюнкция ии1. Тогда т' содержит не менее
п + (а — а)-
символов г. Следовательно, применима последняя импликация,
Итак, чтобы последовательность была перестановочной необходимо и достаточно, чтобы она была перестановочна на единственной нерассмот-
и Оп
реннои конъюнкции
5 случай. Рассмотрим следующую последовательность применения: выберем произвольную тройку чисел из задачи З-РАЗБИЕНИЕ с суммой равной а, применим импликации, соответствующие числам этой тройки (это будет максимальная подпоследовательность), получим уаг2а. После этого применим (уаг2а -> у%а). Заметим, что в данном случае каждый раз применяется максимальная подпоследовательность, имеющая максимально возможную длину (это будет использовано в следующем параграфе).
Если разбиение чисел а* существует, то проделав этот цикл т раз мы по-
/ Од
лучим конъюнкцию т — у , и все импликации, соответствующие числам задачи, будут использованы. Следовательно, ни одна из двух оставшихся импликаций не будет применима. Если разбиения нет, то рано или поздно соответствующую тройку найти станет невозможно. Следовательно, в результате получится конъюнкция «/, в которой или количество у будет меньше а, или количество 2 — меньше 2а. Единственная возможность — применить (г —у МАХ).
Осталось только отметить, что приведенная последовательность импли-
кации всегда применима к у
уба+аа-а, р у6а+аМАХ.
Название работы | Автор | Дата защиты |
---|---|---|
Расслоенные формации мультиоператорных Т-групп и их применения | Демина, Екатерина Николаевна | 2012 |
Группы, насыщенные прямыми произведениями конечных групп | Шлепкин, Алексей Анатольевич | 2013 |
Аддитивные задачи со степенями простых и натуральных чисел | Дашкевич, Александр Михайлович | 1984 |