автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Разработка и исследование параллельных комбинаторных алгоритмов

На правах рукописи

Тимошевская Наталия Евгеньевна

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ПАРАЛЛЕЛЬНЫХ КОМБИНАТОРНЫХ АЛГОРИТМОВ

05 13.01 - Системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и автоматизации)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Томск-2007

151В

003071518

Работа выполнена на кафедре защиты информации и криптографии ГОУ ВПО «Томский государственный университет»

< I

Научный руководитель- доктор технических наук,

профессор Агибалов Геннадий Петрович

Официальные оппоненты доктор технических наук,

профессор Костюк Юрий Леонидович

кандидат технических наук, Семенов Александр Анатольевич

Ведущая организация- Институт вычислительной математики и

математической геофизики СО РАН, Новосибирск

Защита состоится 24 мая 2007 г в 12 00 на заседании Диссертационного совета Д 212 267 12 при ГОУ ВПО «Томский государственный университет» по адресу 634050, г. Томск, пр. Ленина, 36

С диссертацией можно ознакомиться в Научной библиотеке Томского государственного университета по адресу г Томск, пр Ленина, 34а

Автореферат разослан 23 апреля 2007 г.

Ученый секретарь диссертационного совета, д т н, профессор Смагин В И

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность проблемы. Потребность в решении комбинаторных задач и, следовательно, в разработке комбинаторных алгоритмов возникает во многих ' областях, в том числе таких, как автоматизированное проектирование, создание систем искусственного интеллекта, разработка сетей связи и криптография. Под комбинаторными задачами в диссертации подразумеваются перечислительные и поисковые задачи на конечных комбинаторных множествах, элементами которых служат комбинаторные объекты, представляющие собой комбинации элементов других конечных (возможно, тоже комбинаторных) множеств - сочетания, перестановки, разбиения, покрытия, линеаризационные множества переменных, решения систем логических уравнений и т п Перечислительная задача заключается в перечислении всех элементов некоторого подмножества конечного комбинаторного множества, а поисковая — в нахождении в последнем элемента с заданными свойствами За редким исключением перебор (порождение, перечисление) элементов основного комбинаторного множества и их опробование (тестирование на принадлежность требуемому подмножеству или обладание нужным свойством) является единственным способом решения комбинаторной задачи В этом случае элементы порождаются обычно в некотором порядке Во многих случаях это делается в порядке обхода дерева поиска, представляющего собой модель комбинаторного множества

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4) в разработку методов распараллеливания комбинаторных алгоритмов в рамках проектов «Разработка и исследование алгоритмов построения

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

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

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

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и библиографии, включающей 40 наименований, её объем - 150 стр

СОДЕРЖАНИЕ РАБОТЫ В главе 1 дается обзор результатов исследований, в основном зарубежных авторов, по параллельному обходу дерева и на его основе строится классификация существующих методов такого обхода Указывается место результатов автора в этой классификации

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

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

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

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

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

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

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

Таким образом, МВП позволяет обеспечить равномерную загруженность процессов системы, однако требует дополнительных накладных расходов на выделение поддеревьев

Предложенные методы исследовались экспериментально на полных к-ичных деревьях. Целью эксперимента являлась оценка величин ускорения и эффективности На практике ускорение определяется отношением времени решения задачи на одном процессоре ко времени решения той же задачи на системе таких же процессоров, а эффективность — отношением ускорения к числу процессоров Эффективность показывает среднюю долю времени выполнения программы, в течение которого процессоры реально используются для решения задачи, и не превышает 1 Для программной реализации разработанных в диссертации параллельных алгоритмов использовались язык С++ и функции библиотеки MPI, представляющей собой стандартизованный набор средств для обмена сообщениями между процессорами Компьютерное моделирование алгоритмов проводилось в основном на вычислительном кластере Томского госуниверситета, состоящем из 9 двухпроцессорных узлов Результаты проведенного эксперимента показывают, что 1) эффективность для обоих методов зависит от размера дерева, а именно- по мере увеличения числа узлов в дереве эффективность возрастает и стабилизируется в среднем около 0,85; 2) при достаточно большом числе процессов (более 10) эффективность в среднем равна 0,88 для МНП и 0,89 для МВП

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

Дерево, используемое для перечисления сочетаний, интересно своей структурой, в том смысле, что в нем встречаются как поддеревья с очень большим числом вершин, так и много поддеревьев, небольших по числу вершин, более того, имеющих линейную структуру. В работе представлены пошаговые алгоритмы, описывающие действия управляющего и рабочих процессов при использовании МНП и МВП для параллельного обхода дерева В частности, для МВП алгоритм включает операции выделения поддерева, число которых в данной задаче невелико В экспериментах испытывались различные деревья сочетаний из п по к, в том числе содержащие максимальное для заданного п число концевых вершин (например, п = 40, к = 20), «глубокие» (л = 100, к = 93) и «широкие» (и = 100, к — 8) Результаты показали, что для МНП при правильном выборе числа m назначаемых поддеревьев почти во всех случаях достигаются достаточно равномерная загрузка рабочих процессов и высокая эффективность (для 16 процессов » 0,9) Для деревьев с числом узлов Ю10 - 10" наиболее

подходящим оказалось значение т порядка 105 Исключение составляют «глубокие» деревья Причина в том, что, например, для п = 100, к = 93 и при значении т порядка 105 одно из назначаемых поддеревьев содержит примерно половину всех сочетаний, а при т порядка 106 - одну йятую Средняя достигнутая эффективность при использовании МВП также достаточно высока (» 0,86), в том числе и для «глубоких» деревьев

В основе параллельных алгоритмов перечисления разбиений множества лежит рекурсивный алгоритм обхода в глубину дерева, каждая вершина в котором представляет разбиение некоторого подмножества Экспериментальным путем установлено, что для достижения эффективности, близкой к 1, число корневых вершин в МНП должно быть порядка 105 для разбиений множеств мощности 15, 16, 17 и порядка 106 - для мощности 18 Для МВП проведено исследование влияния условия разбиения, определяющего минимальную высоту выделяемого поддерева, на ускорение вычислений Наилучшие результаты (эффективность = 0,9) получены при запрете на выделение поддеревьев высотой меньше 6

В классе задач поиска комбинаторных объектов с заданными свойствами рассмотрена задача о рюкзаке в следующей постановке заданы натуральное число со и набор неотрицательных чисел В = (Ьь Ь2, , Ь„), требуется найти, если они существуют, все такие подмножества , с {1, , п}, для которых

' = а При решении этой задачи методом поиска с возвращением выполняется

л. I '

обход в глубину дерева, которое, в отличие от деревьев для сочетаний и разбиений, не имеет определенной (заранее предсказуемой) структуры Для его распараллеливания использовались оба метода В МНП средняя эффективность получилась равной 0,86 для 12 процессов Для параллельного алгоритма, разработанного по МВП, исследовались две версии, отличающиеся друг от друга условием разбиения В первой указывался максимальный номер яруса А/, на котором может быть расположена корневая вершина выделяемого поддерева, во второй - минимальное число узлов N в разбиваемом поддереве Для оценки числа узлов в поддереве использовался метод Монте-Карло Экспериментальный анализ показал, что вторая версия алгоритма не дает предполагаемого выигрыша по сравнению с первой При хорошем подборе значений М и N в первой и второй версиях в среднем получаются одинаковые результаты по времени, но худшие, чем для МНП

Задача о назначении, состоящая в нахождении для заданных положительных чисел <з,у перестановки (¿ь к2, , к„) чисел 1,2, , п с минимальным значением

л

целевой функции IV , относится к классу задач поиска оптимального

1=1 '

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

обхода дерева некоторым из процессов лучшего решения соответствующее ему значение W следует обновить у всех процессов, что в многопроцессорных системах, не имеющих общей памяти, требует явной передачи Если рабочий процесс находит в" своем поддереве назначение со стоимостью W' < W, то заменяет W на W' и пересылает W' управляющему процессу Обновление значения целевой функции в МНП выполняется управляющим процессом только с назначением очередного поддерева, а в МВП сразу же после получения Результаты экспериментального анализа показали, что при решении данной задачи преимущество имеет МНП

Глава 2 посвящена параллельному перечислению комбинаторных объектов методом нумерации Схема алгоритма перечисления строится обычно по следующим правилам на множестве перечисляемых объектов вводится некоторый порядок, описывается способ преобразования текущего объекта в следующий за ним и формулируется условие окончания перечисления Для распараллеливания данной схемы множество перечисляемых объектов можно предварительно разбить на классы, мощности которых отвечают производительности процессоров в системе, и перечислять объекты в различных классах независимо и параллельно на соответствующих процессорах Однако, когда речь идет о множестве комбинаторных объектов, в отличие, скажем, от числового множества, провести такое разбиение в явном виде не представляется возможным Решение этой проблемы возможно путем сопоставления перечисляемым комбинаторным объектам элементов некоторого "легко разбиваемого" множества Самый простой способ состоит в нумерации комбинаторных объектов числами 1,2, в соответствии с установленным на множестве объектов порядком Последний, естественно, должен допускать восстановление объекта по его номеру, причем время, требуемое на восстановление, должно быть пренебрежимо мало по сравнению со временем, затрачиваемым на перечисление всех объектов одного класса Предложенный метод нумерации параллельного перечисления комбинаторных объектов включает метод построения объекта по его номеру в заданном порядке

Пусть объекты задаются векторами конечной длины вида (аь а2, , а„) с компонентами из конечных упорядоченных множеств А\, Л2, , А„ (сг,еА,) Будем считать, что объекты упорядочены в соответствии с лексикографическим порядком представляющих их векторов, и их нумерация начинается с 1 Требуется найти объект с номером /

Искомый объект строится покомпонентно вначале вычисляется аь затем а2, и т д Пусть р = (а 1, а2, , а, _ ,) уже известный префикс искомого объекта (представляющего объект вектора) и N — номер первого объекта с таким префиксом Обозначим Z{p) = {zu z2, , zr} с А, множество значений, которые может принимать элемент а, при заданном префиксе р Множество объектов с префиксом р можно разбить на классы объектов с префиксами (pzj для всех j = 1, , г Пусть N(p) есть число всех векторов, имеющих префикс р Тогда, если для некоторого целого к между! и |Z(p)|

N + ZNipz,) <I<N+i]N(pz ), (*)

м j=i

то в объекте с номером / элемент с номером / есть а, = zj

Таким образом, в методе нумерации вычисление объекта по его номеру 1 включает следующие шаги,

\.р-.-0,Щр) 1

2, Найти такое к, что 1 йкй \Z(p)\ и верно (*)

№

4 Вычислить Z(p) = {zu z2, , zr)

5. Если Z{p) = 0, то искомый объект представлен вектором р, конец,

иначе перейти в п 2 Для применения метода к конкретным комбинаторным объектам требуется уметь вычислять число N(p) и множество Z(p)

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

Представляющий вектор для сочетания из и по А: есть вектор Ь2, , Ьк) длины к < п с компонентами в {1, 2, и}, в котором Ь, < bl+i для г = 1, ,к- 1 Для сочетаний из п по к имеет место Z(b\, b2, , Vi) = {¿>/-i + 1, Ь,л + 2, , п -

(n — b 4

к +1} nN(b\, bi, ,6M)= Г

IА-/ + 1

, где b0 = 0.

Обозначим slj число всех сочетаний с префиксами (Ь\, 62, , £>м> г), гДе

J—1 (п-г\ „ , й

г е{6м+1, ¿/-1+2, ,у —1} Имеем .у' = £ Пусть также .$' = •

1 г=6,.1+1\ - '

Теорема 2.1. Пусть 1 <г<к и (Ь\, Ь2, , Ь,л) есть префикс сочетания с номером I, тогда элемент Ь, этого сочетания равен наименьшему из таких у, что

и /< л' + , если такие у существуют, и Ь, = п — к + < в

противном случае

В алгоритме параллельного перечисления перестановок методом нумерации требуется построить все перестановки (аь , а„) элементов множества А - {1,2, , и} Для таких перестановок Z(a^, , ам) = А — {аь , ам} и ЛГ(аь , ам) = («-< + 1)'

Обозначим М, число перестановок с префиксом (01, , аь|), номера которых не превосходят /, - кратность префикса Имеем М0= / и М,= М,л- (А-1)(и—

Теорема 2.2. Пусть 1 < I < п - 1, (аь , а(1) - префикс перестановки с номером 1 и М,_1 - его кратность Пусть также , у„-1-ц} = М- {«ь , ам} и

у 1 < ..< уп-1+1 Тогда элемент а, в перестановке с номером I есть ук для к = |_(Л/,

Далее описывается применение метода нумерации к перечислению разбиений множества А = {ах, а2, , а„} Пусть в нем элементы упорядочены некоторым фиксированным образом Будем также фиксировать порядок блоков в любом разбиении множества А и представлять разбиение Я вектором р - (рь р2, , р„), в котором р, есть номер блока, содержащего элемент а,, причем р, < I Таким образом, всегда р\ = 1. При таком представлении любое разбиение множества однозначно определяется своим представляющим вектором, и перечисление разбиений можно осуществить как перечисление их векторов Будем

говорить, что разбиение Я^ множества {а\, . , ат, ат , 0«+/} порождено разбиением Я множества {а,, , ат}, если представляющий вектор разбиения Я является префиксом представляющего вектора разбиения Число всех разбиений порожденных ¿-блочным разбиением Я, не зависит от вида Я и определяется однозначно величинами к и / Обозначим его Щк, /) Теорема 2.3. Пусть £>(0,0) = 1, тогда верны следующие соотношения й(к,0)= 1,к>0,

Б(к, () —к Щк, I- 1) + Б(к + 1, Г- 1), к> О, I > О

Требуемые в методе нумерации величины для разбиений «-элементного множества определяются следующим образом р\ — 1, для / = 2, ,п 2{рх, р2, . , 1,2, ,к,к+ 1}, где к = шах{рь р2, ,р^1},чН{р1,р2,. .,/>,_ О = ЕКк,п-1

+ 1)

Пусть Кт есть число всех разбиений с префиксом (рь р2, , р„), номера которых не превосходят I, - кратность префикса К\ = /, = К„, - (р,„+1 -1 )£>(*, и-/и- 1)

Теорема 2.4. Пусть 1 < т < п, (ри р2, , рт-\) - ¿-блочный префикс разбиения Я = (р 1, рг, , Рп) с номером I и А'„,_1 - его кратность Тогда если Кт_хЮ(к,п-т) < к, торт = /й(к,п-т)~], иначе/>„, = 1

Метод нумерации обеспечивает высокую эффективность, благодаря пропорциональному распределению вычислений и отсутствию обменов данными между процессорами, о чем свидетельствуют и результаты вычислительных экспериментов Для параллельного перечисления сочетаний эффективность в среднем равна 0,87, перестановок - 0,94, эффективность параллельного алгоритма перечисления разбиений множества лежит в диапазоне 0,8 - 0,85

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

ь ,*„),/= 1, ., т,

где Х\, , х„- булевы переменные, л, - булевы константы, /,(х1, . ,х„) - булевы функции, представленные суммой по модулю 2 элементарных конъюнкций, / = 1, , т Множество переменных Ьс:Х={Х\,. ,х„} называется

13

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

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

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

Пусть В есть покрытие множества X Подмножество Ь с X будем называть линеаризационным множеством покрытия В, если \ У — Ц<\ для всех УеВ Если вернуться к системе логических уравнений 5, то здесь X есть множество переменных системы, а В - множество его подмножеств, соответствующих конъюнкциям системы Я, каждое из которых состоит из переменных, входящих в соответствующую ему конъюнкцию (с инверсией или без) В этом случае линеаризационное множество покрытия В будет линеаризационным множеством переменных системы 5, хотя обратное может и не выполняться В задачах построения линеаризационных множеств достаточно рассматривать только покрытия, не содержащие одноэлементных блоков Обозначим М(Х) множество всех таких покрытий множества X

Алгоритм А1 покрытию В е М{Х) в соответствие ставит граф С(У, Е) такой, что V = X и {и, у} еЕ, если и только если существует У е. В, что и <в У, V е У и и / V

Построенный так граф й назовем графическим представлением покрытия В и будем обозначать АЦВ) Алгоритм А1 имеет полиномиальную сложность

Утверждение 3.1. Множество Ь является линеаризационным для В е М(Х) тогда и только тогда, когда оно является вершинный покрытием графа А1(й)

Покрытия Л и С из М{Х) будем называть эквивалентными, если любое подмножество Ь с. X является линеаризационным для В тогда и только тогда, когда оно линеаризационное для С Класс эквивалентности на М(Х), содержащий множество В е М(Х), обозначим [б] Следующая теорема дает конструктивный тест эквивалентности двух покрытий

Теорема 3.1 Пусть В, В'е М(Х) Покрытия В к В' эквивалентны тогда и только тогда, когда графы А1(В) и А 1(5') совпадают.

Число блоков в покрытии будем называть его длиной Число о(В) = |В0| + + \В^\\ назовем весом покрытия В - {В0, , Вк_х) При решении задач поиска некоторого линеаризационного множества заданного покрытия во многих случаях имеет смысл выполнить переход к эквивалентному покрытию, например, меньшей длины или меньшего веса Покрытие В б М(Х) называется кратчайшим или минимальным, если соответственно |Д| < \А\ или сг(В) < о(А) для любого Ав[В\ Покрытие В = [В0, , е М(Х) называется безызбыточным, если не существуют В, е В и и е В„ что В' = {В0, , В,- {м}, В,+1, , ВкЛ}<а М(Х) к В'е [б]

Теорема 3.2. Если покрытие В = {В0, , Ды} является кратчайшим, то не существует таких множеств В1},В, , ,В,г е В, что г > 1, /)< 12< < ¡г и

г

множество У= и В, образует полный подграф в А 1(5)

м '

Теорема 3.3. Покрытие В = {В0, , е М(Х) является безызбыточным тогда и только тогда, когда для любых В, е В и иеВ, имеет место ЭуеВ,(и Ф V &

Доказательство достаточности в теореме 3 3 содержит алгоритм АЗ преобразования заданного покрытия в эквивалентное безызбыточное

Для С(У, Е) = А 1(2?) показывается (утверждения 3.3 — 3.5 ), что 1) 2?е[2?] и Е безызбыточное, 2) если в С7(К, Е) нет клики, содержащей более двух вершин, то |[Д] = 1

Утверждение 3.6. Для любого множества X, [А] > 3, существует безызбыточное, но не кратчайшее и не минимальное покрытие ВеМ(Х)

Утверждение 3 8. Для любого множества X, |А] ^ 5, существует кратчайшее, но не безызбыточное покрытие В е М(Х)

Утверждение 3.9. Любое минимальное покрытие ВеМ(Х) является безызбыточным для любого X

Утверждение ЗЛО. Для любого множества X, > 5, существует кратчайшее, но не минимальное покрытие В е М(Х)

Утверждение З.И, Для любого множества X, |Л1>8, существует минимальное, но не кратчайшее покрытие ВеМ(Х)

Пусть 0(У, Е) есть неориентированный граф без петель и кратных ребер Покрытие В множества Xя" V такое, что множество 1 является линеаризационным для этого покрытия тогда и только тогда, когда оно является вершинным покрытием графа С(У, £), будем называть соответствующим графу (7 В работе дается полиномиальный алгоритм А2 построения соответствующего графу С покрытия, обозначаемого А2(0) Некоторые его свойства отражены в утверждениях (3 15 -3 17)

Утверждение 3.15. Пусть В = {В0, , ВкА} = А2(С(К, £)) Тогда к < \Щ, причем к = \Ц тогда и только тогда, когда \В\ = 2 для каждого / = 0, ., к -1, в этом случае В = Е

Утверяадение 3.16. Пусть В = А2(С( V, Е)) Тогда \В\ < если и только если в й есть полный подграф с тремя (или более) вершинами

Утверждение 3.17. Пусть В = {В0, , Вкл) = А2(С(У, Е)). Тогда о(В) < \Е\ + к, причем о(В) = 2\Е\ тогда и только тогда, когда В = Е

Теорема 3.5. Задача построения кратчайшего покрытия, эквивалентного данному покрытию, является ЛТМрудной.

Экспоненциальная сложность алгоритмов минимизации покрытия вынуждает отказаться от поиска точного решения - кратчайшего или минимального покрытия и ограничиться существующим или с меньшими длиной и весом Последнего в некоторых случаях можно достичь с помощью следующего полиномиального алгоритма А4 Последовательно применяются алгоритмы А1, А2 и АЗ, те вычисляются С(У, £) = А1(В), В' = А2((7), В" = АЗ(В') и В" принимается за результат минимизации В, если |б"| < \В\ и с (В") < а(В)

Теорема 3.7. Задача построения кратчайшего линеаризационного множества покрытия является М*-трудной

Следующие утверждения (3 18 - 3 20) позволяют, во-первых, оценить снизу мощность линеаризационных множеств для покрытий некоторых типов, и, во-вторых, разрабатывать алгоритмы построения покрытий с линеаризационными множествами ограниченной снизу мощности

Утверждение 3.18. Если в графе А1 (В) есть клика мощности к, то любое линеаризационное множество покрытия В имеет мощность не меньше к - 1

Утверждение 3.19. Если А 1(5) является полным двудольным графом К,„„ .то всякое кратчайшее линеаризационное множество для В имеет мощность тш(/, т)

Утверждение 3.20. Если граф А\(В) состоит из г компонент связности йх, Ог и для каждого / = 1, ,г в С, есть клика мощности к„ то для покрытия В не

г

существует линеаризационного множества мощности меньше — г

/•1

Для решения задачи поиска кратчайшего линеаризационного множества покрытия предложены последовательные приближенный (жадный) алгоритм и алгоритм А6 обхода дерева, сокращаемого за счет использования функции нижней оценки, который применим для нахождения как приближенного, так и точного решения

Реализована программа, которая для заданной системы нелинейных уравнений ищет линеаризационное множество соответствующего покрытия по алгоритму А6 В программе предусмотрены следующие режимы работы 1) выполнять переход к эквивалентному покрытию, построенному алгоритмом А4, 2) искать покрытие в течение заданного интервала времени

Из результатов работы программы для ряда генерируемых случайным образом систем уравнений следует 1) вывод о полезности предварительного преобразования соответствующих покрытий алгоритмом А4 оно позволяет в среднем сократить число блоков в покрытии в 15 раз, а время поиска в некоторых случаях - в сотни раз, 2) высокое качество жадного алгоритма мощность кратчайшего линеаризационного множества отличается от мощности множества, найденного жадным алгоритмом, не более чем на 2, 3) для случайных покрытий множества X мощность линеаризационного множества, доставляемого алгоритмом А6 в течение 600 сек, в среднем в 1,5 раза меньше мощности X

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

дается пошаговое описание действий управляющего и рабочего процессов Эффективность распараллеливания получилась в среднем равной 0,9

Наконец оценивается количество покрытий, имеющих линеаризационные

♦

множества заданной мощности Обозначим Ь(п, к) число всех покрытий множества Х- {1,2, , п) с линеаризационными множествами мощности к Теорема 3.8. Цп, 1) = 1 + 2л(ЗпЧ -п)

Пусть есть число покрытий /¡-элементного множества, состоящих из 5 блоков Тогда (следствие из теоремы 3,9)

Z Dh (2

5=1

П-к+1

■1У <L(n, к) <

V

V*,

2* —1

2"~к I Db (2"-j=1

k+l

■1/

Покрытия, не содержащие одноэлементных блоков, будем называть 2-покрытиями Обозначим U(n) число 2-покрытий множествами U(n, к) число тех из них, для которых существуют линеаризационные множества мощности к Для U(n) получена следующая формула

U(n) = S (-l)ri" V("-r), где ¿(и) = 2я - 1 - и

г=о

Обозначим P/at множество всех ¿-блочных покрытий некоторого А-элементного множества L с X, содержащих ровно t одноэлементных блоков. Пусть Дь, = Рассмотрим произвольное Р е Обозначим Mnksi число всех таких 2-покрытий F множества X, что каждый блок в Р входит в какой-нибудь блок покрытия F и каждый блок в F содержит не более одного элемента из L—X\L, те L является линеаризационным для F Подсчитаем число UL(n, к) 2-покрытий множества X, для которых множество L является линеаризационным

Теорема 3.10 ПустьLçzX,\X\ = n,\L\ = к> Q Тогда

UL{n, к) = I 5=1

2-1 min{*,ä}

M,

nksl '

п-к

I (-1)

r=0

Ъ (=0

rn — k

и Аь,= I (-iy W

l'J 7=0

DkstMnkst

|(2n-*"r -iy(2"-k+l~r -Г)*'1

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

Основные публикации автора по теме диссертации

1 Беляев В А , Тимошевская Н Е Распараллеливание обхода дерева поиска для решения задачи о рюкзаке на кластерной системе // Высокопроизводительные параллельные вычисления на кластерных системах Материалы Международного

научно-практического семинара / Под ред проф Р Г Стронгина Нижний Новгород-Изд-во Нижегородского университета, 2002 -С 16-20

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

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

4 Тимошевская Н Е. Разработка параллельных алгоритмов обхода дерева // Высокопроизводительные параллельные вычисления на кластерных системах // Материалы третьего Международного научно-практического семинара / Под ред проф Р Г. Стронгина - Нижний Новгород Изд-во Нижегородского университета, 2003 -С 198-206

5 Тимошевская Н Е Параллельные вычисления в решении систем логических уравнений методом линеаризации // Материалы XV международной школы-семинара "Синтез и сложность управляющих систем" (Новосибирск, 18-23 октября 2004 г.). -Новосибирск Институт математики, 2004 -С 97-102

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

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

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

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

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

11 Тимошевская НЕ О линеаризационных множествах // Проблемы теоретической кибернетики Тезисы докладов XIV Международной конференции (Пенза, 23-28 мая 2005 г) / Под редакцией О.Б Лупанова. - М. Изд-во механико-математического факультета МГУ, 2005. - С 154.

12 Тимошевская Н Е Задача о кратчайшем линеаризационном множестве // Вестник Томского госуниверситегга Приложение -2005 -№ 14-С 79-83

13 Тимошевская Н Е О линеаризационно эквивалентных покрытиях//Вестник Томского госуниверситета Приложение —2005 -№14 —С 84-91

14 Тимошевская Н Е Параллельное перечисление разбиений множества методом нумерации // Вестник Томского госуниверситета Приложение - 2006 - № 17-С 260-264

15 Тимошевская Н.Е. О методах разработки параллельных комбинаторных алгоритмов // Третья Сибирская школа-семинар по параллельным вычислениям / Под ред А В Старченко - Томск Изд-во Том. ун-та, 2006 - С 60-72

Тираж 110 экз. Заказ 501 Томский государственный университет систем управления и радиоэлектроники 634050, г. Томск, пр. Ленина, 40

Введение.

Глава 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- трудность задачи поиска кратчайшего линеаризационного множества;

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

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.