Разработка и исследование параллельных комбинаторных алгоритмов тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Тимошевская, Наталия Евгеньевна

• Тимошевская, Наталия Евгеньевна
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Тимошевская, Наталия Евгеньевна

Введение.

Глава 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.2. Параллельный алгоритм решения системы нелинейных логических уравнений.

3.3. О линеаризационных множествах покрытий.

3.3.1.0 линеаризационно эквивалентных покрытиях множества.

3.3.2. Покрытия, соответствующие графам.

3.3.3. Задача о кратчайшем линеаризационном множестве.

3.3.4. Задача построения покрытия с линеаризационными множествами ограниченной снизу мощности.

3.3.5. Одно обобщение задачи о кратчайшем линеаризационном множестве покрытия.

3.3.6. Оценки доли покрытий с линеаризационными множествами заданной мощности.

Введение диссертации (часть автореферата) на тему «Разработка и исследование параллельных комбинаторных алгоритмов»

Актуальность темы исследования

Под комбинаторными задачами в диссертации подразумеваются перечислительные и поисковые задачи на конечных комбинаторных множествах, элементами которых служат комбинаторные объекты, представляющие собой комбинации элементов других конечных (возможно, тоже комбинаторных) множеств - сочетания, перестановки, размещения, разбиения, покрытия, подмножества, пути в графе, линеаризационные множества переменных, решения систем логических уравнений или систем алгебраических уравнений над конечным полем и т.п. Перечислительная задача заключается в перечислении всех элементов некоторого подмножества конечного комбинаторного множества, а поисковая - в нахождении в последнем элемента с заданными свойствами. И та, и другая, как видим, имеют алгоритмический характер. Алгоритмы решения комбинаторных задач называются комбинаторными алгоритмами. В классе поисковых задач выделяются оптимизационные задачи, в которых искомый объект должен доставлять минимум (или максимум) некоторой положительной функции, заданной на комбинаторном множестве.

Потребность в решении комбинаторных задач и, следовательно, в разработке комбинаторных алгоритмов возникает во многих областях науки и техники, в том числе в таких, как автоматизированное проектирование, составление расписаний, планирование, искусственный интеллект, создание компьютерных игр, разработка сетей связи, криптография, исследование операций и др. [15,19].

То обстоятельство, что решение комбинаторной задачи подразумевает вычисления в пределах конечного множества, делает методы и алгоритмы непрерывной математики фактически не применимыми к ней. За редким исключением перебор (порождение, перечисление) элементов основного комбинаторного множества и их опробование (тестирование на принадлежность требуемому подмножеству или обладание нужным свойством) является единственным способом решения комбинаторной задачи. В этом случае элементы порождаются обычно в некотором порядке, путем преобразования текущего объекта в следующий за ним по определенным правилам. Чаще всего это делается в порядке обхода дерева поиска, представляющего собой модель комбинаторного множества. Корень дерева представляет «пустой» объект, а остальные вершины - возможные «части» объектов в комбинаторном множестве. Ветвление вершин (порождение потомков) моделирует «наращивание» частей объектов путем присоединения к ним новых элементов. Оно выполняется по правилам, свойственным каждой конкретной задаче, но таким образом, что листьями дерева представляются все возможные элементы комбинаторного множества. Полный обход дерева, состоящий в построении всех путей от корня к листьям, позволяет перечислить все элементы комбинаторного множества. Сокращенным обходом строится подмножество путей от корня к листьям, которыми представлены все объекты интересующего подмножества. Различают два метода обхода: в глубину - по схеме «влево-вперед, назад-направо» и в ширину - по схеме «направо-вперед». Первый известен как метод поиска с возвращением (backtracking), типичным представителем второго является метод ветвей и границ (branch-and-bound).

Почти все комбинаторные задачи имеют экспоненциальную сложность. Их решение требует, как правило, больших вычислительных ресурсов. В последнее время в качестве таковых все чаще используют многопроцессорные вычислительные системы (МВС). Их эффективное применение к комбинаторным задачам предполагает разработку параллельных алгоритмов решения последних с максимально возможным ускорением. Основной подход в этом направлении состоит в распараллеливании последовательных методов решения задач, означающем по существу разбиение задачи на подзадачи (в нашем случае - комбинаторного множества на подмножества, или дерева поиска на поддеревья) и в распределении подзадач (подмножеств, поддеревьев) между процессорами системы для решения каким-либо последовательным методом или, рекурсивно, для дальнейшего распараллеливания.

Проблема, однако, заключается в том, как надо разбивать задачу на подзадачи и раздавать последние процессорам так, чтобы обеспечить наивысшую степень ускорения, которое зависит от многих факторов, в том числе от неравномерной загрузки процессоров системы, от накладных расходов на коммуникации, от конкуренции процессоров за доступ к разделяемым данным, от избыточности просматриваемой области поиска и др. Более того, при одном и том же способе распараллеливания эффективность параллельного алгоритма в значительной степени зависит и от решаемой задачи, и от архитектуры МВС. Несмотря на многие сотни работ, выполненных по этой проблеме только за последние два десятка лет, эффективного решения ее на данный момент не найдено ни для МВС с общей памятью, ни для МВС с раздельной памятью, в том числе кластеров. Это справедливо в отношении не только комбинаторной задачи общего вида (с произвольным деревом поиска), но и для многих конкретных комбинаторных задач, в том числе для задач перечисления сочетаний, перестановок, разбиений, о рюкзаке и о назначении, построения кратчайшего линеаризационного множества, решения систем логических уравнений и др.

На основании выше изложенного можно утверждать, что тема диссертационной работы, посвященной исследованию и разработке параллельных алгоритмов решения комбинаторных задач, лежит в русле современного развития вычислительной дискретной математики и является актуальной.

Цель работы и задачи исследования

Целью диссертационной работы является разработка и исследование параллельных алгоритмов решения перечислительных и поисковых комбинаторных задач на вычислительных системах кластерного типа.

Для достижения указанной цели предполагается решение следующих основных задач.

1. Построение методов параллельного обхода дерева поиска в глубину, возникающего в перечислительных и поисковых комбинаторных задачах.

2. Построение метода параллельного перечисления комбинаторных объектов на основе предварительного разбиения комбинаторного множества.

3. Разработка параллельных алгоритмов перечисления сочетаний, перестановок, разбиений, решений задач о рюкзаке и о назначении методами обхода дерева и разбиения комбинаторного множества.

4. Исследование свойств линеаризационных множеств для решения систем логических уравнений.

5. Разработка параллельного алгоритма решения систем логических уравнений с заданным линеаризационным множеством на основе обхода дерева поиска.

6. Экспериментальное исследование разработанных алгоритмов решения комбинаторных задач с помощью компьютерного моделирования.

Методы исследования. Теоретические исследования используют аппарат комбинаторики, теории графов, теории вычислительной сложности, параллельных вычислений, а экспериментальные - программные средства компьютерного моделирования алгоритмов на вычислительных системах кластерного типа.

Научная новизна. Новыми являются все основные результаты, полученные в диссертации, в том числе:

- методы параллельного обхода дерева поиска в глубину - метод назначаемых поддеревьев и метод выделяемых поддеревьев, обеспечивающие высокую эффективность использования ресурсов кластерной системы;

- метод параллельного перечисления комбинаторных объектов на основе предварительного разбиения комбинаторного множества - метод нумерации, обеспечивающий равномерную загрузку процессоров кластера;

- параллельные алгоритмы решения задач перечисления сочетаний, перестановок, разбиений множества методом нумерации;

- параллельные алгоритмы перечисления сочетаний, разбиений множества, решений задач о рюкзаке и о назначении методами параллельного обхода дерева поиска;

- параллельный алгоритм нахождения кратчайшего линеаризационного множества покрытия методом назначаемых поддеревьев;

- параллельный алгоритм решения системы логических уравнений с заданным линеаризационным множеством соответствующего покрытия методом выделяемых поддеревьев;

- экспериментальные оценки эффективности данных алгоритмов.

Новыми являются также следующие вспомогательные результаты, представляющие, кроме того, самостоятельный интерес для вычислительной дискретной математики, в частности для теории логических уравнений и ее приложений:

- введено понятие эквивалентности покрытий множества, где эквивалентными считаются покрытия с одинаковыми линеаризационными множествами; предложен эффективный способ проверки эквивалентности двух покрытий с помощью их графического представления и показана связь между линеаризационным множеством покрытия и вершинным покрытием соответствующего ему графа;

- в классе эквивалентности покрытий определены понятия безызбыточного, кратчайшего и минимального покрытий; установлены необходимое и достаточное условие безызбыточности покрытия и необходимое условие для кратчайшего покрытия; описана структура класса эквивалентности, представляющая собой соотношения между подмножествами безызбыточных, кратчайших и минимальных покрытий в нем;

- доказаны iVP-трудность задачи нахождения кратчайшего линеаризационного множества и задачи построения кратчайшего покрытия, эквивалентного заданному;

- предложена композиция алгоритмов, позволяющих построить безызбыточное покрытие меньшей сложности, эквивалентное заданному;

- описан ряд конструкций и алгоритмы построения покрытий множеств с линеаризационными множествами ограниченной снизу мощности;

- получена оценка доли покрытий, для которых существует линеаризационное множество заданной мощности.

Теоретическая и практическая значимость работы. Построенные методы параллельного обхода дерева и нумерации могут применяться для разработки высокоэффективных параллельных алгоритмов решения перечислительных и поисковых комбинаторных задач, что продемонстрировано в работе на ряде конкретных задач. Разработанные параллельные алгоритмы поиска кратчайшего линеаризационного множества покрытия могут использоваться для решения систем нелинейных логических уравнений, а параллельные алгоритмы решения последних и реализующие их параллельные программы могут применяться для исследования криптографической стойкости генераторов ключевого потока. Выявленные свойства линеаризационных множеств покрытий и линеаризационно эквивалентных покрытий полезны для анализа и синтеза дискретных функций с хорошими криптографическими свойствами.

Достоверность результатов. Достоверность полученных в работе теоретических результатов и формулируемых на их основе выводов обеспечивается строгостью производимых математических выкладок. Справедливость выводов относительно эффективности разработанных алгоритмов подтверждается результатами компьютерного эксперимента.

Основные положения, выносимые на защиту.

1. Методы распараллеливания комбинаторных алгоритмов, а именно: методы назначаемых и выделяемых поддеревьев для параллельного обхода дерева поиска в глубину и метод нумерации для параллельного перечисления комбинаторных объектов.

2. Параллельные алгоритмы решения комбинаторных задач, разработанные на основе методов распараллеливания, включая задачи перечисления (сочетаний, перестановок, разбиений, решений задачи о рюкзаке) и задачи поиска (оптимального назначения, кратчайшего линеаризационного множества покрытия и решения нелинейной системы логических уравнений методом линеаризационного множества), с экспериментальными оценками их эффективности.

3. Элементы теории линеаризационных множеств покрытий в решении систем нелинейных логических уравнений, в том числе доказательства ./УР-трудности задач нахождения кратчайшего линеаризационного множества и задачи построения кратчайшего покрытия, эквивалентного заданному, понятие линеаризационной эквивалентности покрытий множества переменных и соотношения между подмножествами безызбыточных, кратчайших и минимальных покрытий в ее классе, необходимое и достаточное условие безызбыточности покрытия и необходимое условие для кратчайшего покрытия, оценка доли покрытий с линеаризационными множествами заданной мощности, алгоритмы построения безызбыточных покрытий меньшей сложности и покрытий с линеаризационными множествами ограниченной снизу мощности, и др.

Работа состоит из 3-х глав, введения, заключения и списка литературы.

Первая глава посвящена методам и алгоритмам параллельного обхода дерева поиска. Их востребованность определяется существованием ряда комбинаторных задач, при решении которых в той или иной мере используются обходы деревьев. Применение многопроцессорной вычислительной системы позволяет обход дерева распараллелить - воспроизводить одновременно несколько узлов в дереве. Основная проблема, возникающая на этом пути, состоит в таком динамическом распределении неявно заданного дерева между процессорами, при котором достигает минимума время обхода и максимизируется коэффициент эффективности использования процессоров системы. Приводятся обзор и некоторая классификация методов и алгоритмов, призванных решить эту проблему для параллельного обхода дерева в глубину, и предлагаются два метода параллельного обхода дерева - метод назначаемых поддеревьев и метод выделяемых поддеревьев. В первом методе упор делается на сокращение взаимодействия между процессорами, во втором - на равномерную загрузку процессоров системы.

Для экспериментального исследования эффективности предложенных методов и алгоритмов на большом количестве примеров разработаны программы генерации полных Личных деревьев и деревьев, возникающих при решении некоторых известных комбинаторных задач разных типов -перечислительных, поисковых и оптимизационных. Рассматриваются соответствующие конкретные задачи: перечисление сочетаний (п. 1.3.1) и разбиений множества (п. 1.3.2), задача о рюкзаке (п. 1.3.3), задача о назначении (п. 1.3.4). Основной целью разработки параллельных алгоритмов для рассмотренных в этой главе задач было исследование предложенных методов параллельного обхода дерева как в сравнении друг с другом, так и в некоторых случаях с алгоритмами, разработанными методами, не использующими дерево поиска. Однако это не исключает возможности их применения к решению реальных задач.

Вторая глава посвящена методу параллельного перечисления комбинаторных объектов, в основе которого лежит возможность нумерации перечисляемых объектов так, что по номеру можно легко восстановить сопоставленный ему объект. Построенная таким образом нумерация позволяет разбить все множество объектов на классы, мощности которых отвечают производительности процессоров в системе, и генерировать объекты различных классов независимо и параллельно на соответствующих процессорах. Этот метод получил название метода нумерации. Описываются параллельные алгоритмы перечисления сочетаний, перестановок, разбиений множества методом нумерации. Во всех случаях нумерация объектов выполняется в лексикографическом порядке представляющих их векторов. Приводятся результаты вычислительных экспериментов, которые свидетельствуют о том, что предложенный метод обеспечивает высокую эффективность параллельного перечисления комбинаторных объектов, благодаря пропорциональному распределению вычислений и отсутствию обменов данными между процессорами.

Третья глава посвящена разработке и исследованию алгоритмов, в том числе параллельных, возникающих при решении систем нелинейных логических уравнений методом линеаризационного множества и исследовании криптографических свойств дискретных функций, обеспечивающих стойкость к линеаризационной атаке криптосистем, в которых они применяются.

Метод линеаризационного множества [2] предназначен для решения систем вида: st=ft(xо, .,xn-]),t = 0,., т-\, где jt0, ., jc„i - булевы переменные, s, - булевы константы, Дх0, ., -булевы функции, представленные суммой по модулю 2 элементарных конъюнкций, t = О, ., т-\. Центральным понятием в методе является линеаризационное множество - подмножество переменных системы, при любой фиксации значений которых система становится линейной. Поиск набора значений переменных из линеаризационного множества, делающего систему совместной, выполняется алгоритмом, реализующим сокращенный обход бинарного дерева поиска с возвращением. Каждому ярусу дерева сопоставляется переменная из линеаризационного множества. Глубина такого дерева не превосходит мощности последнего. Дается параллельный алгоритм обхода этого дерева по методу выделяемых поддеревьев.

Раздел 3.3 посвящен решению задач о линеаризационных множествах покрытия и линеаризационно эквивалентных покрытиях. Это связано с тем, что каждой системе уравнений можно сопоставить покрытие множества ее переменных так, что любое линеаризационное множество покрытия будет линеаризационным множеством системы.

В разделе 3.3.1 вводятся понятия линеаризационного множества покрытия и линеаризационно эквивалентных покрытий множества. Предлагается эффективный способ проверки эквивалентности двух покрытий с помощью их графового представления. При решении задач, связанных с нахождением некоторого линеаризационного множества заданного покрытия, во многих случаях имеет смысл выполнить переход к эквивалентному покрытию, например, меньшей длины или меньшего веса, в связи с чем определяются безызбыточное, кратчайшее и минимальное покрытия в классе линеаризационной эквивалентности. Даются необходимое условие для кратчайшего покрытия и необходимое и достаточное условие безызбыточности покрытия, по сути, содержащее алгоритм построения последнего. Доказывается ./VP-трудность задачи построения кратчайшего покрытия и предлагается приближенный полиномиальный алгоритм для минимизации заданного покрытия с сохранением его линеаризационных множеств.

В разделе 3.3.2 вводится понятие покрытия, соответствующего графу и предлагается алгоритм построения соответствующего графу покрытия, мощность и вес которого не больше, чем соответственно мощность и вес множества ребер графа. Описана композиция алгоритмов, позволяющих построить безызбыточное покрытие, эквивалентное заданному, с меньшими длиной и весом.

В разделе 3.3.3 рассматривается задача о кратчайшем линеаризационном множестве покрытия. Доказывается ее ^VP-трудность. Показывается связь этой задачи с задачей поиска минимального вершинного покрытия графа, позволяющая решать задачу построения кратчайшего линеаризационного множества покрытия в некоторых частных случаях. В общем же случае для решения задачи предлагаются приближенный жадный алгоритм и алгоритм сокращенного обхода дерева поиска, сокращаемого за счет использования функции нижней оценки. Для последнего алгоритма дается его параллельная реализация по методу назначаемых поддеревьев.

В некоторых приложениях, в частности при синтезе поточных шифров, стойких к линеаризационной атаке [2], возникает задача построения функции или системы функций, не имеющей линеаризационного подмножества аргументов малой мощности. В связи с этим ставится задача построения покрытия с линеаризационными множествами ограниченной снизу мощности, и формулируются утверждения, открывающие возможность разрабатывать алгоритмы построения таких покрытий некоторых типов. Наконец, даются нижняя и верхняя оценки доли покрытий «-множества с линеаризационными множествами заданной мощности к.

Внедрение результатов исследований. Результаты диссертации внедрены:

1) в разработку тем курсовых и дипломных работ в Томском государственном университете в 2004-2006 г.г. (разработка параллельных алгоритмов генерации простых чисел, факторизации числа, решения задач коммивояжера и о выполнимости КНФ);

2) в курсы лекций «Криптографические методы защиты информации», «Методы криптоанализа», «Высокопроизводительные вычислительные системы» и «Комбинаторные алгоритмы» для студентов-математиков ТГУ по специальности 090102 «Компьютерная безопасность» и используются в лабораторных работах по этим курсам;

3) в создание программного обеспечения, предназначенного для исследования стойкости ряда криптосистем, в рамках проекта №38025 "Параллельные алгоритмы в криптоанализе шифров", выполненного при поддержке программы «Развитие потенциала высшей школы» в 2005г.;

4) в разработку методов распараллеливания комбинаторных алгоритмов в рамках проектов «Разработка и исследование алгоритмов построения кратчайших допустимых разбиений конечных множеств» поддержанного грантом РФФИ (01-01-00774), 2003 г. и «Исследование и разработка математических и программных средств синтеза криптографически защищенных информационных систем» (грант ТОО-3.1-2851 Минобразования РФ по фундаментальным исследованиям в области технических наук), 20012002 гг.

Личный вклад автора.

Все результаты, представленные в диссертационной работе, получены автором лично.

Апробация работы.

Основные результаты работы докладывались и обсуждались на IV Всероссийской конференции с международным участием «Новые информационные технологии в исследовании дискретных структур» (Томск, 2002), на международных научно-практических семинарах «Высокопроизводительные параллельные вычисления на кластерных системах» (Нижний Новгород, 2001, 2003), на II - V Сибирских научных школах-семинарах с международным участием «Компьютерная безопасность и криптография» (Томск, 2003; Иркутск, 2004; Томск, 2005; Шушенское, 2006), на 2-й и 3-й Сибирских школах-семинарах по параллельным вычислениям (Томск, 2003, 2005), на XV Международной школе-семинаре "Синтез и сложность управляющих систем" (Новосибирск, 2004), на X Юбилейной Международной научно-практической конференции студентов, аспирантов и молодых ученых «Современные техника и технологии СТТ'2004», посвященной 400-летию г. Томска (Томск, 2004), на XIV международной конференции «Проблемы теоретической кибернетики», посвященной 80-летию со дня рождения С. В. Яблонского (Пенза, 2005), а также на научных семинарах кафедры защиты информации и криптографии Томского госуниверситета.

Публикации.

Основные результаты диссертации опубликованы в работах [А1 - А15].

Структура и объем работы.

Диссертация состоит из введения, трех глав, заключения и списка литературы, насчитывающего 40 наименований, изложена на 150 страницах, содержит 32 иллюстраций и 3 таблицы.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Тимошевская, Наталия Евгеньевна

Выводы к главе 3

1. Продемонстрировано применение метода выделяемых поддеревьев для разработки параллельного алгоритма решения системы нелинейных логических уравнений методом линеаризационного множества. Даны алгоритмы работы управляющего и рабочих процессов, учитывающие особенности распараллеливания обхода для бинарного дерева поиска.

2. Введено понятие эквивалентности покрытий множества (с одинаковыми линеаризационными множествами) и предложен эффективный способ проверки эквивалентности двух покрытий с помощью их графического представления. Показана связь между линеаризационным множеством покрытия и вершинным покрытием, соответствующего ему графа.

3. Даны определения безызбыточного, кратчайшего и минимального покрытий. Установлены необходимое и достаточное условия безызбыточности покрытия и необходимое условие для кратчайшего покрытия. На их основе выявлена структура классов эквивалентности покрытий.

4. Предложен алгоритм построения покрытия, соответствующего графу, мощность и вес которого не больше, чем соответственно мощность и вес множества ребер графа. Разработан алгоритм, позволяющий построить безызбыточное покрытие, эквивалентное заданному, с меньшими длиной и весом.

5. Доказана ТУР-трудность задачи о кратчайшем линеаризационном множестве покрытия. Для этой задачи предложены приближенный жадный алгоритм и алгоритм перебора, сокращаемого за счет использования функции нижней оценки, который применим для нахождения как приближенного, так и точного решений.

6. Разработан по методу назначаемых поддеревьев и исследован в компьютерном эксперименте параллельный алгоритм построения кратчайшего линеаризационного множества покрытия. Показано, что средняя эффективность алгоритма равна 0,9.

7. Сформулированы и доказаны утверждения, позволяющие строить покрытия различных типов с линеаризационными множествами мощности не меньше к, а именно, покрытия, соответствующие: графу с (£+1)-кликой; полному двудольному графу, в котором мощность меньшей доли равна к; графу из г компонент связности, в каждой компоненте которого есть клика мощности г kt (z = l,.,r) и к = Предложен алгоритм, строящий покрытие, 1 соответствующее графу с (&+1)-кликой.

8. Даны оценки доли покрытий с линеаризационными множествами заданной мощности, которые показывают, что доля покрытий с нетривиальными линеаризационными множествами ничтожна мала, но их количество велико и растет с ростом мощностей покрываемого и линеаризационного множеств, оправдывая постановку задачи поиска линеаризационных множеств для них.

Заключение

Перечислим основные результаты работы.

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

- метод назначаемых поддеревьев;

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

2. Параллельные алгоритмы, разработанные по методам назначаемых и выделяемых поддеревьев, для решения задач:

- перечисления сочетаний;

- перечисления разбиений множества;

- перечисления подмножеств с заданной суммой;

- поиска оптимального назначения.

3. Метод нумерации для разработки параллельных алгоритмов перечисления.

4. Построенные по методу нумерации параллельные алгоритмы перечисления: сочетаний, перестановок, разбиений множества.

5. Разработанный по методу выделяемых поддеревьев параллельный алгоритм решения системы логических уравнений методом линеаризационного множества.

6. Разработанный по методу назначаемых поддеревьев параллельный алгоритм поиска кратчайшего линеаризационного множества для произвольного покрытия.

7. Элементы теории линеаризационных множеств для покрытий:

- тест линеаризационной эквивалентности покрытий;

- необходимое и достаточное условия безызбыточности покрытия;

- необходимое условие для кратчайшего покрытия;

- Л^-трудность задачи поиска кратчайшего покрытия;

- алгоритм построения покрытия с определенными свойствами, эквивалентного заданному покрытию;

- структура класса эквивалентности покрытий;

- оценка доли покрытий с линеаризационными множествами заданной мощности.

- NP- трудность задачи поиска кратчайшего линеаризационного множества;

- оценки мощности линеаризационных множеств для некоторых классов покрытий.

Список литературы диссертационного исследования кандидат технических наук Тимошевская, Наталия Евгеньевна, 2007 год

1. Агибалов Г. П., Беляев В. А. Технология решения комбинаторно-логических задач методом сокращённого обхода дерева поиска. Томск: Изд-во Том. ун-та, 1981. - 125 с.

2. Агибалов Г.П. Логические уравнения в криптоанализе генераторов ключевого потока//Вестник ТГУ. Приложение. -2003.-№ 6.-С. 31—41.

3. Алексеев В. Б. Введение в теорию сложности алгоритмов (учебное пособие для студентов) М.: Издательский отдел ф-та ВМ и К МГУ, 2002. - 82 с.

4. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. - 608 с.

5. Галактифонов М. С. AIDA*: параллельная версия алгоритма и его реализация на вычислительном кластере // Третья Сибирская школа-семинар по параллельным вычислениям. Тезисы. Томск: Изд-во Том. ун-та.-2005.-С. 14.

6. Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. Учебное пособие. -Нижний Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2000. 176 с.

7. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Пер. с англ. М.: Мир, 1982. - 416 с.

8. Дейкстра. Э. Дисциплина программирования. М.: Мир, 1978. - 280 с.

9. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. -М.: МЦНМО, 2001.-955 с.

10. Корнеев В. Д. Параллельное программирование в MPI. Новосибирск: Изд-во Сибирского отделения РАН, 2002. - 214 с.

11. Кнут Д. Искусство программирования для ЭВМ, т.1. М.: Мир, 1976. -734 с.

12. Липский В. Комбинаторика для программистов. М.: Мир, 1988. - 200 с.

13. Малышкин В.Э. Параллельное программирование мультикомпьютеров: Учебное пособие. Ярославль: Яросл. гос. ун-т, 1999. - 135 с.

14. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы, теория и практика. М.: Мир, 1980. - 476 с.

15. Саломаа А. Криптография с открытым ключом. Пер. с англ. М.: Мир, 1989.-264 с.

16. Сачков В.Н. Введение в комбинаторные методы дискретной математики. М.: МЦНМО, 2004. - 424 с.

17. Семенов В.В. Алгоритмы параллельного перечисления разбиений множества // Третья Сибирская школа-семинар по параллельным вычислениям / Под ред. А. В. Старченко. Томск: изд-во Том. ун-та, 2006.-С. 73-76.

18. Ху Т. Ч., Шинг М.Т. Комбинаторные алгоритмы. Пер. с англ. Нижний Новгород: Изд-во Нижегородского университета им. Н.И. Лобачевского, 2004.-330 с.

19. Feldman R., Monien В. and Mysliwietz P. A fully distributed chess program // Advances in Computer Chess VI. 1991. - pp. 1 - 27.

20. Ferguson C. and Korf R. Distributed tree search and its application to alpha-beta pruning // Proceedings of the 1988 National Conference on Artificial Intelligence. 1988.

21. Finkel R. A. and Udi Manber. DIB a distributed implementation of backtracking // ACM Transactions of Programming Languages and Systems. -1987.-9.-№2.-pp. 235-256.

22. Gao Y. and Marsland T. A. Multithreaded Pruned Tree Search in Distributed Systems // Journal of Computing and Information. 1996. - 2(1). - pp. 482 -492.

23. Grama A. and Kumar V. Parallel processing for discrete optimization problem // Encyclopedia of microcomputers. 1992. - pp. 129-157.

24. Grama A. and Kumar V. A survey of parallel search algorithms for discrete optimization problems // ORSA Journal of Computing. 1995. - 7(4). - pp. 365-385.

25. Kumar V. and Nageshwara V. Rao. Parallel depth-first search. Part II: Analysis // International Journal of Parallel Programming. 1987. - 16(6). -pp. 501-519.

26. Kumar V., Grama A., Nageshvara V. Rao. Scalable load balancing techniques for parallel computers // Journal of Parallel and Distributed Computing. -1994.-22(1).-pp. 60-79.

27. Orlin J. Contentment in graph theory: covering graphs with cliques // Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen. Series A: Mathematical Sciences. 1977. - Vol. 80. - pp. 406 - 424.

28. Rao V. N. and Kumar V. Parallel depth-first search. Part I: Implementation // International Journal of Parallel Programming. 1987. - 16(6). - pp. 479-499.

29. Rao V. N. and Kumar V. On the Efficiency of Parallel Backtracking // IEEE Trans. Parallel Distrib. Syst. 1993. - 4(4). - pp. 427-437.

30. Ranade A.G. Optimal speedup for backtrack search on a butterfly network // Proceedings of the Third ACM Symposium on Parallel Algorithms and Architectures. -1991.

31. Reinefeld A. and Schnecke. V. Work-Load Balancing in Highly Parallel Depth-First Search // Proc. Scalable High Perf. Сотр. Conf. SHPCC'94,

32. Knoxville. 1994. - pp. 773 - 780.

33. Saletore V. and Kale L.V. Consistent linear speedup to a first solution in parallel state-space search // Proceedings of the 1990 National Conference on Artificial Intelligence. 1990. - pp. 227-233.

34. Sanders Peter. Better Algorithms for Parallel Backtracking. In Workshop on Algorithms for Irregularly Structured Problems // LNCS. 1995. - 980. - pp. 333-347.

35. Sanders Peter. Parallelizing NP-complete problems using tree shaped computations // Journees de l'lnformatique Messine (JIM). 1999.

36. Shu W. and Kale L.V. A dynamic scheduling strategy for the share-kernel system // Proceedings of SuperComputing Conference. 1989. - pp. 389 -398.

37. Публикации автора по теме диссертации

38. А2. Тимошевская Н.Е. О распараллеливании обхода дерева поиска // Вестник Томского госуниверситета. Приложение. 2002. -№ 1(11). - С. 241 -245.

39. A3. Тимошевская Н.Е. О параллельных алгоритмах обхода дерева // Вестник Томского госуниверситета. Приложение. 2003. - № 6. - С. 202 - 209.

40. А6. Тимошевская Н.Е. Параллельные методы обхода дерева // Математическое моделирование. 2004. - Том 16. - №1. - С. 105 - 114.

41. А7. Тимошевская Н.Е. Параллельная генерация сочетаний и перестановок. // Вторая Сибирская школа-семинар по параллельным вычислениям / Под ред. А. В. Старченко. Томск: изд-во Том. ун-та, 2004. - С. 55 - 59.

42. А8. Тимошевская Н.Е. Экспериментальное исследование стойкости сжимающего генератора // Вестник Томского госуниверситета. Приложение. 2004. - № 9(1). - С. 84 - 88.

43. А9. Гисс С.С., Тимошевская Н. Е. Распараллеливание алгоритма решения задачи о выполнимости КНФ // Вторая Сибирская школа-семинар по параллельным вычислениям / Под ред. А. В. Старченко. Томск: изд-во Том. ун-та, 2004. - С. 65 - 66.

44. АЮ.Тимошевская Н.Е. О нумерации перестановок и сочетаний для организации параллельных вычислений в задачах проектирования управляющих систем // Известия Томского политехническогоуниверситета. 2004. - Том 307. - №6. - С. 18 - 20.