Введение к работе
Актуальность темы. Современные научные данные и современные системные представления позволяют говорить о мире как о бесконечной иерархической системе систем. Н.Н. Моисеев определяет системный анализ, как совокупность методов, основанных на использовании ЭВМ и ориентированных на исследование сложных систем — технических, экономических, экологических и т. д.
Однако методология системного анализа в приведенных выше областях может быть спроецирована на изучение объектов из других разделов естествознания (математика, физика и т. д.). Например, в математике за последние десятилетия появилось новое направление — компьютерное доказательство теорем. Первым примером крупной математической теоремы, для доказательства которой был применен компьютер, стала теорема о четырех красках, доказанная в 1976 г. К. Аппелом и У. Хакеном. Конечно, указанное направление существенно использует методы информатики и вычислительной техники, что делает его междисциплинарным.
В диссертационной работе предлагается методология работы со сложными дискретными объектами, характеризующимися большим числом элементов и требующих применения высокопроизводительных ЭВМ. Для формального описания указанных объектов на компьютере необходимы теоретико-множественные представления — дискретные алгебраические системы. Алгебраической системой принято называть множество с заданным на нем набором операций, удовлетворяющим некоторой системе аксиом. Представление алгебраических систем в виде объектов, поддающихся вычислительной обработке, и ответ на три главных вопроса:
Что такое вычисление математического объекта?
Как его вычислить наиболее эффективно?
Каким образом обеспечить достоверность вычислений?
определяют основные задачи компьютерной алгебры.
Одним из важных и интересных направлений компьютерной алгебры является вычислительная теория групп, далее ВТГ. Объектом исследования данного направления являются алгебраические системы с одной бинарной операцией (группоиды, полугруппы, моноиды, группы и т. д.). В связи с всеобщей информатизацией период доминирова-
ния непрерывной математики в значительной мере сменился периодом преобладания дискретной математики. ВТГ находит многочисленные приложения как в самой математике, так и за ее пределами: в кристаллографии, в классической и квантовой механике, в теории элементарных частиц, в химии и биологии, в теории кодирования и теории сложности вычислений, в криптографии и т. д. Первые компьютерные программы для работы с группами были реализованы в начале 50-х годов XX века. С тех пор эта сфера научной деятельности получила широкое распространение, исследования по соответствующей тематике ведутся во многих научных центрах по всему миру. Привлечение фактического материала, получаемого при помощи символьных вычислений в различных классах групп, стало характерной чертой развития теории групп. В подтверждение этого факта уместно напомнить, что первоначальное построение многих простых спорадических групп существенно использовало вычисления на компьютере. Так, в 1982 году Р. Грисс-младший построил группу, названную "монстром" за то, что число её элементов равно
или приближенно 8 1053.
Рассматриваемые в рамках ВТГ алгебраические системы следует отнести к разряду сложных. Дело в том, что проблема тождества слов в группах, как показал П.С. Новиков, в общем случае алгоритмически неразрешима. Аналогичный результат для полугрупп получен независимо А.А. Марковым и Э. Постом. Алгоритмическая неразрешимость проблемы изоморфизма в группах была доказана СИ. Адяном и независимо М. Рабином. И, наконец, алгоритмическая неразрешимость проблемы сопряженности в группах была получена У. Буном. В то же время для частных случаев групп такие алгоритмы существуют. Главным образом, их применение связано с решением задач о конечности группы, определении ее структуры и изоморфизма с другими группами.
К важнейшему классу задач ВТГ относят бернсайдову проблематику. Проблема Бернсайда о периодических группах фиксированного периода была поставлена известным английским математиком У. Берн-сайдом в 1902 году в следующей форме.
Пусть xi,X2,...,xm — конечное число независимых элементов, порождающих группу G, в которой для любого элемента g выполнено соотношение дп = 1, где п — натуральное число. Будет ли
определенная таким образом группа конечной, и если да, то каков ее порядок?
Впоследствии эти группы получили название свободных бернсай-довых групп и обозначение В(т,п). Перечислим известные к настоящему времени результаты по данным группам. В(т,п) конечна для п = 2 (тривиальный случай), п = 3 (У. Бернсайд — 1902 г.), п = 4 (т = 2 — У. Бернсайд, т > 2 — И.Н. Санов — 1940 г.), п = б (М. Холл — 1958 г.). В(т,п) бесконечна для нечётных п > 665 (СИ. Адян, П.С. Новиков — 1975 г.); для четных: п > 248 и п делится на 29 (СВ. Иванов - 1994 г.), п = 16k > 8000 (И.Г. Лысёнок -1996 г.). Для других же показателей, наименьший из которых п = 5, вопрос о конечности В(т,п) остается открытым.
В 1950 году в работе В. Магнуса была сформулирована еще одна проблема, известная как "ослабленная проблема Бернсайда". В ней требовалось выяснить, существует ли максимальная конечная периодическая группа Во(т,п) с данным числом порождающих т и фиксированным периодом п. Связь ослабленной проблемы с основной проблемой Бернсайда сводится к тому, что если бы не существовало бесконечных периодических групп, то группа В(т,п) и была бы максимальной конечной периодической группой при этих тип. Первый результат по этой проблеме был получен в 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) ~ о(2,5). Особую интригу придает тот факт, что при показателях п = 4 и п = б бернсайдовы группы конечны. В связи с чем представляется актуальным создание новых методов, алгоритмов и программ для решения проблем бернсайдового типа.
При неоспоримых преимуществах применения ЭВМ для исследования сложных систем у этого метода имеются и свои недостатки. Как было сказано, совершенствование вычислительной техники привело к тому, что она начала использоваться при доказательстве теорем. Правомерно ли систематическое проведение доказательств, осуществляемых с помощью компьютера? С точки зрения математической традиции подобные доказательства неправомерны, поскольку процедура проверки корректности доказательства в данном случае весьма затруднительна. Поэтому, одной из актуальных задач системного анализа, становится разработка инструментария для обеспечения надежности и достоверности компьютерных доказательств.
Цель диссертационной работы — на основе методологии системного анализа создать и реализовать на ЭВМ комплекс алгоритмов для моделирования дискретных алгебраических систем.
Поставленная в диссертации цель достигается путем решения следующих задач:
-
Проанализировать существующие методы и алгоритмы, реализуемые на ЭВМ, для исследования дискретных алгебраических систем.
-
Создать методологию компьютерного моделирования систем указанного вида.
-
Спроектировать и реализовать на ЭВМ комплекс алгоритмов для моделирования дискретных алгебраических систем.
-
На основе указанного комплекса алгоритмов получить критерии конечности и бесконечности бернсайдовых и других конечнопо-рожденных периодических групп.
-
Провести компьютерное моделирование бернсайдовой группы (2,5) на предмет определения ее структуры.
-
При помощи моделирования групп на ЭВМ исследовать проблемы распознаваемости групп по их спектру.
-
Подтвердить достоверность полученных результатов, применив методологию мультиверсионного программирования.
Методы исследования. Основные результаты получены на основе методологии системного анализа, включающей в себя компьютерное моделирование, высокопроизводительные вычисления и мультиверси-онное программирование, а также дискретной математики и вычислительной теории групп.
Научная новизна диссертационной работы
-
Создана методология компьютерного моделирования дискретных алгебраических систем, основанная на представлении системы указанного типа в виде динамической системы специальных объектов.
-
Предложена концепция минимальных слов, которая позволяет создать единообразное представление рассматриваемых систем, что делает возможным их сравнение по способу вхождения минимальных слов в данные объекты.
-
Предложена концепция независимых слов, позволяющая существенно снизить вычислительную сложность алгоритмов моделирования дискретных алгебраических систем, а также значительно уменьшить объем используемой оперативной памяти ЭВМ.
-
На основе полученной методологии спроектирован и реализован на ЭВМ комплекс алгоритмов для вычисления дискретных алгебраических систем.
-
Для различных классов конечнопорожденных периодических групп доказаны критерии конечности и бесконечности группы.
-
При помощи созданного комплекса алгоритмов проведено компьютерное моделирование бернсайдовой группы (2,5) на предмет определения ее структуры. В терминах минимальных слов получены следующие результаты:
-
Построен ранее неизвестный список соотношений для слов длины < 33.
-
При поэлементном сравнении с группой о(2,5) выявлено, что если длины слов і; иго не превышают 29 и w = v — соотношение в группе >о(2,5), то данное соотношение будет справедливо и в группе (2,5).
-
В группе >о(2,5) на длинах 30-33 найдены такие 128 соотношений, что несправедливость хотя бы одного из них в группе (2,5) будет означать бесконечность (2,5).
d) В группе >о(2,5) найдено соотношение, длина левой и пра
вой части которого равна 47, справедливость этого соотношения
в (2,5) означала бы наличие в (2,5) нециклической абелевой
подгруппы порядка 52.
e) Описаны дополнительные критерии конечности группы (2,5),
основанные на вычислении коммутаторов специального вида.
-
Рассмотрен автоморфизм порядка 2 бернсайдовой группы о(2,5), отображающий образующие элементы 0(2,5) в обратные. Показано, что порядок централизатора указанного автоморфизма в группе о(2,5) равен 516, а также определена структура данного централизатора.
-
По результатам (f) предложен еще один дополнительный критерий конечности группы (2,5).
7. На основе компьютерного моделирования с использованием созданного комплекса алгоритмов решен вопрос о распознаваемости по спектру группы 2(7) в классе всех групп, тем самым был получен положительный ответ на вопрос 16.57 из "Коуровской тетради".
Достоверность всех результатов работы, полученных при помощи компьютерного моделирования, подтверждается на основе методологии мультиверсионного программирования.
Практическая значимость. Результаты диссертации могут быть использованы в системном анализе в качестве методологии исследования дискретных алгебраических систем, а также в компьютерной алгебре и вычислительной теории групп. Кроме того, на их основе могут быть организованы специальные учебные курсы по компьютерному моделированию сложных систем.
Апробация. Результаты диссертации докладывались автором на следующих международных и всероссийских конференциях:
1. Вторая Всероссийская научная конференция "Проектирование
инженерных и научных приложений в среде MATLAB". Москва,
2004 г.
2. Международная алгебраическая конференция "Мальцевские чте
ния". Новосибирск, 2004, 2005, 2008, 2009 гг.
-
Международная конференция, посвященная 75-летию со дня рождения профессора А.И. Кокорина "АЛиК-2004". Иркутск, 2004 г.
-
VI Международная конференция "Дискретные модели в теории управляющих систем", посвященная 80-летию со дня рождения СВ. Яблонского. Москва, 2004 г.
-
Международная алгебраическая конференция, посвященная 100-летию со дня рождения П.Г. Конторовича и 70-летию Л.Н. Шеврина. Екатеринбург, 2005 г.
-
VII Международная конференция "Дискретные модели в теории управляющих систем". Москва, 2006 г.
7. Международная алгебраическая конференция "Алгебра и ее прило
жения". Красноярск, 2007 г.
-
Международная алгебраическая конференция, посвященная 100-летию со дня рождения А.Г. Куроша. Москва, 2008 г.
-
V Российско-Германская школа-конференция "Распределенные и высокопроизводительные вычисления". Новосибирск, 2008 г.
-
Всероссийская конференция по математике и механике. Томск, 2008 г.
-
ИХ Международная конференция "Пограничные вопросы теории моделей и универсальной алгебры". Новосибирск, 2009 г.
-
Международная алгебраическая конференция, посвященная 80-летию со дня рождения А.И. Кострикина. Нальчик, 2009 г.
Они неоднократно обсуждались на семинарах в Сибирском государственном аэрокосмическом университете, Институте математики СО РАН, Институте математики и механики УрО РАН, Сибирском федеральном университете и Красноярском государственном аграрном университете.
Структура и объём работы. Диссертация состоит из введения, пяти глав основного текста, заключения, списка литературы и приложений.
Публикации. По теме диссертации опубликовано более 30 работ, среди которых 11 в ведущих рецензируемых журналах из перечня ВАК России, 2 монографии, а также 4 программы для ЭВМ, зарегистрированные в отраслевом фонде алгоритмов и программ. Список основных публикаций приведен в конце автореферата.
Проекты. Работа была выполнена в рамках следующих проектов:
-
Грант РФФИ (проект 03-01-00905).
-
Грант Президента России по науке (проект МК-2494.2008.1).
-
Грант АВЦП "Развитие научного потенциала высшей школы" (проект 2.1.1/3023).
-
Грант РФФИ (проект 09-01-07177-а).
Награды. По результатам работы автор был удостоен:
-
Государственной премии Красноярского края по науке — 2006 г.
-
Премии главы города Красноярска по науке — 2009 г.
Похожие диссертации на Комплекс алгоритмов компьютерного моделирования дискретных алгебраических систем
