Алгоритмы решения стереометрических задач в системе GAP

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

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

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ОБРАЗОВАНИЯ

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

ИМЕНИ М. Е. ЕВСЕВЬЕВА»

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

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

РЕФЕРАТ

АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ СТЕРЕОМЕТРИИ В СИСТЕМЕ GAP

Выполнила: студентка группы МДМ-114

Э.С. Шокурова

Саранск 2019

Алгоритмы решения задач стереометрии в системе GAP

Системы компьютерной алгебры (СКА) становятся одним из обязательных компонентов компьютерных технологий, используемых в образовании. Такие системы пригодны для решения любой учебной задачи или проведения серьѐзного исследования, где требуется математика – от курсовой работы до научной или инженерной разработки высокого класса.

(с) GAP (от англ. Groups, Algorithms, Programming – Группы, Алгоритмы, Программирование) – свободно распространяемая, открытая и расширяемая система компьютерной алгебры, название которой означает "Groups, Algorithms and Programming". Является системой компьютерной алгебры, задуманной как инструмент вычислительной теории групп, и впоследствии распространившейся на смежные разделы алгебры. В настоящее время GAP является уникальным всемирным совместным научным проектом, объединяющим специалистов в области алгебры, теории чисел, математической логики, информатики и др. наук из различных стран мира. Разработка системы была начата в 1986 г. Первоначально GAP разрабатывался в г. Аахен, Германия (Lehrstuhl D fur Mathematik, RWTH). В настоящее время центр разработки GAP и технической поддержки его пользователей находится в Шотландии (School of Mathematical and Computational Sciences, University of St.-Andrews).

(с) Основные особенности GAP:

• язык программирования, внешне напоминающий Паскаль;

• стандартные типы основных алгебраических объектов: групп (подстановок, абстрактных, матричных), колец, полей;

• удобные типы переменных, в том числе оперативно изменяемые списки и записи;

• более 4 тысяч библиотечных функций;

• обширная библиотека данных, включая практически все группы, порядок которых не превосходит 1000;

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

• подробное и удобное описание (около 1600 стр.) в формате «гипертекст»;

• (с) бесплатное получение по сети Internet вместе с исходными текстами, являющимися незаменимым наглядным пособием для освоения GAP;

• работа в операционных системах DOS, Windows, Unix, Linux, MacOS;

• работа с процессором типа 386 и выше с ОЗУ от 8 Mb;

• занимаемое место на диске - от 10 до 100 Mb в зависимости от объема инсталляции;

• способность работать с ОЗУ до 128 Mb и файлом подкачки до 128 Mb.

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

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

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

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

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

(с) Язык программирования GAP Ключевые слова.

Ключевыми словами GAP являются следующие слова:

Выражения.

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

• операторы сравнения: =, , , =, in;

• арифметические операторы: +, -, *, /, mod, ^;

• логические операторы: not, and, or.

(с) Пример 1:

gap2*2;; #два знака ";" подавляют вывод на экран

gap2*2+9=Fibonacci(7) and Fibonacci(13) in Prime;

true

Сравнения выражений

Формат: left-expr = right-expr

left-exprright-expr

Примечание: любые объекты сравнимы между собой. Объекты различных типов всегда различны, т.е. = приведет к false, и – к true. Кроме того, для них определено отношение «меньше».

Операторы сравнения имеют больший приоритет по сравнению с логическими операторами, но меньший по сравнению с арифметическими. Например, a*b = c and d интерпретируется как ((a*b)=c) and d). Еще один пример (сравнение, левая часть которого является выражением):

gap 2 * 2 + 9 = Fibonacci(7);

true

(с) Арифметические операции

Формат:

+ right-expr

- right-expr

left-expr + right-expr

left-expr - right-expr

left-expr * right-expr

eft-expr / right-expr

left-expr mod right-expr

left-expr ^ right-expr

Значение, как правило, зависит от типа операндов. Mod определен только для целых и рациональных чисел. Для элемента группы ^ означает возведение в степень, если правый операнд - целое число, а если он – также элемент группы, то сопряжение с его помощью. Приоритет операторов (по убыванию):

1) ^

2) унарные + и –

3) *, /, mod

4) + и -

Пример: означает (-(2 ^ (-2)) * 3) + 1 .

Арифметические операторы имеют наивысший приоритет по сравнению с операторами сравнения и логическими операторами.

Команда присваивания.

Присваивания имеют формат var := expr;

Команда вызова процедуры.

Формат: procedure-var();

procedure-var(arg-expr {, arg-expr} );

Различие между процедурами и функциями введено для удобства, GAP же их не различает. Функция возвращает значение, но не производит побочных эффектов. Процедура не возвращает никакого значения, но производит какое-либо действие (например, процедуры Print, Append, Sort).

Команда IF.

Формат:

if bool-expr1 then statements1

{ elif bool-expr2 then statements2 }

[ else statements3 ]

fi;

При этом частей elif может быть произвольное количество или ни одной и часть else также может отсутствовать.

Функции.

Формат: function – var ()

function – var ( arg-expr {, arg-ident} );

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

Процесс компьютерного моделирования фигур и объектов аналитической геометрии состоит из трех этапов: на первом этапе в координатном представлении вычисляются результаты векторных операций; на втором этапе конструируются графические объекты, соответствующие этим операциям, наконец, на заключительном, третьем этапе, производится сборка сложных графических структур на основе простых. Сборка осуществляется с помощью команды display библиотеки Maple plots. Таким образом, можно сконструировать достаточно сложные многопараметрические программные процедуры, позволяющие контролировать свойства конструируемых графических объектов. Такие процедуры удобно объединить в пользовательскую библиотеку программных процедур.

Алгоритмы, которые могут использоваться к решению задач в стереометрии, компьютерное моделирование объектов стереометрии:

На третьем этапе компьютерного моделирования конструируются программные процедуры изображения геометрических фигур. Продемонстрируем пример создания процедуры Nagle(R,a,n,c) графического отображения призмы с ребром a (список), окрашенной в цвет c, в основании которой лежит правильный n-угольник, вписанный в окружность радиуса R:

VectorAlgebra[Nagle]:=proc(R,a,n,c) local

M,i,MN,Ma,MNa,ab,t,k,gab:

M:=(i)-[R*cos(2*Pi*i/n),R*sin(2*Pi*i/n),0]:

Ma:=(i)-[R*cos(2*Pi*i/n)+a[1],

R*sin(2*Pi*i/n)+a[2],a[3]]:

MN:=plots[polygonplot3d]([seq(Ma(i),i=1..n)],style

=WIREFRAME,color=c):MNa:=plots[polygon-

plot3d]([seq(M(i),i=1..n)]

,style=WIREFRAME,color=c):

ab:=(i,t)-[seq(M(i)[k]+a[k]*t,k=1..3)]:

gab:=(i)-

plots[spacecurve](ab(i,t),t=0..1,color=c):

plots[display](MN,MNa,seq(gab(i),i=1..n)):end

proc:

Результат исполнения этой процедуры показан на Рисунок 1:

Рисунок 1 – Графическая иллюстрация призмы VectorAlge- bra[Nagle](2,[1,2,3],5,red);

Пользовательская библиотека программных процедур "Vector-Algebra" содержит следующие процедуры:

• Reper(A,a,b,c,g,c1,c2,c3) – процедура графической иллюстрации координатного репера с опорной точкой A, и базисными векторами a,b,c, где g=n ´ m – количество отображаемых линий координатной сети, c1,c2,c3 – цвета соответствующих плоскостей.

• Reper_name(A,a,b,c,g,c1,c2,c3,p,t,r,d) – процедура графического изображения подписей к координатным осям репера. Где a,b,c – базисные векторы, g=n ´ m – количество отображаемых линий координатной сети, c1,c2,c3 – цвета соответствующих плоскостей, p,t,r – подписи к осям, d – цвет надписей на осях координат.

• Reper_pr (A,a,b,c,g,x1,y1,z1,x2,y2,z2,c1,c2, c3,c4,c5,p,t,r,d) – процедура графического изображения вектора с его проекциями в трехмерной системе координат. Эта процедура является комплексной, содержащей все выше перечисленные процедуры, вложенные друг в друга. Здесь a,b,c – координаты заданных векторов, x1,y1,z1 – координаты начала вектора, x2,y2,z2 – координаты конца вектора, c1,c2,c3 – цвета соответствующих плоскостей, c4 – цвет изображения вектора, c5 – цвет его проекции на координатные плоскости, d – цвет надписей на осях координат.

• parallelogram(A,a,b) – процедура графической иллюстрации параллелограмма где a, b, заданные векторы, приложенные к точке A.

• paralleiepiped_ABCD](A,a,b,c) и pyramid_ABCDE](A,a,b,c) – аналогичные процедуры визуализации параллелепипеда и тетраэдра.

На рисунках 2, 3 и 4 показано исполнение процедур S_vec(A,a,b),Prod_ vec(A,a,b) и Vec_Pr(M,x,e):

Рисунок 2 – Исполнение графической иллюстрации сложения векторов S_vec ([1,2,1],[1,1,1],[2,3,2]);

Рисунок 3 – Исполнение процедуры векторного произведения Prod_vec ([1,2,1], [1,1,-1],[2,3,2]);

Рисунок 4 – Исполнение графической иллюстрации параллельной и перпендикулярной составляющих вектора Vec_Pr([0,0,0],[10,10,10],[2,4,3])

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

1. Панкратьев, Е.В. Компьютерная алгебра: факторизация многочленов / Е.В. Панкратьев. – М.: [не указано], 1988. – 947 c.

2. Слисенко, А.О. Математические методы построения и анализа алгоритмов / А.О. Слисенко, С.В. Соловьев. – М.: [не указано], 1990. – 893 с.

3. Кострикин А.И. Введение в алгебру / А.И. Кострикин – М.: Наука, 1977 – 495 с.

4. Курош А.Г. Теория групп / А.Г. Курош – М.: Наука, 1967 – 648 с.

5. Холл М. Теория групп / М. Холл – М., Издательство иностранной литературы, 1962 – 468 с.