НГУ

Форумы НГУ
Текущее время: Вс апр 21, 2019 9:13 pm

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 9 ] 
Автор Сообщение
СообщениеДобавлено: Вс сен 02, 2007 1:32 am 
Не в сети
Редкий гость

Зарегистрирован: Пт авг 31, 2007 1:15 am
Сообщения: 4
Откуда: Евгений
Доброго времени суток.

Из интереса решил воспроизвести алгоритмы функций, для работы с группами, пакета Maple 9.5, реализовав их на языке Delphi.
С группами перестановок получилось, смотрите на моей страничке.
Вот список функций:
-----------------------------------------------------------
mul- произведение нескольких подстановок.
Кроме операции произведения можно производить возведение в положительную и отрицательные степени.
gr - вычисление группы порождённой заданными подстановками.
find - пойск подстановоки в группе или множестве.
findord - пойск подстановок данного порядка в группе или множестве.
centralizer - вычисление централизатора подмножества группы.
comutant - вычисление коммутанта группы.
normalizer - вычисление нормализатора подмножества
ismulclosed - определяет замкнутость множества
isabelian - определяет является ли группа абелевой.
issubset - определяет содержит ли множество1 множество2.
issubgroup - определяет является ли группа2 подгруппой группы1, и если да то нормальной или нет.
intersection - пересечение множества1 и множества2.
rightclass - выдает представителей правых смежных классов группы по подгруппе.
generators - выдает какие-нибудь образующие группы.
conjugclass - выдает представителей классов сопряженных элементов.
conjugorbit - выдает все элементы сопряженные данному.
sylow - вычисление силовской P подгруппы.
-----------------------------------------------------------
Буду рад услышать ваши замечания и вопросы по программе.

Но у меня остались нерешенными следующие вопросы:

1. Как лучше вычислять силовские подгруппы?

И самые сложные вопросы:

2. Каким образом происходит представление группы, заданной образующими и определяющими соотношениями, в виде группы перестановок, или таблицей Кэли?

3. И обратная задача:
Пусть группа задана таблицей Кэли, найти какие-нибудь образующие этой группы не составляет особой сложности (в моей программе функция generators) , но как определить наименьшую систему соотношений связываюшюю их?

Я надеюсь, что мне кто-нибудь ответит.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн сен 03, 2007 9:11 am 
Не в сети
Постоянный посетитель

Зарегистрирован: Вт дек 14, 2004 4:37 pm
Сообщения: 177
Откуда: Вдовин Евгений Петрович
Я не совсем понимаю, зачем весь этот огород городить? Есть 2 очень хороших программы для работы с группами GAP и MAGMA, причём GAP полностью бесплатный и с группами подстановок работает даже лучше, чем MAGMA, быстро и эффективно. Рекомендую сначала ознакомиться с документацией к GAP, офф. сайт: www.gap-system.org


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн сен 03, 2007 9:32 am 
Не в сети
Редкий гость

Зарегистрирован: Пт авг 31, 2007 1:15 am
Сообщения: 4
Откуда: Евгений
veprus писал(а):
Я не совсем понимаю, зачем весь этот огород городить? Есть 2 очень хороших программы для работы с группами GAP и MAGMA, причём GAP полностью бесплатный и с группами подстановок работает даже лучше, чем MAGMA, быстро и эффективно. Рекомендую сначала ознакомиться с документацией к GAP, офф. сайт: www.gap-system.org

Ну вот, Вы меня огорчили. :( Я же не претендую на то, чтобы эта программа заменяла общеизвестные математические пакеты. Я делю её для того чтобы самому понять и разобраться в алгоритмах, как говорится "испытать всё на собственной шкуре".
Я не совсем с Вами согласен. Если так рассуждать, тогда вообще не нужно учиться считать - есть калькулятор, изучать математику - есть доступные мат.пакеты, и т.д.
А что каксается документации к GAP, я смотрел, но мне это не очень помогло. Я надеялся на совет или ссылку, по вопросу представления групп порожденных образующими.
Все равно, благодарю за внимание.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн сен 03, 2007 10:46 am 
Не в сети
Постоянный посетитель

Зарегистрирован: Вт дек 14, 2004 4:37 pm
Сообщения: 177
Откуда: Вдовин Евгений Петрович
Цитата:
не нужно учиться считать - есть калькулятор

и в этом есть доля правды

Цитата:
изучать математику - есть доступные мат.пакеты

а вот в этом правды нет совсем.

Цитата:
А что каксается документации к GAP, я смотрел, но мне это не очень помогло.

И очень жаль. Её писали люди намного более компетентные в данном вопросе, чем я сам. Я же не предлагаю Вам ничего не делать - я предлагаю ознакомиться с опытом тех, кто уже что-то делал и при этом достиг хорошего результата.

О строении силовских подгрупп написано в книге Каргаполова, Мерзлякова, "Основы теории групп" (в 4-м издании на 107 странице), и вообще это строение указывается в любом учебнике по теории конечных групп.

Задача перевода группы, заданной каким-то способом в другой способ (например, из порождающих и определяющих соотношений в группу подстановок) вообще говоря не имеет алгоритмического решения. Например, для построения точного подстановочного представления единственный универсальный способ - это найти подгруппу, не содержащую неединичных нормальных подгрупп всей группы и построить подстановочное представление по смежным классам этой подгруппы. Всё это относится и к обратной задаче - поиска порождающих и соотношений. Хорошо известно, что задача о нахождении минимального количества порождающих и/или минимального количества определяющих соотношений в общем виде решения не имеет.

И ещё, по поводу термина подстановка и перестановка. Пока мы говорим об элементах группы, оба этих термина равноправны. Но очень часто приходится рассматривать подстановочные (соотв. перестановочные) представления. Если представление одно - это ещё терпимо, хотя уже режет слух, а вот фраза "рассмотрим все эквивалентные перестановочные представления" читается уже совсем неправильно. В английском языке таких сложностей не возникает, а вот в русском - очень даже возникают. Поэтому разумнее использовать термин "подстановка". Кстати, доводов в пользу термина "перестановка", кроме весьма сомнительного утверждения, что это точный перевод слова "permutation", я не знаю.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн сен 03, 2007 10:49 am 
Не в сети
Постоянный посетитель

Зарегистрирован: Вт дек 14, 2004 4:37 pm
Сообщения: 177
Откуда: Вдовин Евгений Петрович
Да, если Вам хочется заняться разработкой алгоритмов для решения групповых задач, то я могу Вам подкинут такие задачи. Для них алгоритмы, теоретически, понятны, но вот практическая их реализация ещё не началась.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн сен 03, 2007 12:01 pm 
Не в сети
Редкий гость

Зарегистрирован: Пт авг 31, 2007 1:15 am
Сообщения: 4
Откуда: Евгений
veprus писал(а):
О строении силовских подгрупп написано в книге Каргаполова, Мерзлякова, "Основы теории групп" (в 4-м издании на 107 странице), и вообще это строение указывается в любом учебнике по теории конечных групп.
Со строением силовских подгрупп я знаком, даже построил алгоритм их вычисления и реализовал его в моей программке, но еще посмотрю эти книги(спасибо). Просто я хочу найти более оптимальный алгоритм. Кстати хотелось бы узнать ваше мнение о прграммке, не судите строго я не программист (учусь на матфаке).

veprus писал(а):

Задача перевода группы, заданной каким-то способом в другой способ (например, из порождающих и определяющих соотношений в группу подстановок) вообще говоря не имеет алгоритмического решения. Например, для построения точного подстановочного представления единственный универсальный способ - это найти подгруппу, не содержащую неединичных нормальных подгрупп всей группы и построить подстановочное представление по смежным классам этой подгруппы. Всё это относится и к обратной задаче - поиска порождающих и соотношений. Хорошо известно, что задача о нахождении минимального количества порождающих и/или минимального количества определяющих соотношений в общем виде решения не имеет.
Вот этот ответ мне уже нравится больше!
То есть это подстановочное представление по смежным классам будет изоморфно самой группе? Почему? Или я ошибаюсь?

И вообще какой принцип нахождения этого представления?
Допустим даны образующие(буквы алфавита): {x1,x2,...,xn} и определяющие соотношения(слова): {u1,u2,...,uk}, как найти подгруппу, не содержащую неединичных нормальных подгрупп всей группы и построить подстановочное представление по смежным классам этой подгруппы???

Да, подкидывайте задачки!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн сен 03, 2007 12:34 pm 
Не в сети
Постоянный посетитель

Зарегистрирован: Вт дек 14, 2004 4:37 pm
Сообщения: 177
Откуда: Вдовин Евгений Петрович
Цитата:
То есть это подстановочное представление по смежным классам будет изоморфно самой группе? Почему? Или я ошибаюсь?


Если H - подгруппа группы G, то можно задать действие группы G на правых смежных классах по H следующим правилом:

x:Hy -> H(yx).

Данное представление задаёт гомоморфизм из G в симметрическую группу множества правых смежных классов. Его ядро - максимальная нормальная подгруппа группы G, содержащаяся в H. В частности, данный гомоморфизм является изоморфизмом тогда и только тогда, когда H не содержит неединичных нормальных подгрупп группы G.

Цитата:
Кстати хотелось бы узнать ваше мнение о прграммке, не судите строго я не программист (учусь на матфаке).


Я тоже не програмист. И паскаль изучал более 10-и лет назад, после чего никогда им не пользовался. Если будет время, я программу могу посмотреть, но лучше будет, если Вы где-нибудь изложите алгоритм без привязки к конкретному языку программирвания.

Цитата:
И вообще какой принцип нахождения этого представления?

см. выше

Цитата:
как найти подгруппу, не содержащую неединичных нормальных подгрупп всей группы

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

Цитата:
Да, подкидывайте задачки!

Рассмотрим 2 матрицы A и B. Вопрос о том, сопряжены ли они имеет алгоритмическое решение - сопряжены тогда и только тогда, когда эквивалентны их лямбда-матрицы (по этому поводу неплохо написано в учебника Мальцева по линейной алгебре). Задача заключается в том, чтобы найти эту самую сопрягающую матрицу (при этом базовое поле произвольно). Данная задача, по крайней мере в GAP-е, решается без учёта специфики матриц, и потому неэффективно. Более эффективный метод решения заключается в следующем соображении:

множество сопрягающих матриц есть пересечения множества всех невырожденных матриц и множества решений системы линейных уравнений: XA=BX. Процесс решения системы линейных уравнений хорошо известен и имеет сложность не более, чем О(n^3), где n - число уравнений (в нашем случае, если k - размер матрицы, то число уравнений k^2). Возможно, из-за специфики системы можно предложить ещё более короткое решение. Поскольку система однородная, множество её решений образует подалгебру в алгебре матриц. Так что достаточно найти только её базис. Таким образом, первая часть задачи - предложить алгоритм, находящий базис. И вторая часть задачи, но она уже будет зависеть от решения первой - предложить алгоритм нахождения хотя бы одного элемента из пересечения.

Данная задача имеет массу важных обобщений. В частности, было бы интересно решить её для произвольных двух конечных множеств матриц. Было бы также полезно реализовать алгоритм проверки сопряжённости матриц.

В качестве пожелания - все алгоритмы лучше писать на C или его клоне, тогда их легче будет "встраивать" в существующие программы и легче переводить на другие платформы и операционные системы (в отличие от Паскаля).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн сен 03, 2007 1:39 pm 
Не в сети
Редкий гость

Зарегистрирован: Пт авг 31, 2007 1:15 am
Сообщения: 4
Откуда: Евгений
veprus писал(а):
Я тоже не програмист. И паскаль изучал более 10-и лет назад, после чего никогда им не пользовался. Если будет время, я программу могу посмотреть, но лучше будет, если Вы где-нибудь изложите алгоритм без привязки к конкретному языку программирвания.

Я имел ввиду посмотреть программу в работе, а не ее исходный текст (как говорится, чужой код потемки).


veprus писал(а):
Если H - подгруппа группы G, то можно задать действие группы G на правых смежных классах по H следующим правилом:

x:Hy -> H(yx).

Данное представление задаёт гомоморфизм из G в симметрическую группу множества правых смежных классов. Его ядро - максимальная нормальная подгруппа группы G, содержащаяся в H. В частности, данный гомоморфизм является изоморфизмом тогда и только тогда, когда H не содержит неединичных нормальных подгрупп группы G.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн сен 03, 2007 7:50 pm 
Не в сети
Постоянный посетитель

Зарегистрирован: Вт дек 14, 2004 4:37 pm
Сообщения: 177
Откуда: Вдовин Евгений Петрович
Цитата:
Я так и немогу понять, как от "слов" из "алфавита" перейти к этому представлению? Возьмем единичную подгруппу, тогда представителями смежных классов будут всё элементы группы, а мы их не знаем, даже не можем узнать сколько их и равны ли между собой какие-нибудь два "слова".
Может объясните подробнее в терминах "алфавита" и "слов", что нужно делать???

Существуют более-менее стандартные алгоритмы перечисления элементов в группе, заданной порождающими и соотношениями. Никогда об этом не задумывался и ссылок не помню. Точно все они работают лишь с конечными группами, так что если система порождающих и соотношений даёт бесконечную группу - алгоритм зависнет. В любом случае задача это долгая и её решение требует очень много времени.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB