Дискретная математика. Полугруппы

[sick_alien]

всем здравствуйте

1-й курс Каунасского технологического университета (Литва), бакалавриат прикладной математики

ломаю зубы об дискретную математику.
делаю домашнее задание - программу генерирования полгрупп - т.е. ввожу элементы множества "a,b,c," и программа генерирует все возможные варианты квадратной матрицы-таблицы Келли, и проверяет ассоциативность и коммутативность (выбирает из них Абелевые группы)

скажите пожалуйста сколько всего полугрупп получается (чтобы я знал правильно программа работает или нет) из множетва из 2-х, 3-х, 4-х, 5-ти элементов
как посчитать количество всех возможнх вариантов таблиц Келли полугрупп?
в какой книге это можно посмотреть?

если кому нужно - могу исходный код программы сбросить как сделаю. мне не жалко. уже некоторая часть работает.

так например для множества [a,b,c] количество вариантов строк матриц - 3*3*3 = 27, количество всех возможгных матриц - 19683, из них полугрупп - 273. правильно ли это?

по идее я должен уловить закономерность и сделать генерацию таблиц Кэли полугрупп для большого числа элементов (типа [a,b,c,d,f,...])оптимизированно, поскольку если перебирать все варианты, то очень резко растёт время расчёта

помогите пожалуйста !!!
в какой литературе это можно посмотреть? а то так таблицы Кэли для полугрупп никто не рассматривает, по крайней мере я пока не нашёл
по идее я должен заметить закономерность в полученных полугруппах для малого числа элементов и спроецировать её для экономной генерации полугрупп для большого числа элементов (так как время счёта очень резко увеличивается уже для 5 элементов, если рассматривать все варианты)
и где это можно посмотреть или подскажите как это сделать (я постараюсь сам, но если это можно посмотреть в литературе, было бы здорово)


вот так выглядят промежуточная проверка

ну тут кусок выходного листинга для контроля

------------------
( c * a )= a || a * b = b [=[(a*b)*c]=]
( a * b )= b || b * c = b [=[a(*b*c)]=]

[=[a(*b*c)]=] == b == b [=[a(*b*c)]=]

Matrica Nr. 112
|eil/st| a | b | c |
--------------------------
| a || a | b | a |
--------------------------
| b || c | c | b |
--------------------------
| c || a | a | b |
--------------------------
--------------------------


------------------
( a * a )= a || a * c = a [=[(a*b)*c]=]
( a * c )= a || a * a = a [=[a(*b*c)]=]

[=[a(*b*c)]=] == a == a [=[a(*b*c)]=]

Matrica Nr. 112
|eil/st| a | b | c |
--------------------------
| a || a | b | a |
--------------------------
| b || c | c | b |
--------------------------
| c || a | a | c |
--------------------------
--------------------------


------------------
( b * b )= c || c * a = a [=[(a*b)*c]=]
( b * a )= c || c * b = a [=[a(*b*c)]=]

[=[a(*b*c)]=] == a == a [=[a(*b*c)]=]

Matrica Nr. 112
|eil/st| a | b | c |
--------------------------
| a || a | b | a |
--------------------------
| b || c | c | b |
--------------------------
| c || a | a | c |
--------------------------
--------------------------


------------------
( b * b )= c || c * c = c [=[(a*b)*c]=]
( b * c )= b || b * b = c [=[a(*b*c)]=]

[=[a(*b*c)]=] == c == c [=[a(*b*c)]=]

Matrica Nr. 112
|eil/st| a | b | c |
--------------------------
| a || a | b | a |
--------------------------
| b || c | c | b |
--------------------------
| c || a | a | c |
--------------------------
--------------------------


------------------
( c * a )= a || a * b = b [=[(a*b)*c]=]
( a * b )= b || b * c = b [=[a(*b*c)]=]

[=[a(*b*c)]=] == b == b [=[a(*b*c)]=]

Matrica Nr. 112
|eil/st| a | b | c |
--------------------------
| a || a | b | a |
--------------------------
| b || c | c | b |
--------------------------
| c || a | a | c |
--------------------------
--------------------------





помогите пожалуйста, сессия горит. крайний срок сдачи - среда

P.S. (вопрос модераторам - я правильно спрятал под кат? - если не так, то исправлю)

@темы: Теория групп, Дискретная математика, Комбинаторика

Comments

[d_a]

Посмотрите, может, тут есть:

www.libgen.in/book/index.php?md5=acc513af905cb4...

[d_a]

UPDATE

Вот, наверное, то, что вам нужно
www.liafa.univ-paris-diderot.fr/~jep/PDF/Rio.pd...

[sick_alien]

Спасибо огромное!!!!!!!!!!!

[d_a]

Вот тут, кстати, более свежий обзор литературы
arxiv.org/pdf/1502.07150.pdf

А тут чужие программы с документацией

www.liafa.jussieu.fr/~jep/semigroupes.html

www.gap-system.org/Packages/semigroups.html

[sick_alien]

Спасибо большое!

[Гость]

Пишет sick_alien:
Здравствуйте.

это опять я - студент 1-го курса прикладной математики Каунасского Технологического Университета
вдогонку вот к этому посту eek.diary.ru/p204578162.htm
программу я написал - можно скачать здесь - yadi.sk/d/uVAnBteKhNdzK cделал на FORTRAN90 в Compaq Visual Fortran 6
считает полугруппы из данного множества со 2 по 4 порядок включительно и выбирает из них Абелевы

остался последний вопрос - как выглядит таблица Кэли полугруппы с множеством из одного элемента - в английской вики как то странно написано - en.wikipedia.org/wiki/Trivial_semigroup

помогите пожалуйста.

[Гость]

sick_alien, а в чём затруднение? там же написана таблица для этого случая.

[sick_alien]

здравствуйте Гость

да, но она странно выглядит.

почему не написан просто один элемент?

и почему в ней две а выделены, а одна а оставлена просто? невыделенная а принадлежит этой таблице?

я потерялся, а в учебниках не написано (может и написано, но я не нашёл)

[All_ex]

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

[sick_alien]

ааа, дошло!

большое спасибо !

[All_ex]

welcome ...