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

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

%

КУЗНЕЦОВ АЛЕКСАНДР АЛЕКСЕЕВИЧ

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

05 13 01 — Системный анализ, управление и обработка информации (космические и информационные технологии)

01 01 09 — Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

Красноярск-2009

003476613

Работа выполнена в Сибирском государственном аэрокосмическом университете имени академика М Ф Решетнева, г Красноярск

Научные консультанты

доктор технических наук,

профессор Антамошкин Александр Николаевич

доктор физико-математических наук, профессор Шлепкин Анатолий Константинович

Официальные оппоненты

член-корреспондент РАН,

доктор физико-математических наук,

профессор Мазуров Виктор Данилович

доктор физико-математических наук, профессор Добронец Борис Станиславович

доктор физико-математических наук, профессор Попов Алексей Михайлович

Ведущая организация

Томский государственный университет

Защита состоится 22 октября 2009 г в 14 часов на заседании диссертационного совета Д 212 249 02 при Сибирском государственном аэрокосмическом университете имени академика М Ф Решетнева по адресу 660014, г Красноярск, проспект имени газеты "Красноярский рабочий", 31

С диссертацией можно ознакомиться в библиотеке Сибирского государственного аэрокосмического университета имени академика М Ф Решетнева

Автореферат разослан "_" сентября 2009 г

Ученый секретарь диссертационного совета

Моргунов Е П

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Современные научные данные и современные системные представления позволяют говорить о мире как о бесконечной иерархической системе систем Н Н Моисеев определяет системный анализ, как совокупность методов, основанных на использовании ЭВМ и ориентированных на исследование сложных систем — технических, экономических, экологических и т д

Однако методология системного анализа в приведенных выше областях может быть спроецирована на изучение объектов из других разделов естествознания (математика, физика и т д) Например, в математике за последние десятилетия появилось новое направление — компьютерное доказательство теорем Первым примером крупной математической теоремы, для доказательства которой был применен компьютер, стала теорема о четырех красках, доказанная в 1976 г К Аппелом и У Хакеном Конечно, указанное направление существенно использует методы информатики и вычислительной техники, что делает его междисциплинарным

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

• Что такое вычисление математического объекта?

• Как его вычислить наиболее эффективно?

• Каким образом обеспечить достоверность вычислений?

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

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

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

808017424794512875886459904961710757005754368000000000,

или приближенно 8 1053

Рассматриваемые в рамках ВТГ алгебраические системы следует отнести к разряду сложных Дело в том, что проблема тождества слов в группах, как показал П С Новиков, в общем случае алгоритмически неразрешима Аналогичный результат для полугрупп получен независимо А А Марковым и Э Постом Алгоритмическая неразрешимость проблемы изоморфизма в группах была доказана С И Адяном и независимо М Рабином И, наконец, алгоритмическая неразрешимость проблемы сопряженности в группах была получена У Буном В то же время для частных случаев групп такие алгоритмы существуют Главным образом, их применение связано с решением задач о конечности группы, определении ее структуры и изоморфизма с другими группами

К важнейшему классу задач ВТГ относят бернсайдову проблематику Проблема Бернсайда о периодических группах фиксированного периода была поставлена известным английским математиком У Берн-сайдом в 1902 году в следующей форме

Пусть 2:1,22> , хт — конечное число независимых элементов, порождающих группу С, в которой для любого элемента д выполнено соотношение дп = 1, где п — натуральное число Будет ли

определенная таким образом группа конечной, и если да, то каков ее порядок?

Впоследствии эти группы получили название свободных бернсай-довых групп и обозначение В(т,п) Перечислим известные к настоящему времени результаты по данным группам В(т,п) конечна для п = 2 (тривиальный случай), п = 3 (У Бернсайд — 1902 г), п = 4 (т = 2 — У Бернсайд, т > 2 — И Н Санов — 1940 г), п = 6 (М Холл — 1958 г) В(тп,п) бесконечна для нечетных п > 665 (С И Адян, ПС Новиков — 1975 г), для четных п > 248 и п делится на 29 (С В Иванов - 1994 г), п = 16fc > 8000 (И Г Лысенок -1996 г) Для других же показателей, наименьший из которых п — 5, вопрос о конечности В(тп,п) остается открытым

В 1950 году в работе В Магнуса была сформулирована еще одна проблема, известная как "ослабленная проблема Бернсайда" В ней требовалось выяснить, существует ли максимальная конечная периодическая группа В0(тп,п) с данным числом порождающих m и фиксированным периодом п Связь ослабленной проблемы с основной проблемой Бернсайда сводится к тому, что если бы не существовало бесконечных периодических групп, то группа В(т, п) и была бы максимальной конечной периодической группой при этих тип Первый результат по этой проблеме был получен в 1955 г А И Кострикин установил существование группы Во (2,5) Положительное решение ослабленной проблемы Бернсайда для любых тип было получено Е И Зельмановым в 1991 г

Компьютерный эксперимент в рамках бернсайдовой проблематики внушителен Большинство работ в этом направлении используют комбинаторно-перечислительные методы в коммутаторном исчислении, базирующиеся на конструкциях алгебры Ли Исчерпывающий библиографический список можно найти в монографиях М Воэн Ли, Ч Сим-са, а также Д Хольта, Б Аика и Е О'Брайна Выделим некоторые результаты Например, в 1974 г Дж Хавас, Г Уолл и Дж Уэмсли, используя результат А И Кострикина о том, что 531 < |ß0(2,5)| < 534, вычислили |£?о(2,5)| = 534 В 2002 г Е О'Брайн и М Воэн Ли определили, что \Во(2,7)| = 720416 Доказательство этого результата заняло около одного года непрерывного машинного счета Среди отечественных исследователей особо стоит отметить работы А И Скопина и его учеников, внесшие значительный вклад в развитие ВТГ

Однако, как было сказано, вопрос о конечности бернсайдовых

групп для показателей 5, 7, 8 и т д до сих пор не решен Наибольший интерес представляет группа В(2,5), поскольку эта группа имеет наименьший показатель и наименьшее число порождающих в сравнении с другими бернсайдовыми группами, конечность которых не определена Кроме того, достаточно хорошо изучена структура группы Во(2,5), и если В(2,5) конечна, то В(2,5) ~ В0(2,5) Особую интригу придает тот факт, что при показателях п = 4 и п = 6 бернсайдовы группы конечны В связи с чем представляется актуальным создание новых методов, алгоритмов и программ для решения проблем бернсайдового типа

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

Цель диссертационной работы — на основе методологии системного анализа создать и реализовать на ЭВМ комплекс алгоритмов для моделирования дискретных алгебраических систем

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

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

2 Создать методологию компьютерного моделирования систем указанного вида.

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

4 На основе указанного комплекса алгоритмов получить критерии конечности и бесконечности бернсайдовых и других конечнопо-рожденных периодических групп

5 Провести компьютерное моделирование бернсайдовой группы В(2,5) на предмет определения ее структуры

6 При помощи моделирования групп на ЭВМ исследовать проблемы распознаваемости групп по их спектру

7 Подтвердить достоверность полученных результатов, применив методологию мультиверсионного программирования

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

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

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

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

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

4 На основе полученной методологии спроектирован и реализован на ЭВМ комплекс алгоритмов для вычисления дискретных алгебраических систем

5 Для различных классов конечнопорожденных периодических групп доказаны критерии конечности и бесконечности группы

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

a) Построен ранее неизвестный список соотношений для слов длины < 33

b) При поэлементном сравнении с группой Во(2,5) выявлено, что если длины слов V и ги не превышают 29 и ги = V — соотношение в группе Во(2,5), то данное соотношение будет справедливо и в группе В (2,5)

c) В группе В0(2,5) на длинах 30-33 найдены такие 128 соотношений, что несправедливость хотя бы одного из них в группе В(2,5) будет означать бесконечность В(2,5)

(1) В группе В0(2,5) найдено соотношение, длина левой и правой части которого равна 47, справедливость этого соотношения в В(2,5) означала бы наличие в В(2,5) нециклической абелевой подгруппы порядка 52

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

§) По результатам (0 предложен еще один дополнительный критерий конечности группы В(2,5)

7 На основе компьютерного моделирования с использованием созданного комплекса алгоритмов решен вопрос о распознаваемости по спектру группы ¿2(7) в классе всех групп, тем самым был получен положительный ответ на вопрос 16 57 из "Коуровской тетради"

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

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

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

1 Вторая Всероссийская научная конференция "Проектирование инженерных и научных приложений в среде МАТЪАВ" Москва, 2004 г

2 Международная алгебраическая конференция "Мальцевские чтения" Новосибирск, 2004, 2005, 2008, 2009 гг

3 Международная конференция, посвященная 75-летию со дня рождения профессора А И Кокорина "АЛиК-2004" Иркутск, 2004 г

4 VI Международная конференция "Дискретные модели в теории управляющих систем", посвященная 80-летию со дня рождения С В Яблонского Москва, 2004 г

5 Международная алгебраическая конференция, посвященная 100-летию со дня рождения П Г Конторовича и 70-летию Л Н Шеврина Екатеринбург, 2005 г

6 VII Международная конференция "Дискретные модели в теории управляющих систем" Москва, 2006 г

7 Международная алгебраическая конференция "Алгебра и ее приложения" Красноярск, 2007 г

8 Международная алгебраическая конференция, посвященная 100-летию со дня рождения А Г Куроша Москва, 2008 г

9 V Российско-Германская школа-конференция "Распределенные и высокопроизводительные вычисления" Новосибирск, 2008 г

10 Всероссийская конференция по математике и механике Томск, 2008 г

11 ИХ Международная конференция "Пограничные вопросы теории моделей и универсальной алгебры" Новосибирск, 2009 г

12 Международная алгебраическая конференция, посвященная 80-летию со дня рождения А И Кострикина Нальчик, 2009 г

Они неоднократно обсуждались на семинарах в Сибирском государственном аэрокосмическом университете, Институте математики СО РАН, Институте математики и механики УрО РАН, Сибирском федеральном университете и Красноярском государственном аграрном университете

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

Публикации. По теме диссертации опубликовано более 30 работ, среди которых 11 в ведущих рецензируемых журналах из перечня ВАК России, 2 монографии, а также 4 программы для ЭВМ, зарегистрированные в отраслевом фонде алгоритмов и программ Список основных публикаций приведен в конце автореферата

Проекты. Работа была выполнена в рамках следующих проектов

1 Грант РФФИ (проект 03-01-00905)

2 Грант Президента России по науке (проект МК-2494 2008 1)

3 Грант АВЦП "Развитие научного потенциала высшей школы" (проект 2 1 1/3023)

4 Грант РФФИ (проект 09-01-07177-а)

Награды. По результатам работы автор был удостоен

1 Государственной премии Красноярского края по науке — 2006 г

2 Премии главы города Красноярска по науке — 2009 г

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

Представление дискретной алгебраической системы в виде динамической системы специальных объектов

Пусть задано конечное множество X = {ссъяг, которое

назовем алфавитом Определим

С = (Х,) (1)

— некоторая дискретная алгебраическая система, состоящая из множества элементов, порожденных {х1,х2, ,хт}, с одной бинарной операцией " " Системы такого вида называют группоидами Будем представлять систему вида (1) следующим образом

<3 = 1ип Кв, 8—*00

где Ks — (PS,TS,AS,CS) — динамическая система специальных объектов, состоящая из последовательности слов (минимальных или независимых — см ниже) Ps, не превышающих по длине s, таблицы умножения Ts, построенной из последовательности слов Рм алгоритма поиска соотношений А, в таблице Ts, основанного на групповой аксиоматике, списка соотношений С„ получаемого при помощи А, Понятие "предела" в данном случае специфично, однако хорошо согласуется с классическим определением предела последовательности Указанное представление явилось базисом для построения комплекса алгоритмов моделирования дискретных алгебраических систем

Концепция минимальных слов

На множестве порождающих системы вида (1) введем отношение порядка "ч" (меньше) {х\ -< х2 -< -< хт} Пусть g элемент из G Тогда его можно представить в виде конечного произведения из свободных порождающих, т е g = qi а2 • «s. где а, € X, правую часть данного равенства мы будем называть словом и записывать v = ai»2 as В некоторых случаях, если необходимо подчеркнуть связь между элементом g и представляющим его словом v (т е записью элемента g через образующие), мы будем писать gv = qj ces

Натуральное число s будем называть длиной слова v Функция L(v) определена на множестве всех слов и равна длине слова v, т е L(v) = s для слова v, указанного выше Единица группоида (если таковая в нем имеется) е будет представлена пустым словом, которое мы также будем обозначать е По определению, длина пустого слова равна 0 Говорят, что слово х входит в слово w, если можно указать такие слова р и q, что w = pxq Если при этом слово р (слово q) пусто, то говорят, что х есть начало (конец) слова w Слово вида w = gx^x, будем называть

п

n-периодическим Слово w будем называть n-апериодическим, если в него не входит никакое непустое слово вида хп, т е w ^ pçx^q

п

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

1 L(w) < L(v)

2 Если L(w) = L(v), тогда пусть w = aiQ2 qs и v = fîifo 0s, ai = Pi, a2 = /?2, . ak-i = Pk-1, ak -< pk для некоторого 1 < k < s

Определение соотношения в группоиде Пусть v = а\а2 as и

го = Р\Рг ■ Рт ~ Два слова, представляющих один элемент д е б, т е дк = ах ■ а2 -а, = дш = Д ¡32 рт Тогда равенство

£*1£*2 а, = РФ2 ■ Рт

мы будет называть соотношением в (7

Определение минимального слова Слово V будем называть минимальным в <? относительно введенного порядка, если для любого другого слова ад, удовлетворяющего условию = дш, будет выполняться V -< V)

Необходимость использования минимальных слов возникает в задачах сравнения двух и более объектов в тех случаях, когда применение традиционных форматов представления по ряду причин не эффективно Предложенная концепция минимальных слов позволяет создать единообразное представление рассматриваемых систем, что делает возможным их сравнение по способу вхождения минимальных слов в данные объекты

Концепция независимых слов

Определение независимого слова Рассмотрим некоторое подмножество слов V в алфавите X Слово V называется независимым относительно V, если для любого гу 6 V невозможна ситуация ю = рид, где р к q некоторые слова Другими словами, V не является полсловом никакого слова т из V Если к тому же само слово V € V, то говорят, что ь независимо в V

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

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

Алгоритм-I

При помощи алгоритма A-I на основе минимальных слов строится динамическая система объектов Ki(m,n), K2(m,п) бернсайдовой группы В(т,тг) Поиск соотношений осуществляется с использованием групповой аксиомы об однозначности разрешения уравнения вида ах = Ь На основе данного алгоритма получен критерий, указывающий конечность В{т,п)

Определение Ki(m,n) = (Pj, А\,С\,Т{) Рассмотрим каждую составляющую объекта Ki(m,n)

Р\ — {е -< х\ -< Х2 ■< -< хт} — множество слов, состоящее из пустого слова и слов, имеющих длину 1, упорядоченных относительно введенного выше порядка "-<" Таким образом, Р\ является упорядоченным множеством образующих группы В(т, п) с единицей А\ — алгоритм n-апериодичности, который преобразует любое слово w в n-апериодическое слово Кратко опишем работу данного алгоритма

1 Задаем исходное слово w

2 Делаем проверку w = pxnq {*)

2 1 Если (*) выполняется, то w = pq Возврат в п 2 2 2 Если (*) не выполняется, то остановка алгоритма

Т\ — ||x,Xj|| (i,j = 1,2, , m) — таблица умножения Ci = 0 — список соотношений

Построение Ks(m, п) для s > 1 Определим

Р,(0) = е <xi < <хт< -< i -< -< t)s-ir Ч

Р.-1

-< XiVs-i 1 -< -< XiVu-if -< Ч Xmvs-1,1 -< -< Xmvs-\T

Таким образом, последовательность Pj0' получается из последовательности Ps_i выделением в Ps_i подпоследовательности всех слов, длины которых равны s — 1, и приписыванием к ее элементам слева образующих {х\,Х2, ,£,„} с последующим упорядочиванием этой подпоследовательности и объединением ее с Ps_i Пусть теперь v пробегает всю pf Рассмотрим множество Pj1^ = {As_i(f) | v e P'f^} Удалим в нем повторяющиеся слова, а затем упорядочим его элементы относительно введенного отношения порядка При этом полученная последовательность Рf1* будет обладать свойством V v е Pj1' = v Запишем

Р,(1) = {vi -< v2 ■< -< um,}

Далее составим таблицу умножения

?;(0) = 1М> (»,5 = 1,2, ,т.)

Затем получим таблицу т!1', применяя ко всем словам из Т,'0' алгоритм л£°\ = А„-1 по определению

гр) = л(°)(г№) = ||40)(^)1!

Пусть в таблице т]1' имеется строка го, в которой

л^к«,) - л<°) м

Это означает, что слова у3 и Ук соответствуют одному и тому же элементу группы, т е если у} = а\а2 <*« и Ук = АДг А-, то с*1 • а2 ав = /?1 /?2 • /Зг В итоге получаем соотношение VJ = Vk, или аха2 а, = рф2 /Зг. Пусть V, -< Ук Считая по определению с!0' = С8_1 = {сх, сг, ., с,.-1} и Сг = {V, = зд}, полагаем

С(1) = {С(°)исг} = {сьс2, ,сг}

После чего строим алгоритм Опишем сначала действие

л'0) на всех словах у € В(т,п), записав С^ в следующем виде

С10) = {ьк = и)к, Ук -< | к = 1,2,.., г - 1}

1 у = А\(у) — приводим слово у к п-апериодическому виду

2 к = 1 — параметр, указывающий номер соотношения в С^

3 Делаем проверку у = ршкЯ (*)

3 1 Если (*) выполняется, то у = рукд Возвращаемся в п 1 3 2 Если (*) не выполняется, то делаем проверку к < г - 1 (**) 3 2 1 Если (**) выполняется, то к — к + 1, возвращаемся в п 3 3 2 2 Если (**) не выполняется, то остановка алгоритма Л^

Алгоритм л!1' действует на всех словах у € В(т,п) аналогично л1°\ но индекс к пробегает значения от 1 до г

Далее, применяя алгоритм л!1' ко всем словам из получим рР\ инвариантную относительно л!1'

Р12) = {у!^У2^ -< ут,}

Затем вычислим таблицу умножения

ТЯ = ||Л(1)(^)||, (1,^ = 1,2, ,ту)

Если в тР найдется строка го, в которой

A^(vtovm) = Af\vlavp), то CÍ1' пополнится новым соотношением Ст+1 = {vm = г/р}, т е

Cf) = {Cf>Ucr+1} = {c1,c2, ,cr+1} Вслед за изменением списка соотношений изменятся также алгоритм,

последовательность и таблица умножения (Лi1' ^ л{2\ Р^ и

т(2) A™

Данный процесс будет продолжаться до тех пор, пока таблица умножения T¡¡не станет инвариантной относительно алгоритма л!2"1', т е в TÍ*' не найдется ни одной строки г0, такой, что = AÍz-1)(u,0t;j¿) Когда это будет выполнено, мы получим, что Ps = Р,(г), As = Л(,г_1), Cs = С\г~х) и Т, = T,w Таким образом, объект K4{m,n) = (Р,, Л„Т„С,) построен

Доказана следующая

Теорема 1. Пусть s — наименьшее натуральное число со свойством, К,(т,п) = Ks+i(m,n), тогда \В(т,п)\ < |Ps(m,п)|

После чего иллюстрируется работа алгоритма A-I на примерах построения известных конечных бернсайдовых групп В(2,3), В(2,4) и В( 3,3)

На рисунке 1 приведена блок-схема алгоритма A-I Алгоритм-И

Алгоритм A-II так же, как и A-I, строит динамическую систему объектов Ki(m,ri), К2(т,п) бернсайдовой группы В(т,п), однако, вместо минимальных слов теперь используются независимые слова Поиск соотношений осуществляется на основе групповой аксиомы об однозначности разрешения уравнения вида ах = b Каждый объект Ks(m, п) = (P„Á„f$,C3) включает в себя последовательность упорядоченных независимых слов Д группы В(т,п), не превышающих по длине s, A¡ — алгоритм, при помощи которого реализуется процедура поиска соотношений в В(т,п), таблицу умножения Ts, построенную из последовательности Ps, а также список получаемых соотношений С$ На основе алгоритма A-II найден критерий, указывающий конечность В(т,п)

Вход

Рисунок! Блок-схема алгоритма А-1

Теорема 2. Пусть в — наименьшее натуральное число со свойством Кц(т,п) = Кв+\(т,п), тогда группа В(т,п) конечна

Затем иллюстрируется работа алгоритма А-Н на примерах построения известных конечных бернсайдовых групп .6(2,3), В(2,4) и В(3,3) Время расчета по А-Н в среднем на два порядка меньше, чем время моделирования соответствующих групп по алгоритму А-1

Алгоритм-Ш

При помощи алгоритма А-Ш на основе минимальных слов строится динамическая система объектов А^т.п), ^(т, п) бернсай-довой группы В(т,п) Поиск соотношений осуществляется с использованием аксиомы ассоциативности операции в группе а(Ьс) — (аЬ)с Каждый объект К,(т,п) = {Р„А„С3) состоит из последовательности упорядоченных минимальных слов Р3 группы В(т, п), не превышающих по длине й, алгоритма поиска соотношений А3, а также списка соотношений С3 На основе алгоритма А-Ш получены критерии, указывающие конечность и бесконечность В(т,п)

В том случае, если имеет место К3(т,п) = К3+1(т,п) для некоторого й, то тогда группа В(т,п) будет конечной Пусть К(т,п) = (Р„ *), где операция * определена на всех элементах из Р, по следующему правилу V а, Ь е Р3 а *Ь = А3(аЬ) Справедлива следующая

Теорема 3. Пусть в — наименьшее натуральное число со свойством К3(т,п) = К3+\[т,п), тогда К(т,п) ~ В(тп,п) и, в частности, |В{т,п)\ - \Р„\

Если V 5 е N |Ра| < |Р5+1|, тогда группа В(т,п) бесконечна

Определим Р = 1ип Р„ следующим образом Пусть Р — [у, |

я—»оо

г = 1,2, } — бесконечная упорядоченная последовательность слов в алфавите образующих {11,0:2, обладающая следующим свой-

ством УиеРЭгем V в > г V е Р,

Определим А(ю) = 1ип ЛДго), где А — алгоритм, действующий

Ч—»00

на всех словах ги в алфавите образующих {х\, х-ь, ,1т} по правилу, указанному ниже Пусть г — наименьшее натуральное число, такое, что для выбранного слова ш V в > г Аг(ъи) = А3(ю) = V € Р Положим А(ь)) = Аг(ю)

Определим С = Ьт С„ С — {с, | г = 1,2, } = {г;, = ги,, V, -< ■ии1 | 8—*00

г = 1,2, } — бесконечный, упорядоченный относительно ш, список

соотношений из В(т, п), обладающий следующим свойством V с, € С 3reN v5>re,ecs

Обозначим lim КЛт,п) = (Р, *), где операция * определена на

»оо

всех элементах из Р по следующему правилу V а,Ь 6 Р а* b = А(аЬ) Справедлива следующая

Теорема 4. Пусть s е N и для всех s |Р4| < |Pi+i| Тогда

hm Ks(m,n) ~ В(т,п) и, в частности, В(т,п) бесконечна 8—>00

После чего иллюстрируется работа алгоритма A-III на примере построения группы 5(2,3)

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

G = {x 1,^2, ,хт I Wk=vk), (k= 1,2, ,n) (2)

— периодическая группа, т е группа, у которой каждый элемент имеет конечный порядок, заданная образующими {яь^г, ,хт} и определяющими СООТНОШеНИЯМИ V)¡(XI,X2, ,хт) — wk(xi,x2, ,хт)

В главе 2 были описаны алгоритмы для работы в свободных берн-сайдовых группах Однако при попытке применить данные алгоритмы для моделирования группы вида (2) возникли трудности, связанные с тем, что не всегда известны порядки элементов группы Сохранив основные идеи из предыдущей главы — способы получения новых соотношений, алгоритмы A-I, А-И, A-III были модифицированы таким образом, что стало возможным вычислять элементы и соотношения в произвольной периодической конечнопорожденной группе

Алгоритм-IV

При помощи алгоритма A-IV на основе минимальных слов строится динамическая система объектов K3(G) = (PS,AS,TS,C,) группы G, заданной (2) Поиск соотношений осуществляется с использованием групповой аксиомы об однозначности разрешения уравнения вида ах = Ь На основе алгоритма A-IV получен критерии, указывающий конечность G

Теорема 5. Пусть s — наименьшее натуральное число со свойством, KS{G) = Ks+l(G), тогда |G| < |PS(G)|

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

Алгоритм-V

Алгоритм A-V на основе независимых слов строит динамическую систему объектов K,(G) — (P„Á„f„C,) группы G, заданной (2) Поиск соотношений осуществляется с использованием групповой аксиомы об однозначности разрешения уравнения вида ах — b На основе алгоритма A-V получен критерий, указывающий конечность G

Теорема 6. Пусть s — наименьшее натуральное число со свойством K„(G) = Ks+i(G), тогда группа G конечна

Затем иллюстрируется работа алгоритма A-V на примере группы диэдра

Алгоритм-VI

При помощи алгоритма A-VI на основе минимальных слов строится динамическая система объектов K,(G) = (P„AS,CS) группы G вида (2) Поиск соотношений базируется на аксиоме ассоциативности операции в группе a(bc) — (ab)c На основе алгоритма A-VI получены критерии, указывающие конечность и бесконечность G

В том случае, если имеет место K^G) = Ks+i(G) для некоторого s, то тогда группа G будет конечной Пусть K(G) = (P¡, *), где операция * определена на всех элементах из Р„ по следующему правилу V a, b € Р, а * b — A,(ab) Справедлива следующая

Теорема 7. Пусть s — наименьшее натуральное число со свойством KS(G) = KS+Í(G), тогда K{G) ~G и, в частности, |G| = |Р,|

Если V s € N |Р,| < |P,+i|, тогда группа G бесконечна Так же, как и в главе 2, определим последовательность Р, алгоритм А и список соотношений С Обозначим lim KS(G) = (Р, *), где операция *

S—»00

определена на всех элементах из Р по следующему правилу V a, b е Р a*b = А{аЬ) Имеет место следующая

Теорема 8. Пусть s е N и для всех s |PS| < ¡Ps+i¡ Тогда hm KS(G) ~ G и, в частности, G бесконечна

S—* 00

После чего иллюстрируется работа алгоритма A-VI на примере построения диэдральной группы

В главе 4 приведены результаты компьютерного моделирования группы В(2,5) Затем сделан сравнительный анализ указанной группы с универсальной конечной бернсайдовой группой В0(2,5) Запишем

В(2,5) = (хьт2|55 = е)

— двупорожденная бернсайдова группа периода 5 На сегодняшний день неизвестно, конечна или бесконечна данная группа В 1955 году А И Кострикин решил ослабленную проблему Бернсайда для показателя 5, доказав, что существует максимальная конечная группа с двумя образующими и тождественным соотношением х5 = 1 (В0(2,5) -группа), для которой 531 < \В0(2,5)| < 534 Позднее, в 1974 году, Дж Хавас, Г Уолл и Дж Уэмсли показали, что |В0(2,5)| = 534 Если группа В(2,5) конечна, то В0(2,5) ~ В(2,5)

Будем считать, что образующие групп В0(2,5) и В(2,5) записаны в одном алфавите {1,2}, те = 1, хг = 2 Дж Хавас, Г Уолл и Дж Уэмсли, используя коммутаторное исчисление, вычислили соотношения для базисных коммутаторов группы В0{2,5) В качестве первых двух коммутаторов были взяты образующие группы В0{2,5), которые обозначили 1 и 2, а последующие, с 3-го по 34-ый, коммутаторы вычисляются рекурсивно через 1 и 2

Каждый элемент h 6 £?о(2,5) однозначно представляется упорядоченным произведением базисных коммутаторов в определенных степенях

h = I"1 2"2 34"",

где а, е {0,1,2,3,4} (г = 1,2, ,34)

Правую часть приведенного равенства мы будем записывать k(h) = 10>2™J 34"34 и называть нормальным словом

Пусть V — гомоморфизм группы В(2,5) на группу Во(2,5), заданный следующим правилом

где hv — элемент, вычисленный по слову v в группе £о(2,5), по аналогии с элементом gv в группе В(2,5)

Очевидно, все соотношения группы В(2,5) будут справедливыми в Во(2,5), обратное утверждение будет верно, если В0(2,5) ~ В(2,5) Таким образом, если два слова v и w равны как элементы группы в В(2,5), то под действием ф они будет соответствовать одному и тому же нормальному слову в Во(2,5). Например, из соотношения 11112222 = 21212121 следует, что 11112222 Л 1424 и 21212121 -t 1424

Если "ф окажется взаимно однозначным, то из этого будет следовать изоморфизм В(2,5) и В0(2,5), т е группа В(2,5) будет конечна В противном случае 5(2,5) — бесконечная группа

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

Для группы В(2,5) был вычислен объект Кзз{2,5) В терминах минимальных слов получилось, что |Сзз(2,5)| = 45392 и |Р33(2,5)| « 514

Расчеты были проведены на кластере Института космических и информационных технологий Сибирского федерального университета Для работы было выделено 125 однородных вычислительных узлов в режиме непрерывного доступа Каждый узел снабжен процессором с тактовой частотой 3 ГГц и ОЗУ 4 ГБ В качестве программного инструмента реализации была взята система компьютерной алгебры MATLAB 7 70 с подключенными дополнительными модулями MATLAB Distributed Computing Server и MATLAB Parallel Computing Toolbox Общее время машинных вычислений и 8 103 часов

При поэлементном сравнении группы В(2,5) с группой В0(2,5) было выявлено следующее

Теорема 9. Пусть v, w — два слова в алфавите образующих {1,2}, L{v) <29 и L(w) < 29 Тогда v = w — соотношение в группе Во(2,5) тогда и только тогда, когда v = w — соотношение в группе 5(2,5)

Однако длина 30 явилась своеобразной "точкой расхождения" групп В(2,5) и В0(2,5) Так, на длине 30 в Во(2,5) имеются 2 соотношения, на длине 31 — 10, на длине 32 — 47, и на длине 33 — 69, доказать справедливость которых в В(2,5) по алгоритмам из главы 2, при применении соотношений, длины левой и правой части которых < 33, не удается В таблице 1 приведены некоторые соотношения указанного вида (полный список в табл 4 1 диссертации)

Таблица 1

Фрагмент табл 4.1 диссертации

122121121221121212211212212112 = 212121122112212121122112212121 1221122121211221122121212222111 = 2121122121121221121212211212212 12211222121111211222212222121112 = 21211112121221122112112121112111 121211211121121211211122121221112 = 211122121221112112121121112112121

Поэтому имеет место

Теорема 10. Если в группе В(2,5) не выполняется хотя бы одно соотношение из таблицы 4 1 диссертации, то тогда группа 6(2,5) бесконечна

Дж Хавас, Г Уолл и Дж Уэмсли показали, что в группе Во(2,5) имеется абелева нормальная подгруппа Но индекса 510, элементы которой в терминах нормальных слов имеют вид h = 11а"12°12 34°31, т е Qi = аг = = аю = О

Пусть Я - подгруппа из В(2,5) такая, что при гомоморфизме ф 5(2,5) —» В0(2,5), Н0 является гомоморфным образом Я, те В(2,5)/Я ~ В0(2,5)/Я0 Очевидно, если Я — абелева подгруппа, то В(2,5) = Вй(2,5) В связи с этим интересно посмотреть, как ведет себя подгруппа Я на предмет коммутативности, т е если hi ^ /г2 6 Я, следует ли отсюда равенство h\h2 = h^hx (конечно, h\ и hz не лежат в одной циклической подгруппе)'

Элементы из Н впервые встречаются на длине 30 Всего таких элементов на указанной длине 180 При помощи несложных вычислений было получено, что среди них нет элементов, принадлежащих одной циклической подгруппе Пусть h„ h} G Я (i,j = 1,2, ,180) В группе В(2,5) доказать соотношения hjij - hjh, при г Ф j пока не удается, однако в группе Дз(2,5) указанные соотношения имеют место Приведем самое короткое по длинам слов соотношение указанного вида (длина каждого слова равна 47), справедливость которого означала бы наличие в группе В{2,5) абелевой нециклической подгруппы порядка 52

Теорема 11. Если в группе В(2,5) справедливо соотношение

12221211122122112112221211121221221121121222121 = = 21221121121222121112221211121212221211122122112,

тогда в В{2,5) имеется нециклическая абелева подгруппа порядка 52 </11) х (Л2), где /11 = 111212122212111221221121122212 и И2 = 111212212211211212221211122212

Далее в главе 4 описываются дополнительные критерии конечности группы В(2,5), основанные на вычислении коммутаторов специального вида Пусть

= [1,2] = Гх2-112 = 1111222212,

4га) = [4т"1),®1 = 4п_1Г1*~14т~1)*. т > 1,

где х — 1 для четных т и х — 2 для нечетных т Если группа В(2,5) конечна, то будет верно следующее соотношение

412) = [4П), 1]=е,

где е — единица группы (пустое слово) В(2,5), 12 — ступень нильпотентности группы £?о(2,5) Данный коммутатор был вычислен, и, с учетом полученного списка соотношений С33(2,5), его длина была сокращена от 19990 (без учета соотношений) до 16325 Пусть

К^ = [1,2] = \-12~112 = 1111222212,

К™ - [4т_1),2] = ^т-1)"12-14т"1)2, гп > 1 В том случае, если группа В(2,5) конечна, то будет верно следующее соотношение

46М45).2]=е,

где е — единица группы £(2,5), 6 — энгелев индекс группы Во{2,Ь) Указанный коммутатор был вычислен, и, с учетом полученного списка соотношений С33(2,5), его длина была сокращена от 320 (без учета соотношений) до 280

После чего в главе 4 при помощи ЭВМ исследуется автоморфизм порядка 2 бернсайдовой группы Во(2,5), отображающий образующие элементы £?о(2,5) в обратные Цель данного исследования — попытаться редуцировать проблему совпадения групп В{2,5) и В0(2,5) к проблеме совпадения двух групп, одна из которых имеет порядок существенно меньший, чем 534 Указанная попытка основана на классическом результате В П Шункова, который был получен в 1972 году периодическая группа, содержащая инволюцию, централизатор которой конечен, локально конечна и почти локально разрешима

Пусть {1,2} — образующие группы В(2,5) и <р — автоморфизм порядка 2 данной группы следующего вида

/1 - I-1 ^ [2 -» 2"1

Аналогичным образом (в тех же обозначениях образующих) можно определить автоморфизм (ро группы В0(2,5)

Пусть СВ(2,5)(у) и Св0(2,5)(^о) ~ централизаторы автоморфизмов ¡р и ¡ро в В(2,5) и В0(2,5) соответственно

Теорема 12. Для Св0(г,ь){щ) имеют место следующие утверждения

1) |СВо(2,5)(Ы1 = 516

2) Св0(2,5)(9'о) = х х (х5), где (х5) — центр группы В0(2,5), X = (х\,х2,хз,х\) — группа со следующими свойствами

a) X имеет нормальную абелеву подгруппу и |//2| = 511

b) Х/Н2 = {ххН2) х (х2Н2) х (х3Н2) х (х4Н2)

c) |Х| = 515

3) 5 — минимальное число порождающих Св0(2,ь)(<Ро)

Поскольку по приведенной теореме порядок Сво(2 5)(<Ро) значительно меньше порядка группы В0(2,5), предлагается сравнивать Сд(2,5)(</>) и <7во(2,5)(уо) Ясно, что если СВ{2,ь){(р) - Св0(2,5) (уо). то по упомянутому выше результату В П Шункова, группа В(2,5) будет конечна

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

Цель главы 5 — дать положительный ответ на вопрос 16 57 из "Коуровской тетради" о распознаваемости простой группы Ь2(7) по спектру Для конечных групп этот результат получен У Ши

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

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

Теорема 13. Если спектр группы G равен {1,2,3,4,7}, то G- L2(7)

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

4 На основе полученной методологии спроектирован и реализован на ЭВМ комплекс алгоритмов для вычисления дискретных алгебраических систем

5 Для различных классов конечнопорожденных периодических групп доказаны критерии конечности и бесконечности группы

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

a) Построен ранее неизвестный список соотношений для слов длины < 33

b) При поэлементном сравнении с группой В0(2,5) выявлено, что если длины слов V и т не превышают 29 и гу = и — соотношение в группе £?о(2,5), то данное соотношение будет справедливо и в группе В(2,5)

c) В группе В0(2,5) на длинах 30-33 найдены такие 128 соотношений, что несправедливость хотя бы одного из них в группе В{2,5) будет означать бесконечность В{2,5)

с1) В группе В0{2,5) найдено соотношение, длина левой и правой части которого равна 47, справедливость этого соотношения в В(2,5) означала бы наличие в 23(2,5) нециклической абелевой подгруппы порядка 52

е) Описаны дополнительные критерии конечности группы В(2,5), основанные на вычислении коммутаторов специального вида

0 Рассмотрен автоморфизм порядка 2 бернсайдовой группы В0(2,5), отображающий образующие элементы Во{2,5) в обратные Показано, что порядок централизатора указанного автоморфизма в группе В0(2,5) равен 516, а также определена структура данного централизатора

g) По результатам (0 предложен еще один дополнительный критерий конечности группы В(2,5)

7 На основе компьютерного моделирования с использованием созданного комплекса алгоритмов решен вопрос о распознаваемости по спектру группы Ь2(7) в классе всех групп, тем самым был получен положительный ответ на вопрос 16 57 из "Коуровской тетради"

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

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

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

[1] Кузнецов А.А , Шлепкин А К К вопросу о построении апериодических последовательностей // Вестн Красноярского гос ун-та Серия физ -мат науки 2004 № 3 С 90-94

[2] Кузнецов А А , Антамошкин А H , Шлепкин А К Моделирование периодических групп // Системы управления и информационные технологии 2008 № 2(32) С 4-8

[3] Кузнецов А А , Тарасов Ю С Модификация алгоритма моделировании периодических групп // Вестн Сиб гос аэрокосмич. ун-та

2008 Вып 2(19) С 42-43

[4] Кузнецов А А , Антамошкин А H , Шлепкин А К Применение независимых слов при моделировании периодических групп // Системы управления и информационные технологии 2008 № 2 2(32) С 286-289

[5] Кузнецов А А Теоретико-множественный анализ алгебраических систем в вопросах распознавания групп по их спектру // Вестн Сиб гос аэрокосмич ун-та 2009 Вып 2(23) С 38-40

[6] Кузнецов А А , Шлепкин А К , Тарасов С А Обобщенный алгоритм моделирования периодических групп // Вестн Новосибирского гос ун-та Серия математика, механика, информатика

2009 № 2 С 47-54

[7] Кузнецов А А , Шлепкин А К , Антамошкин А H Об одном критерии конечности бернсайдовой группы В(2,5) // Вестн Сиб гос аэрокосмич. ун-та 2009 Вып 2(23) С 28-30

[8] Кузнецов А А , Шлепкин А К Сравнительный анализ бернсайдо-вых групп В(2,5) и Во(2,5) // Труды Института математики и механики УрО РАН 2009 Том 15, № 2 С 125-132

[9] Кузнецов А А Моделирование периодических групп в задачах распознавания групп по их спектру // Информатика и системы управления 2009 № 2(20) С 19-23

[10] Кузнецов А А , Антамошкин А H , Шлепкин А К Моделирование периодических групп на основе теоретико-множественного анализа алгебраических систем // Системы управления и информационные технологии 2009 № 3(37) С 32-35

[11] Кузнецов А А , Шлепкин А К , Антамошкин А H Компьютерное моделирование бернсайдовой группы В(2,5) // Вестн Сиб гос аэрокосмич ун-та 2009 Вып 3(24) С 27-29

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

[12] Кузнецов А А , Лыткина Д В , Тухватуллина J1 Р , Филиппов К А Группы с условием насыщенности Красноярск КрасГАУ, 2009 270 с

[13] Кузнецов А А, Кузьмин ДА, Лыткина ДВ, Тухватуллина Л Р, Филиппов К А Компьютерные алгоритмы теоретико-множественного анализа сложных алгебраических систем Красноярск КрасГАУ, 2009 200 с

[14] Кузнецов А А , Шлепкин А К К вопросу о конечности свободных бернсайдовых групп В{т,п) // Матем системы 2005 Вып 3 С 36-38

[15] Кузнецов А А К вопросу о конечности свободной бернсайдовой группы В(2,5) // Матем системы 2005 Вып 4 С 38-47

[16] Кузнецов А А К вопросу о распознавании группы ¿г(7) по спектру // Сиб электр матем. изв 2005 Т 2 С 250-252

[17] Кузнецов А А К вопросу о конечности свободной бернсайдовой группы В(2,5) // Вестн молодых ученых КрасГАУ 2005 № 3 С 49-57

[18] Кузнецов А А , Тихомирова М В К вопросу о конечности группы В(2,5) // Матем системы 2006 Вып 5 С 15-19

[19] Кузнецов А А , Тарасов С А , Тухватуллина J1 Р Алгоритм перечисления группы // Матем системы 2007 Вып 6 С 63-72

[20] Kuznetsov А А, Lytkma D V Recogmzability by spectrum of the group L2(7) in the class of all groups 11 Сиб электр матем изв

2007 Т 4 С 136-140

[21] Кузнецов А А , Тарасов С А , Шлепкин А К К вопросу о конечности двупорожденной бернсайдовой группы периода 5 // Матем системы 2009 Вып 7 С 6-9

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

[22] Кузнецов А А , Тарасов С А , Шлепкин А К Вычисление элементов и соотношений в периодических группах // М ВНТИЦ,

2008 № 50200800998

[23] Кузнецов А А , Тарасов С А , Шлепкин А К Применение независимых слов при моделировании периодических групп // М ВНТИЦ, 2008 № 50200801020

[24] Кузнецов А А Приведение элементов бернсайдовых групп к нормальной коммутаторной форме // М ВНТИЦ, 2008 № 50200802050

[25] Кузнецов А А Параллельный алгоритм вычисления элементов и соотношений в периодических группах // М ВНТИЦ, 2009 № 502009000338

Кузнецов Александр Алексеевич

Комплекс алгоритмов компьютерного моделирования дискретных алгебраических систем

Автореферат

Подписано в печать 13 08 2009 Формат 60x84/16 Бумага писчая Гарнитура Times New Roman Уел печ л 1,875 Уч -изд л 1,5 Тираж 150 экз Заказ №280

Отпечатано в ООО «Поляком» 660017, г Красноярск, ул Ленина, 113, оф 416

Введение

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

1.1. Представление дискретной алгебраической системы в виде динамической системы специальных объектов

1.2. Концепция минимальных слов.

1.3. Концепция независимых слов.

2 Комплекс алгоритмов для моделирования бернсайдовых групп

2.1. Основные определения и предварительные леммы.

2.2. Алгоритм-1.

2.2.1. Определение Кх(т,п) = (Ри ЛьСЪТХ).

2.2.2. Построение К3(тп,п) для з > 1.

2.2.3. Условие конечности группы В(тп,п).

2.2.4. Пример: моделирование группы -0(2,3).

2.2.5. Пример: моделирование группы В(2,4).

2.2.6. Пример: моделирование группы В(3,3).

2.3. Алгоритм-Н

2.3.1. Определение К^тп, п) = (Рь Аи Си Т\).

2.3.2. Построение Кв(т,п) для й > 1.

2.3.3. Условие конечности группы В(т,п).

2.3.4. Пример: моделирование группы В(2,3).

2.3.5. Пример: моделирование группы В(2,4).

2.3.6. Пример: моделирование группы В(3,3).

2.4. Алгоритм-Ш.

2.4.1. Определение Кх(т,п) = {Р\,А],С\).

2.4.2. Построение К3(т,п) для 5 > 1.

2.4.3. Условие конечности группы В(т,п).

2.4.4. Условие бесконечности группы В(т,п).

2.4.5. Пример: моделирование группы В(2,3).

3 Комплекс алгоритмов для моделирования произвольных конечнопорожден-ных периодических групп

3.1. Основные определения и замечания.

3.2. Алгоритм-1У.

3.2.1. Определение Кх(С) = (Ри Аи СХ1ТХ)

3.2.2. Построение Ка(С) для в > 1.

3.2.3. Условие конечности группы С?.

3.2.4. Пример: моделирование группы диэдра.

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

3.3. Алгоритм-У.

3.3.1. Определение К\{в) = (А, Аъ СиТх)

3.3.2. Построение К3(0) для в > 1.

3.3.3. Условие конечности группы С.

3.3.4. Пример: моделирование группы диэдра.

3.4. Алгоритм-VI.

3.4.1. Определение Кг{С) = {РиАи Сх).

3.4.2. Построение Ка((3) для 5 > 1.

3.4.3. Условие конечности группы С.

3.4.4. Условие бесконечности группы С.

3.4.5. Пример: моделирование группы диэдра.

4 Исследование группы В(2,5)

4.1. Известные факты о -6(2,5) и В0(2,5).

4.2. Результаты вычислений в 5(2,5).

4.3. Сравнение В0(2,5) и В{2,5)

4.3.1. Поэлементное сравнение.

4.3.2. Сравнение по подгруппе индекса

4.4. Вычисление коммутаторов специального вида в В(2,5).

4.5. О структуре одного автоморфизма порядка 2 группы Во(2,5)

5 Распознавание группы £/2(7) по спектру в классе всех групп

5.1. Обозначения и известные результаты.

5.2. Предварительные леммы

5.3. Доказательство основного результата.

Актуальность темы. Современные научные данные и современные системные представления позволяют говорить о мире как о бесконечной иерархической системе систем [44]. Выдающийся советский ученый H.H. Моисеев определяет системный анализ, как совокупность методов, основанных на использовании ЭВМ и ориентированных на исследование сложных систем — технических, экономических, экологических и т. д. [34].

Однако методология системного анализа в приведенных выше областях может быть спроецирована на изучение объектов из других разделов естествознания (математика, физика и т. д.). Например, в математике за последние десятилетия появилось новое направление — компьютерное доказательство теорем. Первым примером крупной математической теоремы, для доказательства которой был применен компьютер, стала теорема о четырех красках, доказанная в 1976 г. К. Аппелом и У. Хакеном [70,71]. Конечно, указанное направление существенно использует методы информатики и вычислительной техники, что делает его междисциплинарным.

В настоящей работе предлагается методология работы со сложными дискретными объектами, характеризующимися большим числом элементов и требующих применения высокопроизводительных ЭВМ. Для формального описания указанных объектов на компьютере необходимы теоретико-множественные представления — дискретные алгебраические системы. Алгебраической системой принято называть множество с заданным на нем набором операций, удовлетворяющим некоторой системе аксиом [7,31,51]. Представление алгебраических систем в виде объектов, поддающихся вычислительной обработке, и ответ на три главных вопроса:

• Что такое вычисление математического объекта?

• Как его вычислить наиболее эффективно?

• Каким образом обеспечить достоверность вычислений?определяют основные задачи компьютерной алгебры [15,24,43,49].

Одним из важных и интересных направлений компьютерной алгебры является вычислительная теория• групп (computational group theory), далее ВТ<Г. Объектом исследования данного направления являются алгебраические системы с одной бинарной операцией (группоиды, полугруппы, моноиды, группы и т. д.) [25]. Как самостоятельное научное направление со своей проблематикой ВТГ оформилась после того как в 1911 г. М. Дэн сформулировал основные алгоритмические проблемы теории групп: проблему распознавания равенства, известную в литературе также под названием "проблема тождества слов", проблему сопряженности и проблему изоморфизма [78]. ВТГ находит многочисленные приложения как в самой математике (в геометрии, теории функций, теории дифференциальных уравнений и др.), так и за ее пределами (в кристаллографии, в классической и квантовой механике, в теории элементарных частиц, в химии, в биологии и т. д.) [8]. В связи с всеобщей информатизацией период доминирования непрерывной математики в значительной мере сменился периодом преобладания дискретной математики. В результате расширились и приложения теории групп: комбинаторика, теория конечных геометрий, теория графов, теория кодирования, теория сложности вычислений, криптография и т. д. [13]. Первые компьютерные программы для работы с группами были реализованы в начале 50-х годов XX века [84]. С тех пор эта сфера научной деятельности получила широкое распространение, исследования по соответствующей тематике ведутся во многих научных центрах по всему миру [9]. Помимо отдельных программ, разработано несколько мощных систем компьютерной алгебры, специализированных на вычислениях в группах (GAP [79], Magma [88]), накоплен также богатый опыт использования систем компьютерной алгебры общего назначения (Maple, Mathematica, Matlab и др. [16]) для теоретико-групповых вычислений. Привлечение фактического материала, получаемого при помощи символьных вычислений в различных классах групп, стало характерной чертой развития теории групп. В подтверждении этого факта уместно напомнить, что первоначальное построение многих простых спорадических групп существенно использовало вычисления на компьютере. Так в 1982 году Р. Грисс-младший построил группу, названную "монстром" за то, что число её элементов равно

808017424794512875886459904961710757005754368000000000, или приближенно 8 • 1053 [14].

Рассматриваемые в рамках ВТГ алгебраические системы следует отнести к разряду сложных [33]. Дело в том, что проблема тождества слов в группах, как показал П.С. Новиков [41], в общем случае алгоритмически неразрешима. Аналогичный результат для полугрупп получен независимо A.A. Марковым [32] и Э. Постом [94]. Алгоритмическая неразрешимость проблемы изоморфизма в группах была доказана С.И. Адяном [1] и М. Рабином [95]. И, наконец, алгоритмическая неразрешимость проблемы сопряженности в группах была получена У. Бу-ном [74].

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

Ситуация с конечноопределенными группами значительно сложнее. Здесь есть принципиальная трудность, состоящая в неразрешимости проблемы тождества слов в общем случае. Имеется весьма ограниченный набор базисных алгоритмов: метод Тодда-Коксеттера перечисления смежных классов и процедура Кнута-Бендикса по переписыванию слов в некоторой нормальной форме путем сбора всех существующих пар эквивалентных слов [84,98]. В частных подклассах конечноопределенных групп, в которых проблема тождества слов разрешима, опять имеется большое число методов и алгоритмов. Упомянем здесь подклас конечных групп, а также полициклических групп (имеющих конечный субнормальный ряд с циклическими факторами). Особенно эффективные алгоритмы разработаны для пересечения этих классов, т. е. для конечных разрешимых групп. Некоторые из внедренных здесь методов превосходят по быстродействию своих аналогов в группах подстановок [84,98]. В последнее время помимо детерминированных алгоритмов для нужд ВТГ пытаются также применять и вероятностные методы [75,91], основанные на генетических алгоритмах [11,48].

В связи с интенсивным развитием высокопроизводительных вычислительных систем — суперкомпьютеров1, а также соответствующего программного обеспечения для реализации параллельных алгоритмов ( [6,10,26,69]), появилась возможность существенно повысить скорость расчетов в задачах ВТГ.

Несмотря на то, что квантовые компьютеры ( [40,46]) еще находятся в стадии разработки, в работе [72] уже предложены квантовые алгоритмы для вычислений в группах.

К важнейшему классу задач ВТГ относят бернсайдову проблематику. Проблема Бернсайда о периодических группах фиксированного периода была поставлена известным английским математиком У. Бернсайдом в 1902 году в следующей форме [77].

Пусть х\, х'2, • • •) — конечное число независимых элементов, порождающих группу G, в которой для любого элемента g выполнено соотношение ga — 1, где п — данное целое число. Будет ли определенная таким образом группа конечной, и если да, то каков ее порядок?

Впоследствии эти группы получили название свободных бернсай-довых групп и обозначение В(т,п). Перечислим известные к настоящему времени результаты по данным группам. В(т,п) конечна для п = 2 (тривиальный случай), п = 3 (У. Бернсайд, 1902 [77]), п = 4 (га = 2 —

28 июля 2009 г. президент РФ Д.А. Медведев на заседании Совета безопасности заявил, что разработка суперкомпьютеров является приоритетной задачей России.". У нас считанные единицы моделей обсчитываются на суперкомпьютерах, а остальные делаются на ватмане с применением известных прежних подходов. При этом только цифровой подход может дать необходимый эффект, повысить уровень прогнозирования и управления самыми сложными процессами", — отметил он [47].

У. Бернсайд [77], т > 2 — И'.Н. Санов, 1940 [50]), п = 6 (М. Холл, 1958 [80]). В(т,п) бесконечна для нечётных п > 665 (С.И. Адян, П.С. Новиков, 1968 для п > 4381 [42], 1975 для п > 665 [2]); для четных: п > 248 и п делится на 29 (С.В1 Иванов, 1994 [86]), п = 16А; > 8000 (И.Г. Лысёнок, 1996 [28]). Отметим, что перечисленные результаты были получены без привлечения компьютерных вычислений. Для других же показателей, наименьший из котороых п = 5, вопрос о конечности В(т,п) остается открытым.

Приведем порядки конечных бернсайдовых групп. Группа В(т, 2) явлется элементарной абелевой и имеет порядок 2т. Ф. Леви1 и Б. Л'. Ван дер Варден показали, что \В(т, 3)| = За, где а = т + С^ + С^ (1933 [87]), здесь С* — биномиальный коэффициент. Для показателя п = 4 известны порядки следующих бернсайдовых групп: \В{2,4)\ = 212 (Дж. Тобин, 1954' [99]), |В(3,4)| = 269 (А. Байес, Дж. Кауц-кий, Дж. Уэмсли, 1974 [73]), |£(4,4)| = 2422 (Дж. Хавас, М. Ньюмен, 1980 [82]), \В(Ъ, 4)| = 22728 (Е. О'Брайн, М. Ньюмен, 1996, [92]). Для- последних трех случаев порядки- групп были вычислены при помощи компьютера. И, наконец, \В(т, 6)| = 2а3&, где о = 1 + {т — 1)3С, Ь = 1 + (т- 1)2т и с = т + С^ + С^ (М. Холл, 1958 [80]).

Более общий вопрос о локальной конечности периодических групп без ограничения на порядки элементов имеет название "общая проблема Бернсайда", отрицательное решение которой было получено Е.С. Голодом [12] в 1964 году. После чего была построена целая серия примеров бесконечных групп из которых отметим результат С.В. Алешина, полученный на основе автоматных преобразований [4].

В 1950 году в работе В. Магнуса [37] была сформулирована еще одна проблема, известная как "ослабленная проблема Бернсайда". В ней требовалось выяснить, существует ли максимальная конечная периодическая группа Во(т, п) с данным числом порождающих т и фиксированным периодом п. Связь ослабленной проблемы с основной проблемой Бернсайда сводится к тому, что если бы не существовало бесконечных периодических групп, то группа В(т, п) и была бы максимальной конечной периодической группой при этих тип [3]. Первый результат по этой проблеме был получен в 1955 г. А.И. Кострикиным было установлено существование группы В0(2,5) [20]. Затем В0(т, 5) — в 1956 г. [21,83], и Во(т,р) — в 1958 г. [22]. Окончательное положительное решение ослабленной проблемы Бернсайда для любых тип было получено Е.И. Зель-мановым [17].

Компьютерный эксперимент в рамках бернсайдовой проблематике внушителен. Большинство работ в этом направлении используют комбинаторно-перечислительные методы в коммутаторном исчислении, базирующиеся на конструкциях алгебры Ли [52]. Исчерпывающий библиографический список можно найти в монографиях [84,98,101]. Выделим некоторые результаты. Например, в [81], используя результат А.И. Кострикина из [20] о том, что 531 < |Д)(2,5)| < 534, было получено \Во{2,5)| = 534. В [93] было показно, что |В0(2,7)| = 720416. Доказательство этого результата заняло около одного года непрерывного машинного счета. Среди отечественных исследователей особо стоит отметить работы А.И. Скопина и его учеников [18,27,35-38,53-65], внесшие значительный вклад в развитие ВТГ.

Однако, как было сказано, вопрос о конечности бернсайдовых групп для показателей 5, 7, 8 и т. д. до сих пор не решен. Наибольший интерес представляет двупорожденная группа периода 5 (группа В(2,5)), поскольку это группа имеет наименьший показатель и наименьшее число порождающих в сравнении с другими бернсайдовыми группами, конечность которых не определена. Кроме этого, достаточно хорошо изучена структура группы В0(2,5), и если 5(2,5) конечна, то В(2,5) ~ Д)(2,5). Особую интригу придает тот факт, что при показателях п = 4ип = 6 бернсайдовы группы конечны. В связи с чем, представляется актуальным создание новых методов, алгоритмов и программ для решения проблем бернсайдового типа.

При неоспоримых преимуществах применения ЭВМ для исследования сложных систем у этого метода имеются и свои недостатки [45,76]. Как было сказано, совершенствование вычислительной техники привело к тому, что она начала использоваться при доказательстве теорем.

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

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

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

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

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

2. Создать методологию компьютерного моделирования систем указанного вида.

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

4. На основе указанного комплекса алгоритмов получить критерии конечности и бесконечности бернсайдовых и других конечнопорож-денных периодических групп.

5. Провести компьютерное моделирование бернсайдовой группы В(2,5) на предмет определения ее структуры.

6. При помощи моделирования групп на ЭВМ исследовать проблемы распознаваемости групп по их спектру.

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

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

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

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

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

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

4. На основе полученной методологии спроектирован и реализован на ЭВМ комплекс алгоритмов для вычисления дискретных алгебраических систем.

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

6. При помощи созданного комплекса алгоритмов проведено компьютерное моделирование бернсайдовой группы В{2,5) на предмет определения ее структуры. В терминах минимальных слов получены следующие результаты: a) Построен ранее неизвестный список соотношений для слов длины <33. b) При поэлементном сравнении с группой 50(2,5) выявлено, что если длины слов г/ и ио не превышают 29 и т = V — соотношение в группе Д)(2,5), то данное соотношение будет справедливо и в группе £?(2,5). c) В группе Во(2,5) на длинах 30-33 найдены такие 128 соотношений, что несправедливость хотя бы одного из них в группе В(2,5) будет означать бесконечность В(2,5). с1) В группе В0(2,5) найдено соотношение, длина левой и правой части которого равна 47, справедливость этого соотношения в В(2,5) означала бы наличие в В{2,Ъ) нециклической абелевой подгруппы порядка 52. е) Описаны дополнительные критерии конечности группы В(2,5), основанные на вычислении коммутаторов специального вида.

О Рассмотрен автоморфизм порядка 2 бернсайдовой группы Б0(2,5), отображающий образующие элементы Во(2,5) в обратные. Показано, что порядок централизатора указанного автоморфизма в группе Во(2,5) равен 516, а также определена структура данного централизатора. g) По результатам (£) предложен еще один дополнительный критерий конечности группы В{2,5).

7. На основе компьютерного моделирования с использованием созданного комплекса алгоритмов решен вопрос о распознаваемости по спектру группы 1/2(7) в классе всех групп, тем самым был получен положительный ответ на вопрос 16.57 из "Коуровской тетради".

Результаты, изложенные в п. 1-6, получены автором лично, а результат из п. 7 в нераздельном соавторстве с Д.В. Лыткиной. Достоверность всех результатов работы, полученных при помощи компьютерного моделирования, подтверждается на основе методологии мультиверсионного программирования.

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

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

1. Вторая-Всероссийской научная конференция "Проектирование инженерных и научных приложений в среде MATLAB". Москва, 2004 г.

2. Международная алгебраическая конференция "Мальцевские чтения". Новосибирск, 2004, 2005, 2008, 2009 гг.

3. Международная конференция, посвященная 75-летию со дня рождения профессора А.И. Кокорина "АЛиК-2004". Иркутск, 2004 г.

4. VI Международная конференция "Дискретные модели в теории управляющих систем", посвященная 80-летию со дня рождения C.B. Яблонского. Москва, 2004 г.

5. Международная алгебраическая конференция, посвященная 100-летию со дня рождения П'.Г. Конторовича и 70-летию-Л.Н. Шеврина. Екатеринбург, 2005 г.

6. VII Международная конференция "Дискретные модели в теории управляющих систем". Москва, 2006 г.

7. Международная алгебраическая конференция "Алгебра и ее приложения". Красноярск, 2007 г.

8. Международная алгебраическая конференция, посвященная 100-летию со дня рождения А.Г. Куроша. Москва, 2008 г.

9. V Российско-Германская школа-конференция "Распределенные и высокопроизводительные вычисления". Новосибирск, 2008 г.

10. Всероссийская конференция по математике и механике. Томск, 2008* г.

11. ИХ Международная конференция "Пограничные вопросы теории моделей-и универсальной алгебры". Новосибирск, 2009 г.

12. Международная алгебраическая конференция, посвященная 80-летию со дня рождения А.И. Кострикина. Нальчик, 2009 г.

Они неоднократно обсуждались на семинарах в Сибирском государственном аэрокосмическом университете, Институте математики СО РАН, Институте математики и механики УрО РАН, Сибирском федеральном университете и Красноярском государственном аграрном университете.

Публикации. По теме диссертации опубликовано более 30 работ [95-125], среди которых 11 в ведущих рецензируемых журналах из перечня ВАК России, 2 монографии, а также 4 программы для ЭВМ, зарегистрированные в отраслевом фонде алгоритмов и программ.

Проекты. Работа была выполнена в рамках следующих проектов:

1. Грант РФФИ (проект 03-01-00905).

2. Грант,Президента России по науке (проект МК-2494.2008.1).

3. Грант АВЦП "Развитие научного потенциала высшей школы" (проект 2.1.1/3023).

4. Грант РФФИ (проект 09-01-07177-а).

Награды. По результатам работы автор был удостоен

1. Государственной премии Красноярского края по науке — 2006 г.

2. Премии главы города Красноярска по науке — 2009 г.

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

Заключение

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

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

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

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

4. На основе полученной методологии спроектирован и реализован на ЭВМ комплекс алгоритмов для вычисления дискретных алгебраиче ских систем.

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

6. При помощи созданного комплекса алгоритмов проведено компьютерное моделирование бернсайдовой группы £(2,5) на предмет определения ее структуры. В терминах минимальных слов получены следующие результаты: a) Построен ранее неизвестный список соотношений для слов длины < 33. b) При поэлементном сравнении с группой £0(2,5) выявлено, что если длины слов у и т не превышают 29 и и> — у — соотношение в группе Д)(2,5), то данное соотношение будет справедливо и в группе £(2,5). c) В группе £о(2,5) на длинах 30-33 найдены такие 128 соотношений, что несправедливость хотя бы одного из них в группе В{2,5) будет означать бесконечность £(2,5). с!) В группе £о(2,5) найдено соотношение, длина левой и правой части которого равна 47, справедливость этого соотношения в £(2,5) означала бы наличие в £(2,5) нециклической абелевой подгруппы порядка 52. е) Описаны дополнительные критерии конечности группы £(2,5), основанные на вычислении коммутаторов специального вида.

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

2?о(2,5) равен 516, а также определена структура данного централизатора. По результатам (0 предложен еще один дополнительный критерий конечности группы В(2,5). I

7. На основе компьютерного моделирования с использованием созданного комплекса алгоритмов решен вопрос о распознаваемости по спектру группы Ь2{1) в классе всех групп, тем самым был получен положительный ответ на вопрос 16.57 из "Коуровской тетради".

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

Автор сердечно благодарит своих научных консультантов — профессоров А.Н Антамошкина и А.К. Шлёпкина за всестороннюю поддержку, полученную во время написания диссертационной работы. Также автор благодарен всем студентам, аспирантам и профессиональным программистам, в частности, С.А. Тарасову, Ю.С. Тарасову и Е.В. Грачеву, которые провели экспертизу результатов, полученных при помощи ЭВМ. Кроме этого, автор очень признателен Д.А. Кузьмину за помощь, полученную при организации вычислительного процесса на суперкомпьютере ИКИТ СФУ.

1. Адян С.И. Об алгоритмических проблемах в эффективно полных классах групп // Докл. АН СССР. 1958. 123, № 1. С. 3-16.

2. Адян С.И. Проблема Бернсайда и тождества в группах. М.: Наука. 1975. 335 с.

3. Адян С.И. Проблема Бернсайда о периодических группах и смежные вопросы // Совр. пробл. матем. 2003. Вып. 1. С. 5—28.

4. Алешин C.B. Конечные автоматы и проблема Бернсайда о периодических группах // Мат. заметки. 1972. Т. 11, № 3. С. 319-328.

5. Ануфриев И.Е., Смирнов А.Б., Смирнова E.H. MATLAB 7. СПб: БХВ-Петербург, 2005. 1104 с.

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

7. Богомолов A.M., Салий В.М. Алгебраические основы теории дискретных систем. М.: Наука. Физматлит, 1997. 368 с.

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

9. Вавилов Н. А., Мысовских В. И., Тетерин Ю. Г. Вычислительная теория групп в Петербурге // Зап. научн. сем. ПОМИ 1997 № 236. С. 42-49.

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

11. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. М.: ФИЗМАТЛИТ, 2006. 320 с.

12. Голод Е.С. О ниль-алгебрах и финитно аппроксимируемых груп-, пах // Изв. АН СССР. Сер. матем. 1964. Т. 28, №2. С. 273-276.

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

14. Горенстейн. Д. Грандиозная теорема // В мире науки 1986. № 2 С. ,62-74.

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

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

17. Зельманов Е.И. Решение ослабленной проблемы Бернсайда для 2групп // Матем. сб. 1991. 182(4) С. 568-592.i 1

18. Иванов Ф.А., Скопин А.И. Максимальная 2-порожденная трансме-табелева группа первого типа экспоненты 9 // Алгебра и анализ. 1990. 2(6) С. 150-160.

19. Ковалев И.В., Новой A.B., Штенцель A.B. Оценка надежности мультиверсионной программной архитектуры систем управленияи обработки информации // Вестн. Сиб. гос. аэрокосмич. ун-та.i i2008, Вып. 1(20). С. 50-52.

20. Кострикин А.И. Решение ослабленной проблемы Бернсайда для показателя 5 // Изв. АН СССР. Сер. матем. 1955. Т. 19, № 3. С. 233-244.

21. Кострикин А.И. О кольцах Ли, удовлетворяющих условию Энгеля // ДАН СССР. 1956. Т. 108, № 4. С. 580-582.

22. Кострикин А.И. О проблеме Бернсайда // ДАН СССР. 1958.

23. Т. 119, № 6. С. 1081-1084.

24. Кострикин А.И. Вокруг Бернсайда. М.: Наука, 1986. 232 с.

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

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

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

28. Лобыч 'В.П. Скопин А.И. О соотношениях в группах экспоненты 8 // Зап. научн. сем. ЛОМИ. 1976. № 64. С. 92-94.

29. Лысёнок И.Г. Бесконечные бернсайдовы группы чётного периода // Изв. РАН. Сер. матем. 1996. 60(3). С. 3-224.

30. Лыткина Д.В. Строение группы, порядки элементов которой не превосходят числа 4. // Сиб. матем. журнал. 2007. Т. 48, № 2. С. 353-358.

31. Мазуров В.Д. Группы с заданным спектром // Известия Уральского гос. у-та. Серия: математика и механика. 2005. Т. 36, № 7. С 119-138.

32. Мальцев А.И. Алгебраические системы. М.: Наука, 1970. 392 с.

33. Марков А. А. Невозможность некоторых алгорифмов в теории ассоциативных систем // Докл. АН СССР. 1947. Т. 55, № 7. С. 587-590.

34. Методологические проблемы кибернетики: в 2-х т. М.: МГУ, 1970. Т. 1-2.

35. Моисеев H.H. Математические задачи системного анализа. М.: Наука, 1981. 488 с.

36. Монарх Е.И., Скопин А.И. Диалоговая система символьных вычислений в группах Берндсайдовского типа // Зап. научн. сем. ЛОМИ. 1982. № 114. С. 164-173.

37. Мысовских В.И., Скопин А.И. Свойства вложения непримарных подгрупп симметрической группы степени восемь // Зап. научн. сем. ПОМИ. 1997. № 236. С. 124-128.

38. Мысовских В.И., Скопин А.И. Вложения подгрупп в симметрической группе степени девять // Зап. научн. сем. ПОМИ. 1999. № 265. С. 281-284.

39. Мысовских В.И., Скопин А.И. Вложения непримарных подгрупп в симметрической группе Sg // Зап. научн. сем. ПОМИ. 2001. № 281. С. 237-252.

40. Нерешённые вопросы теории групп. Коуровская тетрадь, вып. 16 / под. общей редакцией В.Д. Мазурова, Е.И. Хухро. Новосибирск: ИМ СО РАН, 2006. 193 с.

41. Нильсен М., Чанг И. Квантовые вычисления и квантовая информация / пер. с англ. М.: Мир, 2006. 824 с.

42. Новиков П.С. Об алгоритмической неразрешимости проблемы тождества слов в теории групп // Труды МИАН им. В.А. Стеклова. 1955. № 44. С. 1-144.

43. Новиков П.С., Адян С.И. О бесконечных периодических группах. I, II, III // Изв. АН СССР. Сер. матем. 1968. № 32(1), с. 212-244; № 32(2), с. 251-524; № 32(3), с. 709-731.

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

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

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

47. Прескилл Дж. Квантовая информация и квантовые вычисления. Т. 1 / пер. с англ. М.-Ижевск: НИЦ "Регулярная и хаотическиая динамика"; Институт компьютерных исследований, 2008. 464 с.

48. РБК — "РосБизнесКонсалтинг". Общество. Д. Медведев: Россия будет вкладывать средства в суперкомпьютеры // URL: http://top.rbc.ru/society/28/07/2009/318377.shtml (дата обращения: 12.08.2009).

49. Рутковская Д., Пилинсьский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы / пер. с польск. М.: Горячая линия-Телеком, 2007. 452 с.

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

51. Санов И.Н. Решение проблемы Бернсайда для периода 4 // Учен, записки ЛГУ. Сер. матем. 1940. № 10. С. 166-170.

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

53. Серр Ж.П. Алгебры Ли и группы Ли / пер. с француз. М.: Мир,1969. 376 с.1

54. Скопин А.И. О собирательной формуле // Зап. научн. сем. ЛОМИ. 1974. № 46 С. 53-58.

55. Скопин А.И. О соотношениях в группах экспоненты 8 // Зап. научн. сем. ЛОМИ. 1976. № 57. С. 129-169.

56. Скопин А.И. Трансметаабелевы группы // Зап. научн. сем. ЛОМИ. 1978. № 75. С. 159-163.

57. Скопин А.И. Метаабелева группа экспоненты 9 с двумя образующими // Зап. научн. сем. ЛОМИ. 1980. № 103. С. 124-131.

58. Скопин А.И. Факторы нильпотентного ряда некоторых метаабеле-вых групп примарной экспоненты // Зап. научн. сем. ЛОМИ. 1983. № 132. С. 129-163.

59. СкопинЛ.И. Исследование на БЭСМ-б структуры нильпотентного | ряда метаабелевой 2-порожденной группы экспоненты 27 // Зап.научн. сем. ЛОМИ. 1987. № 160. С. 247-256.

60. Скопин А.И. О реализации вычислений на ЭВМ в трансметаабе-левых группах // Вестн. ЛГУ. Серия 1. 1988. Вып. 1. С. 20-23.

61. Скопин А.И. Тождество Якоби в собирательной формуле Ф. Холла в трансметаабелевых группах двух типов // Зап. научн. сем. ЛОМИ. 1989. № 175. С. 106-112.I

62. Скопин А.И. Нижний центральный ряд максимальной 2-порожденной трансметабелевой группы I типа экспоненты 8 // Алгебра и анализ. 1990. 2(5) С. 197-219.

63. Скопин А.И. Базисы свободных метаабелевых и трансметаабелевых групп // Зап. научн. сем. ЛОМИ. 1991. № 191. С. 126-139.

64. Скопин А.И. Графическое построение собирательной формулы для некоторых типов групп // Зап. научн. сем. ЛОМИ. 1991. № 191. С. 140-151.

65. Скопин А.И., Тетерин Ю.Г. Ускорение алгорифма построения собирательной формулы Ф. Холла // Зап. научн. сем. ПОМИ. 1995. № 227. С. 106-112.

66. Скопин А.И., Тетерин Ю.Г. О компьютерных вычислениях для трансметабелевых групп экспоненты 16, 25 и 27 // Зап. научн. сем. ПОМИ. 1997. № 236. С. 162-165.

67. Царев Р. Ю. Многоатрибутивное принятие решений в мультивер-сионном проектировании: Монография. Красноярск: ИПЦ КГТУ, 2005. 156 с.

68. Царев Р. Ю. Система поддержки принятия решений при формировании мультиверсионного программного обеспечения // Программные продукты и системы. 2007. № 1(77). С. 57—59.

69. Шунков В.П. О периодических группах с почти регулярной инволюцией // Алгебра и логика. 1972. Т. 11, № 4. С. 470-494.

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

71. Appel К., Haken W. Every planar map is four colorable. Part I, Discharging // Illinois J. Math. 1977. № 21. P. 429-490.

72. Appel K., Haken W. Every planar map is four colorable. Part II, Reducibility // Illinois J. Math. 1977. № 21. P. 491-567.

73. Batty M., Braunstein S.L., Duncan A.J., Rees S. Quantum algorithms in group theory // Contemporary Math. AMS. 2004. № 349. P. 1-62.

74. Boone W. W. The word problem // Ann. Math. 1959. 70, № 2. P 207-265.

75. Booth R., Bormotov D., Borovik A. Genetic algorithms and equations in free groups and semigroups // Contemporary Math. AMS. 2004. № 349. P. 63-81.

76. Brian D. Whither Mathematics? // Notices of the AMS. 2005. Vol. 52, № 11. P. 1350-1356.

77. Burnside W. On an unsettled question in the theory of distinctinuous groups // J. Pure Appl. Math. 1902. № 33. P. 393-399.

78. Dehn M. Über unendliche diskontinuierliche Gruppen // Math. Ann. 1911. № 71. P. 116-144.

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

80. Hall M., Jr. Solution of the Burnside problem for exponent six, III//J. Math. 1958. № 2. P. 764-786.

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

82. Havas G., and Newman M. Application of Computers to Questions Like Those of Burnside // In Burnside Groups. Proceedings of a Workshop held at the University of Bielefeld, Bielefeld, June-July 1977. New York: Springer-Verlag, 1980. P. 211-230.

83. Higman R. On finite groups of exponent five // Proc. Cambr. Phil. Soc. 1956. № 52. P. 381-390.

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

85. Huppert В. Endliche Gruppen I. Berlin-Heidelberg-NewYork: Springer Verlag, 1983. 800 p.

86. Ivanov S.V. The free Burnside groups of sufficiently large exponents // Int. J. of Algebra and Computation. 1994. № 4.

87. Leyi F., van der Waerden, B. L. Über eine besondere Klasse von Gruppen // Abh. Math. Sem. Univ. Hamburg. 1933. № 9. P 154158.

88. MAGMA Computational Algebra ' System. URL: http://magma.maths.usyd.edu.au/magma/ (дата обращения: 30.05.2009).

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

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

91. Miasnikov A.D., Myasnikov A.G. Whitehead method and genetic algorithms // Contemporary Math. AMS. 2004. № 349. P. 89-114.

92. O'Brien E., Newman, M. Application of Computers to Questions Like

93. Those of Burnside, II // Internat. J. Algebra Comput. 1996. № 6. P. 593-605.

94. O'Brien E., Vaughan Lee M. The 2-generaror restricted Burnside group of exponent 7 // Internat. J. Algebra Comput. 2002. № 12. P. 575-592.

95. Post E. Recursive unsolvabiiity of a problem of Thue // J. Symbol. Log. 1947. 12, № 1. P. 1-11.

96. Rabin M. O. Recursive unsolvabiiity of group theoretic problems // Ann. Math. 1958. 67, № 1. P. 172-104.

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

98. Shi W.J. A characteristic property of PSL2{7) // J.Austral. Math. Soc. Ser. A. 1984. 36(3). P. 354-356.

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

100. Tobin J. On Groups with Exponent 4. Thesis. Manchester, England: University of Manchester, 1954.

101. Thompson J.G. Finite groups with fixed-point-free automorphisms of prime order// Proc. Nat. Acad. Sci. U.S.A. 1959. № 45. P. 578-581.

102. Vaughan Lee M. The restricted Burnside problem. New York: Clarendon Press, 1993. 210 p.

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

104. Кузнецов A.A., Шлёпкнн А.К. К вопросу о построении апериодических последовательностей // Вестн. Красноярского гос. у-та. Серия: физ.-мат. науки. 2004. № 3. С. 90-94.

105. Кузнецов A.A., Антамошкин А.Н., Шлёпкин А.К. Моделирование периодических групп // Системы управления и информационные технологии. 2008. № 2(32). С. 4-8. '

106. Кузнецов A.A., Тарасов Ю.С. Модификация алгоритма моделировании периодических групп // Вестн. Сиб. гос. аэрокосмич. ун-та. 2008. Вып. 2(19). С. 42-43.

107. Кузнецов A.A., Антамошкин. А.Н., Шлёпкин А.К. Примене1ние независимых слов при моделировании периодических групп // Системы управления и информационные технологии. 2008. № 2.2(32). С. 286-289.

108. Кузнецов A.A. Теоретико-множественный анализ алгебраических систем в вопросах распознавания групп по их спектру // Вестн. Сиб. гос. аэрокосмич. ун-та. 2009. Вып. 2(23). С. 38-40.

109. Кузнецов A.A., Шлёпкин А.К., Тарасов С.А. Обобщенный алгоритм моделирования периодических групп // Вестн. Новосибирского гос. ун-та. Серия: математика, механика, информатика. 2009. № 2. С. 47-54.

110. Кузнецов A.A., Шлёпкин А.К., Антамошкин А.Н. Об одном критерии конечности бернсайдовой группы 5(2,5) // Вестн. Сиб. гос. аэрокосмич. ун-та. 2009. Вып. 2(23). С. 28-30.

111. Кузнецов A.A., Шлёпкин A.K. Сравнительный анализ бернсайдо-вых групп В(2,5) и Д)(2,5) // Труды Института математики и механики УрО РАН. 2009. Том 15, № 2. С. 125-132.

112. Кузнецов A.A. Моделирование периодических групп в задачах распознавания групп по их спектру // Информатика и системы управления. 2009. № 2(20). С. 19-23.

113. Кузнецов A.A., Антамошкин А.Н., Шлёпкин А.К. Моделирование периодических групп на основе теоретико-множественного анализа алгебраических систем // Системы управления и информационные технологии. 2009. № 2(36). С. 32-35.

114. Кузнецов A.A., Шлёпкин А.К., Антамошкин А.Н. Компьютерное моделирование бернсайдовой группы В(2,5) // Вестн. Сиб. гос. аэрокосмич. ун-та. 2009. Вып. 3(24). С. 27-29.1. Прочие публикации

115. Кузнецов A.A. Некоторые комбинаторные вопросы в периодических группах: дис. . канд. физ.-мат. наук. Красноярск, 2006. 102 с.

116. Кузнецов A.A., Лыткина Д.В., Тухватуллина JI.P., Филиппов К.А. Группы с условием насыщенности. Красноярск: КрасГАУ, 2009. 270 с.

117. Кузнецов A.A., Кузьмин Д.А., Лыткина Д.В., Тухватуллина Л.Р., Филиппов К.А. Компьютерные алгоритмы теоретико-множественного анализа сложных алгебраических систем Красноярск: КрасГАУ, 2009. 200 с.

118. Кузнецов A.A., Шлёпкин A.K. К вопросу о конечности свободных бернсайдовых групп В(т,п) // Матем. системы. 2005. Вып. 3. С. 36-38.1

119. Кузнецов A.A. К вопросу о конечности свободной бернсайдовой группы В{2,5) // Матем. системы. 2005. Вып. 4. С. 38-47.

120. Кузнецов A.A. К вопросу о распознавании группы Ь2{7) по спектру // Сиб. электр. матем. изв. 2005. Т. 2. С. 250-252.

121. Кузнецов A.A. К вопросу о конечности свободной бернсайдовой группы .0(2,5) // Вестн. молодых ученых КрасГАУ. 2005. № 3. С. 49-57.

122. Кузнецов A.A., Тихомирова М.В. К вопросу о конечности группыI2,5) // Матем. системы. 2006. Вып. 5. С. 15-19.

123. Кузнецов A.A., Тарасов С.А., Тухватуллина JI.P. Алгоритм перечисления группы // Матем. системы. 2007. Вып. 6. С. 63-72.

124. Kuznetsov A.A., Lytkina D.V. Recognizability by spectrum of the group 1/2(7) in the class of all groups // Сиб. электр. матем. изв. 2007. Т. 4. С. 136-140.

125. Кузнецов A.A., Тарасов С.А., Шлёпкин А.К. К вопросу о конечности двупорожденной бернсайдовой группы периода 5 // Матем. системы. 2009. Вып. 7. С. 6-9.

126. Кузнецов A.A., Шлёпкин А.К. К вопросу о вычислении элементов в свободных бернсайдовских группах // Труды Второй Всероссийской научной конф. "Проектирование инженерных и научных приложений в среде MATLAB". М., 2004. С. 215-221.

127. Кузнецов A.A., Шлёпкин А.К. Использование параллельных вычислений для нахождения элементов в свободных бернсайдовских группах В(т,п) // Труды IV Межрегиональной школы-семинара "Распределённые и кластерные вычисления", Красноярск, 2005. С. 136-140.

128. Кузнецов A.A., Шлёпкин А.К., Тарасов С.А. Алгоритмические вопросы в группах бернсайдового типа // Материалы Международной алгебраической конф.: К 100-летию со дня рождения П.Г. Кон-торовича и 70-летию JI.H. Шеврина. Екатеринбург, 2005. С. 55-56.

129. Кузнецов A.A., Шлёпкин А.К., Тарасов С.А. О независимых словах в группах бернсайдового типа // Труды VII Международной конф. "Дискретные модели в теории управляющих систем". М., 2006. С. 181-182.

130. Разработки, зарегистрированные в отраслевом фонде алгоритмов и программ

131. Кузнецов A.A., Тарасов С.А., Шлёпкин А.К. Вычисление элементов и соотношений в периодических группах // М.: ВНТИЦ, 2008. № 50200800998.

132. Кузнецов A.A., Тарасов С.А., Шлёпкин А.К. Применение независимых слов при моделировании периодических групп // М.: ВНТИЦ, 2008. № 50200801020.

133. Кузнецов A.A. Приведение элементов бернсайдовых групп к нормальной коммутаторной форме // М.: ВНТИЦ, 2008. № 50200802050.

134. Кузнецов A.A. Параллельный алгоритм вычисления элементов и соотношений в периодических группах // М.: ВНТИЦ, 2009. № 502009000338.