Разработка и исследование параллельных комбинаторных алгоритмов

• Автор: Тимошевская, Наталия Евгеньевна
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Томск
• Количество страниц: 150 с. : ил.

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

Глава 1. Методы и алгоритмы параллельного обхода дерева

1.1. Методы обхода дерева.

1.2. Общие методы параллельного обхода.

1.2.1. Обзор методов параллельного обхода в глубину

1.2.2. Метод назначаемых поддеревьев.

1.2.3. Метод выделяемых поддеревьев

1.2.4. Экспериментальное исследование методов параллельного обхода

1.3. Параллельные алгоритмы решения комбинаторных задач обходом дерева

1.3.1. Перечисление сочетаний

1.3.2. Перечисление разбиений
1.3.3. Задача о рюкзаке
1.3.4. Задача о назначении.
Глава 2. Параллельное перечисление комбинаторных объектов методом нумерации
2.1. Формулировка метода
2.2. Параллельные алгоритмы перечисления комбинаторных объектов методом нумерации.
2.2.1. Перечисление сочетаний
2.2.2. Перечисление перестановок.
2.2.3. Перечисление разбиений
Глава 3. Параллельное решение системы логических уравнений методом линеаризационного множества.
3.1. Метод линеаризационного множества
. Параллельный алгоритм решения системы нелинейных логических
уравнений.
3.3.0 линеаризационных множествах покрытий.
3.3.1.0 линеаризационно эквивалентных покрытиях множества
3.3.2. Покрытия, соответствующие графам.
3.3.3. Задача о кратчайшем линеаризационном множестве.
3.3.4. Задача построения покрытия с линеаризационными множествами ограниченной снизу мощности.
3.3.5. Одно обобщение задачи о кратчайшем линеаризационном множестве покрытия
3.3.6. Оценки доли покрытий с линеаризационными множествами заданной мощности
Заключение
Список использованной литературы


Вторая глава посвящена методу параллельного перечисления комбинаторных объектов, в основе которого лежит возможность нумерации перечисляемых объектов так, что по номеру можно легко восстановить сопоставленный ему объект. Построенная таким образом нумерация позволяет разбить все множество объектов на классы, мощности которых отвечают производительности процессоров в системе, и генерировать объекты различных классов независимо и параллельно на соответствующих процессорах. Этот метод получил название метода нумерации. Описываются параллельные алгоритмы перечисления сочетаний, перестановок, разбиений множества методом нумерации. Во всех случаях нумерация объектов выполняется в лексикографическом порядке представляющих их векторов. Третья глава посвящена разработке и исследованию алгоритмов, в том числе параллельных, возникающих при решении систем нелинейных логических уравнений методом линеаризационного множества и исследовании криптографических свойств дискретных функций, обеспечивающих стойкость к линеаризационной атаке криптосистем, в которых они применяются. ДГ0, - булевы переменные, - булевы константы, Дхо, . Центральным понятием в методе является линеаризационное множество - подмножество переменных системы, при любой фиксации значений которых система становится линейной. Поиск набора значений переменных из линеаризационного множества, делающего систему совместной, выполняется алгоритмом, реализующим сокращенный обход бинарного дерева поиска с возвращением. Каждому ярусу дерева сопоставляется переменная из линеаризационного множества. Глубина такого дерева не превосходит мощности последнего. Дается параллельный алгоритм обхода этого дерева по методу выделяемых поддеревьев. Раздел 3. Это связано с тем, что каждой системе уравнений можно сопоставить покрытие множества ее переменных так, что любое линеаризационное множество покрытия будет линеаризационным множеством системы. В разделе 3. При решении задач, связанных с нахождением некоторого линеаризационного множества заданного покрытия, во многих случаях имеет смысл выполнить переход к эквивалентному покрытию, например, меньшей длины или меньшего веса, в связи с чем определяются безызбыточное, кратчайшее и минимальное покрытия в классе линеаризационной эквивалентности. Даются необходимое условие для кратчайшего покрытия и необходимое и достаточное условие безызбыточности покрытия, по сути, содержащее алгоритм построения последнего. Доказывается МР-трудность задачи построения кратчайшего покрытия и предлагается приближенный полиномиальный алгоритм для минимизации заданного покрытия с сохранением его линеаризационных множеств. В разделе 3. Описана композиция алгоритмов, позволяющих построить безызбыточное покрытие, эквивалентное заданному, с меньшими длиной и весом. В разделе 3. Доказывается ее А^Р-трудность. Показывается связь этой задачи с задачей поиска минимального вершинного покрытия графа, позволяющая решать задачу построения кратчайшего линеаризационного множества покрытия в некоторых частных случаях. В общем же случае для решения задачи предлагаются приближенный жадный алгоритм и алгоритм сокращенного обхода дерева поиска, сокращаемого за счет использования функции нижней оценки. Для последнего алгоритма дается его параллельная реализация по методу назначаемых поддеревьев. В связи с этим ставится задача построения покрытия с линеаризационными множествами ограниченной снизу мощности, и формулируются утверждения, открывающие возможность разрабатывать алгоритмы построения таких покрытий некоторых типов. Наконец, даются нижняя и верхняя оценки доли покрытий ^-множества с линеаризационными множествами заданной мощности к. Внедрение результатов исследований. Томском государственном университете в - г. Параллельные алгоритмы в криптоанализе шифров”, выполненного при поддержке программы «Развитие потенциала высшей школы» в г. Разработка и исследование алгоритмов построения кратчайших допустимых разбиений конечных множеств» поддержанного грантом РФФИ (4), г. Исследование и разработка математических и программных средств синтеза криптографически защищенных информационных систем» (грант ТОО-3. Минобразования РФ по фундаментальным исследованиям в области технических наук), - гг.