Диплом, курсовая, контрольная работа
Помощь в написании студенческих работ

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

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

Одним из важных и интересных направлений компьютерной алгебры является вычислительная теория• групп (computational group theory), далее ВТ<�Г. Объектом исследования данного направления являются алгебраические системы с одной бинарной операцией (группоиды, полугруппы, моноиды, группы и т. д.). Как самостоятельное научное направление со своей проблематикой ВТГ оформилась после того как в 1911 г. М… Читать ещё >

Содержание

  • 1. Методологические концепции моделирования дискретных алгебраических систем
    • 1. 1. Представление дискретной алгебраической системы в виде динамической системы специальных объектов
    • 1. 2. Концепция минимальных слов
    • 1. 3. Концепция независимых слов
  • 2. Комплекс алгоритмов для моделирования бернсайдовых групп
    • 2. 1. Основные определения и предварительные леммы
    • 2. 2. Алгоритм
      • 2. 2. 1. Определение Кх (т, п) = (Ри ЛьСЪТХ)
      • 2. 2. 2. Построение К3(тп, п) для з >
      • 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. Построение Кв (т, п) для й >
      • 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 >
      • 2. 4. 3. Условие конечности группы В (т, п)
      • 2. 4. 4. Условие бесконечности группы В (т, п)
      • 2. 4. 5. Пример: моделирование группы В (2,3)
  • 3. Комплекс алгоритмов для моделирования произвольных конечнопорожден-ных периодических групп
    • 3. 1. Основные определения и замечания
    • 3. 2. Алгоритм-1У
      • 3. 2. 1. Определение Кх© = (Ри Аи СХ1ТХ)
      • 3. 2. 2. Построение Ка© для в >
      • 3. 2. 3. Условие конечности группы С?
      • 3. 2. 4. Пример: моделирование группы диэдра
      • 3. 2. 5. Пример: моделирование периодической группы, порожденной тремя инволюциями, с дополнительными ограничениями на порядки элементов
    • 3. 3. Алгоритм-У
      • 3. 3. 1. Определение К{в) = (А, Аъ СиТх)
      • 3. 3. 2. Построение К3(0) для в >
      • 3. 3. 3. Условие конечности группы С
      • 3. 3. 4. Пример: моделирование группы диэдра
    • 3. 4. Алгоритм-VI
      • 3. 4. 1. Определение Кг{С) = {РиАи Сх)
      • 3. 4. 2. Построение Ка ((3) для 5 >
      • 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 году Р. Грисс-младший построил группу, названную «монстром» за то, что число её элементов равно.

808 017 424 794 512 849 313 485 887 658 987 330 265 356 840 558 657 536, или приближенно 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)| = 22 728 (Е. О’Брайн, М. Ньюмен, 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)| = 720 416. Доказательство этого результата заняло около одного года непрерывного машинного счета. Среди отечественных исследователей особо стоит отметить работы А. И. Скопина и его учеников [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. На основе компьютерного моделирования с использованием созданного комплекса алгоритмов решен вопрос о распознаваемости по спектру группы ½(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−905).

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

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

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

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

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/318 377.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. Uber 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. Uber eine besondere Klasse von Gruppen // Abh. Math. Sem. Univ. Hamburg. 1933. № 9. P 154 158.
  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 ½(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. № 50 200 800 998.
  132. A.A., Тарасов С. А., Шлёпкин А. К. Применение независимых слов при моделировании периодических групп // М.: ВНТИЦ, 2008. № 50 200 801 020.
  133. A.A. Приведение элементов бернсайдовых групп к нормальной коммутаторной форме // М.: ВНТИЦ, 2008. № 50 200 802 050.
  134. A.A. Параллельный алгоритм вычисления элементов и соотношений в периодических группах // М.: ВНТИЦ, 2009. № 502 009 000 338.
Заполнить форму текущей работой

На отлично!