Реферат "Программные средства визуализации решений задач теории групп (пакет Gap)"

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ

ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ М. Е. ЕВСЕВЬЕВА»

Факультет физико-математический

Кафедра информатики и вычислительной техники

РЕФЕРАТ

Программные средства визуализации решений задач теории групп (пакет GAP)

Автор работы _____________________________________ М. А. Жалдыбина

Направления подготовки 44.03.05 Педагогическое образование

Профиль Математика. Информатика

Руководитель работы

канд. физ. мат. наук, доцент__________________________Т. В. Кормилицына

Оценка __________

Саранск 2021

Введение 3

Система компьютерной алгебры GAP 4

Язык программирования 7

Примеры задач 10

Список использованных источников 12

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

В настоящее время основы теории групп стала составной частью подготовки не только бакалавров математиков, но и специалистов в области физики, химии и информатики. Основные идеи теории групп изучаются студентами и в рамках таких фундаментальных математических дисциплин как «Алгебра», «Алгебра и геометрия», «Геометрия и алгебра» и других.

Разработка системы компьютерной алгебры GAP, название которой расшифровывается как "Groups, Algorithms and Programming", была начата в 1986 г. в г.Аахен, Германия. В 1997 г. центр координации разработки и технической поддержки пользователей переместился в Университет г.Сент-Эндрюс, Шотландия. В настоящее время GAP является уникальным всемирным совместным научным проектом, объединяющим специалистов в области алгебры, теории чисел, математической логики, информатики и др. наук из различных стран мира. Основные центры разработки системы находятся в университетах г.Сент-Эндрюс (Шотландия), гг. Аахен, Брауншвейг (Германия) и Университете штата Колорадо (США). Текущая версия системы - GAP 4.4.10 - была выпущена в октябре 2007 г.

Изначально система GAP разрабатывалась под Unix, а затем была портирована для работы в других операционных системах. В настоящее время она работает в разнообразных версиях Unix/Linux, а также в Windows и Mac OS. Заметим, что ряд пакетов, расширяющих функциональность системы, работает только в среде Unix/Linux.

GAP является свободно распространяемой, открытой и расширяемой системой. Она распространяется в соответствии с GNU Public License. Cистема поставляется вместе с исходными текстами, которые написаны на двух языках: ядро системы написано на Си, а библиотека функций - на специальном языке, также называемом GAP, который по синтаксису напоминает Pascal, однако является объектно-ориентированным языком. Пользователи могут создавать свои собственные программы на этом языке, и здесь исходные тексты являются незаменимым наглядным пособием. Наконец, разработчики программ для GAP могут оформить свои разработки в виде пакета для системы GAP и представить их на рассмотрение в Совет GAP. После прохождения процедуры рецензирования и одобрения советом GAP такой пакет включается в приложение к дистрибутиву GAP и распространяется вместе с ним. Процедура рецензирования позволяет приравнивать принятые Советом GAP пакеты к научной публикации, и ссылаться на них наравне с другими источниками.

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

• ядра системы, обеспечивающего поддержку языка GAP, работу с системой в программном и интерактивном режиме;

• библиотеки функций, в которой реализованы разнообразные алгебраические алгоритмы (более 4000 пользовательских функций, более 140000 строк программ на языке GAP);

• библиотеки данных, включая, например, библиотеку всех групп порядка не более 2000 (за исключением 49487365422 групп порядка 1024, точное количество которых, кстати, также было определено с помощью системы GAP), библиотеку примитивных групп подстановок, таблицы характеров конечных групп и т.д., что в совокупности составляет эффективное средство для выдвижения и тестирования научных гипотез;

• обширной (около полутора тысяч страниц) документации, доступной в разнообразных форматах (txt, pdf, html), а также через Интернет.

Система GAP была задумана как инструмент комбинаторной теории групп - раздела алгебры, изучающего группы, заданные порождающими элементами и определяющими соотношениями. В дальнейшем, с выходом каждой новой версии системы сфера ее применения охватывала все новые и новые разделы алгебры. В разнообразии областей алгебры, охватываемых GAP сегодня, можно убедиться, даже только лишь прочитав названия разделов обширнейшей документации по системе, занимающей около 1500 страниц (которая, кстати, не только входит в состав дистрибутива, но и доступна через Интернет). Вычислительная мощь системы может быть продемонстрирована находящимся на ее сайте примером определения того, что кубик Рубика имеет 43252003274489856000 различных состояний, и сборки кубика Рубика из произвольного начального состояния в среднем за 100 ходов.

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

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

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

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

При успешном запуске GAP на экране появится эмблема GAP. После нее будет напечатана дополнительная информация о версии системы и установленных компонентах, например:

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

Символы и категории слов в GAP. GAP воспринимает следующие символы: цифры, буквы (верхний и нижний регистры), пробел, символы табуляции и новой строки, а также специальные символы.

Составленные из символов слова относятся к следующим категориям:

• ключевые слова (зарезервированные последовательности букв нижнего регистра);

• идентификаторы (последовательности цифр и букв, содержащие не менее одной буквы и не являющиеся ключевым словом);

• строки (последовательности произвольных символов, заключенная в двойные кавычки);

• целые числа (последовательности цифр);

• операторы и ограничители в соответствии со следующим списком

Ключевые слова:

Идентификаторы состоят из букв, цифр, символов «_», и должны содержать не менее одной буквы или символа «_». При этом регистр является существенным. Примеры идентификаторов:

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

Приведём список некоторых групп из библиотеки системы GAP с указанными в скобках командами обращения к этим группам, причём параметр filt в этих командах определяет способ задания группы. Например, при filt=IsPermGroup получаем подстановочное представление группы, а при filt = IsMatrixGroup — её линейное представление.

Циклическая группа порядка n (CyclicGroup( [filt, ]n ));

Абелева группа, разложимая в прямую сумму групп порядков ints[1],ints[2],...,ints[n] для списка ints натуральных чисел (AbelianGroup( [filt,]ints ));

Группа диэдра порядка n (DihedralGroup( [filt, ]n ));

Знакопеременная группа степени deg (AlternatingGroup( [filt, ]deg ));

Симметрическая группа степени deg (SymmetricGroup( [filt, ]deg ));

Группа Матье степени degree (MathieuGroup( [filt, ]degree ));

Общая линейная группа обратимых d × d матриц над кольцом R (GL([filt, ]d, R ));

Общая линейная группа обратимых d × d матриц над конечным полем из q элементов (GL( [filt, ]d, q ));

Специальная линейная группа обратимых d × d матриц над кольцом R (SL( [filt, ]d, R ));

Специальная линейная группа обратимых d × d матриц с единичным определителем над конечным полем из q элементов (SL( [filt, ]d, q ));

Проективная специальная линейная группа, изоморфная фактор-группе группы SL(d, q) по её центру (PSL( [filt, ]d, q ));

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

Задача 1. Симметрическая группа имеет, кроме себя самой и единичной подгруппы, лишь следующие нормальные подгруппы[1]:

а) знакопеременную группу U ;

б) «четверную группу Клейна», состоящую из подстановок:

(1), (1 2) (3 4), (1 3) (2 4), (1 4) (2 3).

Последняя группа абелева.

c:=SymmetricGroup(4); Sym( [ 1 .. 4 ] )

gap NormalSubgroups(c);

[ Group(()), Group([ (1,4)(2,3), (1,3)(2,4) ]), Group([ (2,4,3), (1,4)(2,3), (1,3)(2,4) ]), Sym( [ 1 .. 4 ] ) ]

gap z:=Group([(2,4,3),(1,4)(2,3),(1,3)(2,4)]); Group([ (2,4,3), (1,4)(2,3), (1,3)(2,4) ])

gap IsAbelian(z); false

gap x:=Group([(1,4)(2,3),(1,3)(2,4)]); Group([ (1,4)(2,3), (1,3)(2,4) ])

gap IsAbelian(x); true

Задача 2. Найти число Силовских 5-подгрупп в [4].

gap S:= SymmetricGroup(5); Sym( [ 1 … 5 ] )

gap A5:= CommutatorSubgroup(S, S); Group( [ ( 1, 2, 3), (2, 3, 4), (2, 4) (3, 5) ] ) # задание исходной группы

gap P5:=SylowSubgroup(A5,5); Group( [ ( 1, 5, 4, 3, 2) ] ) # по второй теореме Силова все Силовские р-подгруппы сопряжены, то функция SylowSubgroup возвращает только одну подгруппу, которая является представителем некоторого класса сопряженных подгрупп

gap C5:=ConjugasyClassSubgroups(A, P5); Group( [ ( 1, 5, 4, 3, 2) ] )^G # чтобы получить остальные подгруппы из этого класса, сначала нужно создать класс сопряженных подгрупп данной группы с заданным представителем, а затем получить список содержащихся в нем подгрупп

gap L5:= AsList(C5); [ Group( [ ( 1, 5, 4, 3, 2) ] ), Group( [ ( 1, 3, 5, 4, 2) ] ), Group( [ ( 1, 4, 3, 5, 2) ] ), Group( [ ( 1, 4, 5, 2, 3) ] ), Group( [ ( 1, 5, 2, 4, 3) ] ), Group( [ ( 1, 5, 3, 2, 4) ] )

gap H:= Length(L5); 6

1. Ван дер Варден, Б.Л. Алгебра / Б. Л. Ван дер Варден – М.: Наука, 1976. - 623 с.

2. Кормилицына, Т. В. Решение задач теории групп в системе компьютерной алгебры GAP / Т. В. Кормилицына, С. М. Миронова // Организация проблемного обучения в школе и вузе / Межвузовский сборник научно-методических трудов. Вып. 3 / Мордов. гос. пед. ин-т – Саранск, 2008. – С. 147 – 149.

3. Кормилицына, Т. В. Преобразование симметрии и дискретно-групповой анализ обыкновенных дифференциальных уравнений / Т. В. Кормилицына // Технические и естественные науки: проблемы, теория, эксперимент: межвуз. сб. науч. тр. / Мордов. гос. университет. – Саранск, 2002. – С. 125 – 128.

4. Кострикин, А.И. Введение в алгебру. Часть III/ Основные структуры / А. И. Кострикин – М.: ФИЗМАТЛИТ, 2004 – 495 с.

5. Ларин, С. В. Лекции по теории групп / – Красноярск.: 1994