Параллельные алгоритмы оптимизации на графах Кэли тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Кузнецова, Александра Сергеевна

• Кузнецова, Александра Сергеевна
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Кузнецова, Александра Сергеевна

Содержание

Введение

1 Основные определения и понятия

1.1. Группы

1.1.1. Симметрическая группа

1.2. Графы

1.2.1. Графы Кэли

1.3. Последовательный алгоритм А-1

1.3.1. Примеры

2 Исследование графов симметрических групп

2.1. Постановка задачи

2.2. Параллельная версия алгоритма А-1 для графов групп Бп

2.3. Анализ компьютерных вычислений

3 Исследование графов конечных двупорожденных групп периода 5

3.1. Постановка задачи

3.2. Быстрое произведение элементов группы

3.3. Параллельная версия алгоритма А-1 для графов групп

3.4. Изучение графов для симметричного порождающего множества

3.5. Изучение графов для несимметричного порождающего множества

Заключение

Список литературы

Работы автора по теме диссертации

Приложение

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

Введение

Актуальность темы. Определение графа Кэли было дано известным английским математиком Артуром Кэли в 1878 году для представления алгебраической группы, заданной фиксированным множеством порождающих элементов [11].

В последние десятилетия теория графов Кэли развивается как отдельная большая ветвь теории графов. Графы Кэли находят применение как в математике, так и за ее пределами [42]. Заметим, что известная задача по определению так называемого "числа Бога" кубика Рубика 3 х 3 х 3, т. е. минимального количества поворотов граней кубика за которое его можно "собрать" из любого начального положения, сводится к исследованию соответствующего графа Кэли [44].

Неожиданное применение графы Кэли нашли в информационных технологиях после пионерской работы 1986 года С. Эйкерса и Б. Криш-намурти [25], которые впервые предложили применять указанные графы для представления компьютерных сетей, в том числе для моделирования топологий многопроцессорных вычислительных систем (МВС) — суперкомпьютеров [1,4,14,24]. С тех пор данное направление активно развивается. Это связано с тем, что графы Кэли имеют много привлекательных свойств, из которых выделим их регулярность, вершинно-транзитивность, малые диаметр и степень при достаточно большом количестве вершин в графе. Кстати, такие базовые топологии сети, как

"кольцо" и "гиперкуб" [2], являются графами Кэли. Среди множества работ [11,26-31,33,35,39-41,43,45-47,51,52,56,57] отдельно стоит отметить статью С. Шайбелла и Р. Стаффорда 1992 года [52], в которой показано, что наряду с диаметром графа Кэли, очень важное значение для производительности МВС имеет также средний диаметр графа.

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

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

Поиск минимального слова в большой конечной группе является хотя и разрешимой, но достаточно сложной проблемой. Это связано с тем, что в общем случае задача по определению минимального слова в группе, а следовательно и диаметра графа Кэли, как показали С. Ивен и О. Голдрейх в 1981 году, является ИР-трудной [32]. Так, при вы-числениии в 2010 году упомянутого выше "числа Бога", которое равно

диаметру соответсвующего графа Кэли, Т. Рокики, Г. Коцемба, М. Дэвидсон и Д. Детридж доказали, что любая конфигурация кубика Рубика может быть решена не более чем в 20 ходов [36]. Для установления данного факта потребовалось около 35 "процессоро-лет" распределенных вычислений. Поэтому для эффективного решения задач оптимизаци на графах Кэли, имеющих большое количество вершин, необходимо применять МВС. В связи с этим представляется актуальной проблема разработки параллельных алгоритмов для исследования графов Кэли частных классов групп.

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

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

1. Проанализировать существующие методы и алгоритмы, реализуемые на ЭВМ, для исследования свойств графов Кэли.

2. Создать базовый последовательный алгоритм А-1 для решения задач оптимизации на графах Кэли, доказать его корректность.

3. На основе А-1 разработать параллельные алгоритмы для решения задач оптимизации на графах Кэли симметрических групп, а также групп, заданных коммутаторами, т. е. рс-представлениями.

4. Применить созданные алгоритмы на МВС для решения задач оптимизации на конкретных графах Кэли указанных типов групп.

Соответствие диссертации паспорту специальности. Работа выполнена в соответствии с пунктом 4 — "Разработка методов и алгорит-

мов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации" паспорта специальности ВАК 05.13.01 — системный анализ, управление и обработка информации.

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

Научная новизна диссертационной работы

1. Создан новый последовательный алгоритм А-1 для решения задач оптимизации на графах Кэли, обоснована его корректность (теорема 1).

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

3. Решены задачи оптимизации на графах Кэли симметрических групп 5П для п < 13, заданных циклами транспозиций, на основе которых определены ранее неизвестные диаметры, средние диаметры и функции роста указанных графов (теорема 2).

4. Решены задачи оптимизации на графах Кэли конечных двупо-рожденных групп периода пять Вк при к < 5 (заданных рс-представлениями), на основе которых найдены ранее неизвестные диаметры, средние диаметры и функции роста данных графов для симметричного (теорема 4), а также несимметричного (теорема 5)

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

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

Апробация. Результаты диссертационной работы докладывались автором на следующих международных и всероссийских конференциях: XIV, XV, XVI Международная конференция "Решетневские чтения" (Красноярск, 2010-2012 гг.); Международная алгебраическая конференция "Мальцевские чтения" (Новосибирск, 2012 г.); VII Всероссийская конференция "Всесибирский конгресс женщин математиков" (Красноярск, 2012 г.); Ь Международная научная студенческая конференция "Студент и научно-технический прогресс" (Новосибирск, 2012 г.); XI, XII Сибирская научная школа-семинар с международным участием "Компьютерная безопасность и криптография" — 51ВЕС1^УРТ (Иркутск, 2012 г.; Томск 2013 г.).

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

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

которых 4 в журналах из перечня ВАК России, а также 2 программы для ЭВМ, прошедших государственную регистрацию.

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

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

В первой главе приведены основные понятия из теории групп и теории графов. После чего дано описание нового последовательного алгоритма А-1 для вычисления функции роста, диаметра и среднего диаметра графа Кэли произвольной конечной группы. Затем доказана корректность представленного алгоритма, а в конце главы приведены примеры, иллюстрирующие его работу.

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

В третьей главе представлена модификация алгоритма А-1, адаптированная к исследованию графов Кэли двупорожденных групп периода пять на МВС. Затем приведен алгоритм для быстрого умножения элементов в указанных группах, основанный на полиномах Холла. После чего исследуются графы этих групп, заданных симметричным и несимметричным множествами.

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

В приложениии приведены полиномы Холла для быстрого умножения элементов двупорожденных групп периода пять.

Глава 1

Основные определения и понятия

В настоящей главе приведены основные понятия из теории групп [3,6,13,42,53,54] и теории графов [9,15,17,22,23]. После чего дано описание нового последовательного алгоритма А-1 для вычисления функции роста, диаметра и среднего диаметра графа Кэли произвольной конечной группы. Затем доказана корректность представленного алгоритма, а в конце главы приведены примеры, иллюстрирующие его работу.

1.1. Группы

Определение 1. Пусть У — произвольное множество. Бинарной алгебраической операцией (или законом композиции) на У называют произвольное фиксированное отображение г : У х У —>■ У декартова квадрата У2 = У х У в У.

Это значит, что любой упорядоченной паре (а, Ь) элементов а, Ъ € У ставится в соответствие однозначно определенный элемент т(а, Ь) из того же множества У. Часто бинарную операцию г на У обозначают каким-нибудь специальным символом (*,-, + и т. д.) и пишут атЪ. Будем называть а-Ь (или просто аЬ) — произведением (умножением), а а + Ъ —

суммой элементов а, Ь Е У. Очевидно, что эти названия в большинстве случаев условны.

На У можно задать несколько операций. Если необходимо веди-лить одну из них, то используют скобки: (У, •), и говорят, что операция • определяет на У алгебраическую систему.

Определение 2. Группой С? = (С7, •) называется множество элементов на котором задана бинарная операция удовлетворяющая следующим условиям:

(7) для всех а,Ь,с £ (7 верно а • (Ь • с) = (а • Ъ) • с (ассоциативность);

(и) в й существует единственный единичный элемент е, такой что д • е — е • д — д для любого д 6 С;

(Ш) каждый элемент д £ С имеет обратный д~1:

9 • д"1 = д~1 • 9 = е.

Если для любых элементов а, Ь € С? выполняется а • 6 = Ь • а, то такую группу называют коммутативной или абелевой.

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

Если множество С является конечным, то говорят, что группа конечна, а число ее элементов называют порядком группы и обозначают |Сх|. Если же множество G бесконечно, группу называют бесконечной. Пусть д е й и п — наименьшее положительное число для которого дп = е, тогда п является порядком элемента д.

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

(С,+). Ненулевые рациональные О])*, действительные М* и комплексные С* образуют коммутативные группы относительно операции умножения чисел: (О*,*), (К*,*), (О*,*)- Очевидно, что все указанные группы бесконечны.

Определение 3. Положим (7 — конечная группа и X с С. Множество X = {х1,х2, ■ ■. ,хт} называют порождающим множеством группы, а его элементы — порождающими, и записывают (2 = (X), если любой элемент из С можно представить в виде конечного произведения из порождающих:

С = (X) \/д € (7 => д = а\ • а2 •... • а8, где щ Е X.

Порождающее множество X называют также алфавитом, а порождающие элементы Хг — буквами.

Определение 4. Пусть д элемент из <2 и д = а\ • а2 • ... • а8, где ос{ е X. Правую часть данного выражения мы будем называть словом и записывать а\а2.. .а3. Множество всех слов над алфавитом X будем обозначать X*.

Если необходимо подчеркнуть, что слово V € X* соответствует элементу д е (3, то следует писать: уд.

Очевидно, что фиксированное слово у соответствует только лишь одному элементу группы.

Определение 5. Если два различных слова у = а\а2.. .аг и ту — ¡3г(32. • -А» представляют один элемент д группы (2, т. е. д = а\ ■ а2 ■ ... • аг и д = (3\- ¡32 -... • рг, то выражение а\ • а2 •... • аг = /3\ • /32 • •.. • (Зг (или уд = и)д) называют соотношением в <2.

Часто при задании группы соотношения записывают в каноническом виде: v = е. Если д = h — соотношение в группе, то в каноническом виде оно будет выглядеть д • h~l = е.

Определение 6. Положим v — произвольное слово из X*. Количество букв, входящее в v, будем называть длиной слова v и обозначать length (и).

Единица группы е будет представлена пустым словом, которое мы также обозначим е. По определению length(e) = 0.

На множестве порождающих введем отношение порядка "-<":

{Xi -<Х2<----< хт}.

Определение 7. Пусть v и w произвольные слова из X*. Будем говорить, что слово v = ai«2- • меньше слова w = fiifa.. ф3 и записывать v -< w, если имеет место одно из следующих утверждений:

(i) г < s;

(it) если г = s, тогда а\ = /?ь се2 = Pi, ■ • ■, otk-1 = Pk-ъ ®k ~< Pk для некоторого 1 < k < s.

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

Определение 8. Слово v будем называть минимальным в G относительно введенного порядка, если для любого другого слова w, удовлетворяющего условию vg = wg, будет выполняться v -< w.

Определение 9. Длиной length^, X) элемента g в алфавите X будем называть длину минимального слова vg е X*, представляющего данный элемент, т. е.

1ещ1Ъ.(д, X) = тт^ех^Цг^) | уд €= X*}.

Определение 10. Диаметром сНат(С?, X) группы С относительно порождающего множества X будем называть максимальную длину элементов данной группы. Другими словами,

сНат((2, X) = тах{1е1^]1(д, X) | д €

или,

сНат(С?,Х) = тах{т1п{1еп^Ь(г;р) | уд £ X*} | д € С?}. (1.1)

Определение 11. Пусть й = {X). Шаром КГ(С,Х) радиуса г группы С относительно X будем называть множество

Кг(в,Х) = {дев 11е^%,Х) < г}. (1.2)

Таким образом шар КГ(С,Х) радиуса г представляет собой все элементы группы С, длины которых относительно порождающего множества X не превышают г.

Определение 12. Функция роста growth(G!, X, г) группы С? = (X) от аргумента г € {0} и N задается соотношением growth(G!, X, 0) = 1 и growth((x, х, г) = \Кг(в,Х)\- \КГ^{С,Х)\ при г € N.

Это означает, что каждое значение функции роста growth(Gr, X, г) равно числу элементов группы С? = (X) фиксированной длины г.

Определение 13. Средним диаметром сИат(С?, X) конечной группы С будем называть среднюю длину ее элементов в алфавите X. Другими словами:

сИат

Е 1еп^Ь(р, X) £ growth(Gí, X, г) • г X) = '-^—щ-= —-щ-• (1-3)

1.1.1. Симметрическая группа Sn

Пусть Q — конечное множество из п элементов. Поскольку природа элементов для нас несущественна, удобно считать, что П = {1,2, ...,п}. Элементы множества Sn = S(Q) всех взаимно однозначных перобразова-ний Q —> О, называются перестановками.

В развернутой форме произвольную перестановку -к: % 7г (г), г = 1,2,..., п, изображают в виде

где = тг(к), к = 1,2,..., п — переставленные символы 1,2,..., п.

Произведением (композицией) двух перестановок а • г является перестановка, которая получается в соответсвии с общим правилом композиции отображений: (сгт) = <т(т(г)). Например, для перестановок

получим

Однако

12 3 4 2 3 4 1/ \3 2 1 4

поэтому сгт ф та.

Множество всех перестановок с композицией в качестве групповой операции называется симметрической группой степени п. Оче-

(12 ... п\

видно |5„| =п\, единица группы — е = — тождественная

\1 2 ... п

перестановка. Иногда 5„ называют группой подстановок степени п, а ее элементы — подстановками.

Циклом (?1 ¿2 ... гп) длины п будем называть подстановку, переводящую ¿1 в ¿2, 12 в гз, ..., гп_1 в гп, наконец, гп в ¿1. Не имеет значения откуда начинать циклы. Поэтому, например,

(¿1 г2 ... г„) = (г2 ... г„ ¿1).

Любая подстановка представима в виде произведения циклов. Поясним сказанное на примере указанных выше перестановок <т, г € 54.

Перестановка а, кратко записываемая в виде сг = (1 2 3 4), или, что то же самое, в виде

ст = (1 2 3 4) = (2 3 4 1) = (3 4 1 2) = (4 1 2 3),

называется циклом длины 4, а перестановка

т = ( 1 4) (2 3)

— произведением двух независимых циклов длины 2. Цикл длины 2 называют также транспозицией.

1.2. Графы

Определение 14. Графом Г = (У,Е) называют совокупность двух множеств — множества вершин V — {^,«2,... ,ут} и множество ребер Е = {в1, в2,..., еп}, где каждое ребро из Е определяется неупорядоченной парой вершин {г^г^}.

Отметим, что приведенная выше формулировка определяет неориентированный граф. Если же каждое ребро графа задается упорядоченной парой (и*,^-) вершин, то такой граф называют ориентированным.

Далее под графом будем понимать неориентированный граф.

Пусть VI и г>2 — вершины графа, е\ — соединяющее их ребро. Тогда вершина у\ и ребро е\ инцидентны, ребро е\ и вершина у2 также инцедентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.

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

Порядок графа определяется числом его вершин \У\.

Определение 15. Автоморфизмом графа Г = (V, Е) называется отображение множества вершин на себя, сохраняющее смежность, т. е. если {и, у] € Е, то будет верно {ср(и), (р(у)} е Е.

Определение 16. Граф Г = {УуЩ называют вершинно-транзитивным, если для любых двух вершин и,у £ V существует автоморфизм у, при котором (р(и) = у.

Определение 17. Маршрутом в графе Г = (У,Е) называют последовательность вершин и ребер из Г

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

Граф является связным, если между любыми его двумя вершинами существует маршрут.

Определение 18. Расстоянием d(u,v) между вершинами и и v в графе Г будем называть длину кратчайшей цепи, связывающей эти две вершины.

По определению d(u,u) = 0 и d(u,v) = d{v,u).

Определение 19. Диаметром diam(r) графа Г называется расстояние между двумя наиболее удаленными вершинами в графе, т. е.

diam(r) = таx{d(u,v) | и, v G V}. (1.4)

Определение 20. Средним диаметром diam(r) конечного непустого графа Г = (V,E) будем называть среднее расстояние между его вершинами. Другими словами:

Е d(u,v)

1.2.1. Графы Кэли

Определение 21. Пусть X — порождающее множество группы G, т. е. G = (X). Графом Кэли Г = Cay(G,X) = (V,E) называют ориентированный граф, обладающий следующими свойствами:

(i) множество вершин V(r) соответствуют элементам группы G,

(и) множество ребер Е(Г) состоит из всех упорядоченных пар (д, хд), где g € G и х G X.

В дальнейшем будем считать порождающее множество X симметричным и свободным от единичного элемента группы, т. е. х G X =ф> яГ1 € X и е £ X. Поскольку X является свободным от единичного элемента, то граф Г не содержит петель. Симметричность порождающего множества означает, что граф будет неориентированным и без кратных

ребер, т. е. если в графе имеется ребро из д в хд, то оно совпадает с ребром из хд в х~1(хд) = д. Таким образом,

Г = Cay(G, X) = (V,E), где V = G и Е = {{д,хд} | д е G, х е X}.

(1.6)

1.3. Последовательный алгоритм A-I

Для обоснования корректности алгоритма A-I докажем сначала вспомогательные утверждения.

Лемма 1. Пусть G = (X) и Г = Cay(G,X) — граф Кэли группы G относительно X. Тогда

(г) Г является связным \Х\-регулярным графом,

(И) Г является вершинно-транзитивным графом,

{iii) Уд, h, € G d(g, h) = length(/i£-1, X),

(iv) diam(r) = сйат((2, X),

(v) diam(r) =Шат(С,Х).

Доказательство, (г) Так как X является порождающим множеством группы G, то граф Г является связным, а в связи с тем, что X — симметричное порождающее множество, то каждая вершина в Г имеет степень равную Поэтому Г является связным |Х|-регулярным графом.

(п) Если и и у две произвольные смежные вершины в Г, то v = хи для некоторого х € X. Отсюда следует, что для смежных вершин всегда

найдется такой элемент х Е X, что уи~1 = х. Обратно, если и и и не являются смежными, то уи~~1 ^ X.

На множестве вершин из Г рассмотрим отображение такое что Фь(д) = дк. Докажем, что рн сохраняет смежность, т. е. если и и у две смежные вершины, то (рн{и) и (рн(у) также будут являться смежными. Действительно,

фъ.^)РнЫ)'1 = ук(иК)~1 = уИН^и'1 = ууГ1 е X.

Если же и и у не являются смежными, то будет выполняться ^аМ^лМ-1 ^ X, поэтому вершины <рн(и) и (рн{ъ) также не будут являться смежными. Так как отображение (рь сохраняет смежность, то оно будет являться автоморфизмом графа Г.

Положим К = и~1у. Тогда (ри(и) — <ри-ч{и) — ии~1у = у. Следовательно Г является вершинно-транзитивным графом.

(гм) Пусть дик — произвольные вершины в Г. Согласно (г) данный граф является связным, а значит существует путь связывающий эти вершины. Предположим, что кратчайший путь имеет следующий вид: д, «1 д, а20с\д,..., а3...а2а1 д (оц € X), т. е. (1(д,К) = в. С другой стороны, а3...а2^1 = Нд~1, следовательно, length(Кд~1,Х) = я. Таким образом, между длинами элементов группы (3 и кратчайшими цепями в графе Г имеется взаимно-однозначное соответствие, в частности, имеет место равенство

Мд^ев = \ещЬЪ(кд-\Х). (1.7)

(гу) Запишем формулу (1.4) с учетом (1.7):

сИат(Г) - = тах{(/(б?, К) \ д, Н е (2} =

тах{1е1^Ш(%_1,Х) | кд~1 € (?} = сНат(Сг,Х).

(г;) Согласно (И) граф Кэли является вершинно-транзитивным и для любых двух его вершин и и v будет выполняться

J2d(u,v) = J2d(u,v). (1.8)

veV u&v

С учетом (1.8) перепишем формулу (1.5):

£<*(«.«) \v\ Е d(u,v) Е d(u,v)

u,veV vzv vev

diam(r) - - - ^ .

Пусть u = e — единица G. Поскольку V = G, а также в силу (1.7), получим

Е <*(е, v) Е length(р, X)

сИат(Г) = щ-= —-Щ-= ¿1ат(<3, X).

□

Беря во внимание свойства (И) и (ггг) вышеприведенной леммы, мы можем определить функцию роста графа Кэли growth(Г,r) = growth(G?, X, г), которая задает количество вершин в графе, удаленных от любой заданной вершины на расстояние г.

Ниже представлен последовательный алгоритм для исследования графов Кэли конечных групп. Как показано во второй и третьей главах диссертации, данный алгоритм можно распараллелить для эффективной реализации на МВС.

Алгоритм А-1

Вход: С? = (С, •) — конечная группа и X = {х\ -< -< ... < хт} — упорядоченное порождающее множество С.

Выход: диаметр сЦат(Г), средний диаметр сНат(Г) графа Кэли Г = Сау(С,Х), а также функция роста графа growth(r) = growth(Г,r), 0 < г < сИат(Г).

1. 5 = О, К$ = К3{С,Х) = {е} - шар группы в, Т = К8.

2. s = 5 + 1, Ks = Ks-1, U = xi-TUx2-T.. .UXm'T — лексикографически упорядоченное множество.

3. T = 0, г = 1.

4. Если Wj ^ Ks, то К8 = К3ищ,Т = Ти щ.

Ii < \U\, то г = г + 1, переход в пункт 4;

i = \U\, то переход в пункт 6.

IT ф 0, то переход в пункт 2;

Т — 0, то переход в пункт 7. 7. diam(r) = 5 — 1, growth(r) = \Kr\ — \Kr-i\ для 1 < г < s — 1 и

s—1

Е growth (г) • г

growth(O) = 1, diam(r) = ———:-. Возврат полученных значений.

\KS-1\

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

Доказательство. По построению А-1 выражает каждый элемент группы (7 в виде уникального минимального слова. После каждого прохода от пункта 2 до пункта 6 множество К3 будет представлять собой шар радиуса 5 группы (3 в алфавите X. Поскольку количество элементов группы конечно, то через конечное число шагов все д € (2 будут записаны в формате минимальных слов, длины которых меньше в:

\/д е <2 3\ид € К8-х => Уу9 <£ 1 =>ид ^ уд.

Это означает, что diam(G?, X) = 5 — 1 и однозначно определяет

функцию роста группы (7 в алфавите X. Как было сказано growth(Г, г) = growth(G,X, г). По лемме 1 диаметр и средний диаметр графа Кэли Г группы <2 = (X) равны соответстующим характеристикам С. □

1.3.1. Примеры

Пусть

Tn = {(¿ ¿ + 1) | l<t<n-l} (1.9)

— множество транспозиций, которое, как известно [10], порождает симметрическую группу Sn, т. е. Sn = (Тп). Доказано [41], что

i- r^, t п m \\ nln ~ 1)

ámm{Cay{Sn,Tn)) =---.

Отметим, что данное семейство графов широко используется для моделирования топологии компьютерных сетей [25]. В литературе [41] граф Гп = Cay(Sn, Тп) известен как "Bubble-sort graph" или в переводе на русский "Граф пузырьковой сортировки". Такое название граф получил в связи с взаимосвязью с задачей сортировки массива методом пузырька [15].

Для иллюстрации алгоритма A-I вычислим характеристики графов Кэли групп S3, ¿>4 и S¡ в образующих (1.9).

Группа S3

Пусть а = (1 2), Ъ = (2 3), Т3 = {а -< Ъ} и 53 = (Т3). В результате вычислений получим: К3 = {е, а = (1 2), b = (2 3), ab = (1 3 2), ba = (1 2 3), aba = (1 3)}.

Таблица 1.1. Функция роста growth(r3,r)

г 0 1 2 3

growth (г) 1 2 2 1

diam(r3) = 3, diam(r3) = 1,5.

\ \

•

/ /

\ / \

Рис. 1.1. Граф Кэли Г3 Группа

Пусть а = (1 2), b = (2 3), с = (3 4) Т4 = {а -< Ь -< с} и 54 = (Т4>. На выходе получим: Kg = {е, a, b, с, ab, ас, ba, be, cb, aba, abc, acb, бас, beb, cba, abac, abeb, aeba, bacb, beba, abacb, abeba, baeba, abaeba}.

Таблица 1.2. Функция роста growth^, г)

г 0 1 2 3 4 5 6

growth(r) 1 3 5 б 5 3 1

diam(r4) = 6, diam^) = 3.

Рис. 1.2. Граф Кэли Г3 Группа S5

Пусть а = (1 2), Ъ = (2 3), с = (3 4), с = (4 5).

Т5 = {а -< Ъ < с -< d] и Sb = (Г5>.

В результате вычислений получим: К10 = {е, а, Ь, с, d, ab, ас, ad, 6а, be, bd, cb, cd, de, aba, abe, abd, acb, acd, ade, bac, bad, beb, bed, bdc, cba, c6<i, ede, deb, abac, abad, abeb, abed, abde, acba, acbd, aede, adeb, bacb, bacd, bade, beba, bebd, bede, bdcb, cbad, ebde, edeb, deba, abacb, abaed, abade, abeba, abebd, abede, abdeb, acbad, acbdc, acdcb, adeba, bacba, bacbd, baede, badeb, bebad, bebde, bedeb, bdeba, cbadc, cbdcb, edeba, abacba, abacbd, abaede, abadeb, abebad, abebde, abedeb, abdeba, acbadc, acbdcb, aedeba, bacbad, bacbde, bacdcb, badeba, bebade, bebdeb, bedeba, cbadcb, ebdeba, abacbad, abacbdc, abaedeb, abadeba, abebade, abebdeb, abedeba, acbadcb, acbdcba, bacbadc, bacbdcb, baedeba, bebadeb, bebdeba, cbadcba, abacbadc, abacbdcb, abaedeba, abebadeb, abebdeba, acbadcba, bacbadcb, bacbdcba, bebadeba, abacbadcb, abacbdcba, abebadeba, bacbadcba, abacbadcba}.

Список литературы диссертационного исследования кандидат наук Кузнецова, Александра Сергеевна, 2013 год

Список литературы

[1] Барский А.Б. Параллельные информационные технологии: учебное пособие. М.: Интернет-Университет Информациооных Технологий; Бином. Лаборатория знаний, 2007. 503 с.

[2] Богданов A.B., Корхов В.В., Мареев В.В., Станкова E.H. Архитектуры и топологии многопроцессорных вычислительных систем. Курс лекций. М.: ИНТУ ИТ.РУ " Интернет-университет информационных технологий", 2004. 176 с.

[3] Босс В. Лекции по математике. Т. 8: Теория групп. М.: КомКнига, 2007. 216 с.

[4] Гергель В.П. Теория и практика параллельных вычислений: учебное пособие. М.: Интернет-Университет Информациооных Технологий; Бином. Лаборатория знаний, 2007. 423 с.

[5] Гоппа В.Д. Введение в алгебраическую теорию информации. М.: Наука. Физматлит, 1995. 112 с.

[6] Гроссман И., Магнус В. Группы и их графы / пер. с англ. М.: Мир, 1971. 246 с.

[7] Дэвенпорт Дж., Сирэ И., Турнье Э. Компьютерная алгебра: символьные и алгебраические вычисления / пер. с англ. М.: Мир, 1991. 350 с.

[8] Дяконов В.П. Компьютерная математика. Теория и практика. М.: Нолидж, 2001. 1296 с.

[9] Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич В.И. Лекции по теории графов. М.: Либроком, 2009. 392 с.

[10] Коксетер Г., Мозер У. Порождающие элементы и определяющие соотношения дискретных групп / пер. с англ. М.: Наука, 1980. 240 с.

[11] Константинова Е.В. Комбинаторные задачи на графах Кэли // Новосибирск: НГУ, 2010. 110 с.

[12] Кузнецов М. И., Бурланков Д.Е., Долгов Г.А., Чирков А.Ю., Яковлев В.А. Компьютерная алгебра. Н. Новгород: Изд-во Нижегород. гос. ун-та, 2002. 223 с.

[13] Курош А.Г. Теория групп. СПб.: Лань, 2005. 648 с.

[14] Лацис А.О. Как построить и использовать суперкомпьютер. М.: Бестеллер, 2003. 240 с.

[15] Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. СПб: Питер, 2008. 384 с.

[16] Ноден П., Китте К. Алгебраическая алгоритмика (с упражнениями и решениями). М.: Мир, 1999. 720 с.

[17] Ope О. Теория графов. М.: Наука, 1980. 336 с.

[18] Перегудов Ф.И., Тарасенко Ф.П. Введение в системный анализ. М.: Высшая школа, 1989. 367 с.

[19] Петров Ю.П. История и философия науки. Математика, вычислительная техника, информатика. СПб.: БХВ-Перербург, 2005. 448 с.

[20] Самсонов Б.Б., Плохов Е.М., Филоненков А.И. Компьютерная математика (основание информатики). Ростов-на-Дону: Феникс, 2002. 512 с.

[21] Системный анализ и принятие решений: Словарь-справочник: учеб. пособие для вузов / под. ред. В.Н. Волковой, В.Н. Козлова. М.: Высш.шк., 2004. 616 с.

[22] Уилсон Р. Введение в теорию графов / пер с англ. М.: Мир, 1977. 208 с.

[23] Харари Ф. Теория графов. М.: КомКнига, 2006. 296 с.

[24] Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования / пер. с англ. М.: Издательсткий дом "Вильяме", 2003. 512 с.

[25] Akers S., Krishnamurthy В. A group theoretic model for symmetric interconnection networks // Proceedings of the International Conference on Parallel Processing, 1986. P. 216-223.

[26] Asai S., Kounoike, Shinano Y., Kaneko K. Computing the diameter of 17—pancake graphs using a PC cluster // LNSC. 2006. Vol. 4128. P. 1114-1124.

[27] Bafna V., Pevzner P. Sorting by transpositions // SIAM Journal on Computing. 1998. Vol. 11, № 2. P. 224-240.

[28] Bamberg J., Gill N., Hayes Т., Helfgott H., Seress A., Spiga P. Bounds on the diameter of Cayley graphs of the symmetric group. URL: http://arxiv.org/abs/1205.1596 (дата обращения: 29.09.2013).

[29] Chen В., Xiao W., Parhami B. Internode distance and optimal routing in a class of alternating group networks // IEEE Transactionson Computers. 2006. Vol. 55, № 12. P. 1645-1648.

[30] Cibulka J. On average and highest number of flips in pancake sorting // Theoretical Computer Science. 2011. Vol. 412. P. 822-834.

[31] Cooperman G., Finkelstein L. New methods for using Cayley graphs in interconnection networks // Discrete Applied Mathematics. 1992. Vol. 37, P. 95-118.

[32] Even S., Goldreich O. The Minimum Length Generator Sequence is NP-Hard // Journal of Algorithms. 1981. Vol. 2. P. 11-313.

[33] Ganesan A. An Efficient Algorithm for the Diameter of Cayley Graphs Generated by Transposition Trees (Submitted on 31 Oct 2012) // URL: http://arxiv.org/abs/1202.5888 (дата обращения: 29.09.2013).

[34] GAP — Groups, Algorithms, Programming — a System for Computational Discrete Algebra // URL: http://www.gap-system.org/ (дата обращения: 29.09.2013).

[35] Gates W., Papadimitriou C. Bounds for sorting by prefix-reversal // Discrete Mathematics. 1979. Vol. 27. P. 47-57.

[36] God's Number is 20 // URL: http://www.cube20.org/ (дата обращения: 29.09.2013).

[37] Hall P. Nilpotent groups, Notes of lectures given at the Canadian Mathematical Congress 1957 Summer Seminar, in The collected works of Philip Hall. // Oxford: Clarendon Press, 1988. P. 415-462.

[38] Havas G., Wall G., Wamsley J. The two generator restricted Burnside group of exponent five // Bull. Austral. Math. Soc. 1974. № 10. P. 459-470.

[39] Helfgott H., Seress A. On the diameter of permutation groups (Submitted on 16 Sep 2011) // URL: http://arxiv.org/abs/1109.3550

[40] Heydari M.H., I. Sudborough I. On the diameter of the pankace network // Journal of Algorihms. 1997. Vol. 30. P. 67-94.

[41] Heydemann M. Cayley graphs and interconnection networks, in Graph symmetry: algebraic methods and applications (Editors: Hahnand Sabidussi) // Dordrecht: Kluwer Academic Publishers, 1997. P. 167-226. 167-226.

[42] Holt D., Eick B., O'Brien E. Handbook of computational group theory. Boca Raton: Chapman & Hall/CRC Press, 2005. 514 p.

[43] Jerrum M. The complexity of finding minimum length generator sequences // Theoretical Computer Science. 1985. Vol. 36, P. 265289.

[44] Joyner D. Adventures in group theory. Rubic's Cube, Merlin's Mashine, and other Mathematical Toys. Baltimore: The Johns Hopkins University Press, 2008. 310 p.

[45] Kounoike Y., Kaneko K., Shinano Y. Computing the diameter of 14— and 15—pancake graphs // In: Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, 2005. P. 490-495.

[46] Lakshmivarahan S., Jho J., Dhall S. Symmetry in interconnection networks based on Cayley graphs of permutation groupsiA survey // Parallel Computing. 1993. Vol. 19. P. 361-407.

[47] Malkevitch J. Pancakes, Graphs, and the Genome of Plants // The UMAP Journal. 2002. Vol. 23. P. 373-382.

[48] MAGMA Computational Algebra System // URL: http://magma.maths.usyd.edu.au/magma/ (дата обращения: 29.09.2013).

[49] MATLAB Distributed Computing Server System Administrator's Guide. The MathWorks, Inc., 2008. 73 p.

[50] MATLAB Parallel Computing Toolbox User's Guide. The MathWorks, Inc., 2008. 577 p.

[51] Parhami B. Swapped interconnection networks: Topological, performance, and robustness attributes // Journal of Parallel and Distributed Computing/ 2005. Vol. 65, № 11, P. 1443-1452.

[52] Schibell S., Stafford R. Processor interconnection networks and Cayley graphs // Discrete Applied Mathematics. 1992. Vol. 40. P. 337-357.

[53] Seress. A. An introduction to computational group theory // Notices AMS. 1997. 44, № 6. P 671-679.

[54] Sims C. Computation with finitely presented groups. Cambridge: Cambridge University Press, 1994. 628 p.

[55] Sims C. Fast multiplication and growth in groups // Proceedings of the 1998 international symposium on Symbolic and algebraic computation, 1998. P. 165-170.

[56] Wang L., Tang K. The Cayley Graph implementation in TinyOS for dense wireless sensor networks // Proc. of the 6th Wireless Telecommunications Symposium (WTS'07), 2007.

[57] Xu J. Topological Structure and Analysis of Interconnection Networks. Dordrecht: Kluwer Academic Publishers, 2001. 352 p.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в журналах из перечня ВАК России

[58] Кузнецова A.C., Кузнецов A.A. Компьютерное моделирование конечных двупорожденных групп периода 5 // Вестник СибГАУ. 2012. № 5(45). С. 59-62.

[59] Кузнецова A.C., Кузнецов A.A. О взаимосвязи функций роста в симметрических группах с задачами комбинаторной оптимизации // Вестник СибГАУ. 2012. № 6(46). С. 93 -97.

[60] Кузнецова A.C., Кузнецов A.A. Быстрое умножение элементов в конечных двупорожденных группах периода пять // Прикладная дискретная математика. 2013. № 1(18). С. 110-116.

[61] Кузнецова A.C. Исследование функций роста в конечных двупорожденных группах периода 5 // Вестник СибГАУ. 2013. № 3(49).

Прочие публикации

[62] Кузнецова A.C., Кузнецов A.A. Теоретико-групповой подход в задачах комбинаторной оптимизации // Труды XIV Международной конф. "Решетневские чтения". Красноярск: Изд-во СибГАУ, 2010. С. 449.

[63] Кузнецова A.C., Кузнецов A.A. Моделирование топологии мультипроцессорной вычислительной системы на основе теории групп // Труды XVI Международной конф. "Решетневские чтения". Красноярск: Изд-во СибГАУ, 2012. С. 545-546.

[64] Кузнецова A.C., Кузнецов A.A. Быстрое умножение элементов в двупорожденных бернсайдовых группах периода пять // Материалы VII Всероссийской конф. "Всесибирский конгресс женщин математиков". Красноярск: Изд-во СибГТУ, 2012. С. 108-110.

[65] Кузнецова A.C., Сафонов К.В. Об одной задаче комбинаторной оптимизации // Приложение к журналу Прикладная дискретная математика. 2012. № 5(17). С. 15-16.

[66] Кузнецова A.C., Кузнецов A.A. К вопросу о вычислении функции роста в бернсайдовой группе В0(2,5,7) // Тезисы Международной конф. "Мальцевские чтения". Новосибирск: Изд-во ИМ СО РАН, 2012. С. 62.

[67] Кузнецова A.C., Кузнецов A.A. Функции роста в конечных двупорожденных бернсайдовых группах периода 5 // Материалы юбилейной 50-й Международной научной студенческой конф. "Студент и научно-технический прогресс": Математика. Новосибирск: Изд-во НГУ, 2012. С. 12.

[68] Кузнецова A.C., Кузнецов A.A., Сафонов К.В. Параллельный алгоритм вычисления функций роста в конечных двупорожденных группах периода 5 // Приложение к журналу Прикладная дискретная математика. 2013. № 6. С. 119-121.

Разработки, зарегистрированные в государственном объединенном фонде электроннных ресурсов "Наука и образование"

[69] Кузнецова A.C., Кузнецов A.A. Вычисление функций роста в симметрических группах // Свидетельство о государственной регистрации электронного ресурса № 18544 от 27.09.2012.

[70] Кузнецова A.C., Кузнецов A.A. Вычисление функций роста в конечных полициклических группах // Свидетельство о государственной регистрации электронного ресурса № 18555 от 03.10.2012.