ассоциативность

[bot]

Не впечатляет. Нужен пример плодотворного применения этого простого замечания.
Весьма скептически отношусь к нему как к средству ограничения перебора троек. К примеру, если $ab=a$ или $ab=b$, то замечание ничего не даёт. Ещё в полугруппах массово встречаются ситуации типа $ab=aa$ и они перекрываются с первыми, что запутывают картину далее не подлежащих проверке троек. Всё это настолько связано с индивидуальностью полугруппы, что строить на этом алгоритм проверки считаю делом бесперспективным.

Вас уже спрашивали - Вы не ответили, спрошу и я. В связи с чем возник этот вопрос? Конкретика может очень сильно помочь и даже совсем простенькая банальность может творить чудеса - знаю на собственном опыте. Тест на ассоциативность всегда считался трудоёмким и использовался для демонстрации возможностей создаваемых ЭВМ. После того, как SWAG computes 126 distinct (то есть не изоморфных и неантизоморфных) semigroups of order 4, американцы надолго застряли, а мне позарез были нужны 5-элементные. Вот я и взялся - какая самонадеянность! Если ещё добавить мои более чем скромные возможности (имел доступ к ЭВМ в режиме разделения времени с самым низким студенческим приоритетом), то нахальству моему вообще предела не было.
Перебирать группоиды и подвергать их тесту на ассоциативность (а потом ещё и на изоморфизм) было абсолютно бессмысленно. Зайти с другой стороны помогла банальность - представление полугруппы правыми сдвигами - наподобие как в группах, только здесь нюансик есть: единичку сначала надо внешним образом добавить. Вот здесь как раз и заработал принцип: определил произведение очередной пары - смотри следствия, для одних пар проиведение само опрелилось, для других сузились возможности перебора, то есть в дереве перебора целиком ветки рубятся. Ну и ещё удачно соединил эту банальность с другой - рубил изоморфные до того как, а не после того.

[zkutch]

bot в сообщении #423923 писал(а):

Вас уже спрашивали - Вы не ответили, спрошу и я. В связи с чем возник этот вопрос?

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

bot в сообщении #423923 писал(а):

Не впечатляет. Нужен пример плодотворного применения этого простого замечания.
Весьма скептически отношусь к нему как к средству ограничения перебора троек.

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

[bot]

zkutch в сообщении #424049 писал(а):

Проверка всех троек не нужна.

Как правило, отсечь много ненужных для проверки троек не удастаться - если повезёт, то примерно треть, а взамен потребуется подстраивать процесс перебора троек под данный индивидуализм, что существенно усложнит алгоритм перебора. А может и не повести - среди полугрупп полно таких, у которрых двупорождённые полугруппы маленькие и даже тех, у которые все двупорождённые двухэлементны, на них вообще выигрыша не будет, а [quote="zkutch в будут только потери из-за пустой возни с организацией перебора.

(Оффтоп)

сообщении #424049"](((сериал дал плоды - а какой, если не секрет?)))[/quote]оффтоп про таймаут на сериал я стёр при редактирования. Ну смотрю в пол-глаза всякую фигню ... Жене ведь одной скучно смотреть, перекинуться словом по ходу надо, вот и играю в игру: угадай чего надо - детям цветы, женщинам мороженое или наоборот.

[zkutch]

Ну спасибо всем участникам. И материал есть новый для чтения и обмен мнениями помог. Если у кого будут по данному вопросу новости, буду рад услышать.

[bot]

zkutch в сообщении #424049 писал(а):

вопрос возникает при создании определенных индексов к базам данных

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

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

2) Вариант похожий на тот, с которым имел дело. Требуется построить полугруппы заданного порядка, которым по известным не мне правилам соответствуют какие-то там базы. Порядок не слишком велик? Полагаю, вряд ли - скорее всего зашкаливает за возможности даже суперкомпьютеров. Полугруппы возникают всякие или нет? Насколько существенен для Вашего соответствия изоморфизм и антиизоморфизм?

3) Не угадал.

[zkutch]

bot

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

[bot]

zkutch в сообщении #424374 писал(а):

Мне, как математику, проявился и был интересен вопрос, который и задал.

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

bot в сообщении #423428 писал(а):

Необходимо и достаточно, чтобы выполнялось тождество $x(yz)=(xy)z$.

Если хотите получить другой ответ, займитесь уточнением вопроса.

zkutch в сообщении #424374 писал(а):

Похоже на лапшу из ваших первых двух догадок

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

[zkutch]

Ну у вас уже есть ответы на ваши соображения в "Leox в сообщении #423702"

вы очень настойчиво меняете тему и странно меняете предложения:

с одной стороны

bot в сообщении #423651 писал(а):

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

а с другой

bot в сообщении #424126 писал(а):

Как правило, отсечь много ненужных для проверки троек не удастаться - если повезёт, то примерно треть

[bot]

Вы отличаете массовую проблему от индивидуальной?

Рассмотрим совсем простенький пример. Пусть Вам попался группоид 2011-го порядка с умножением:
$x\cdot y= c$ во всех случаях, кроме $a\cdot b=b$.
Здесь единственная неассоциативная тройка: $a(ab)=b\ne (aa)b=c$.
Как Вы собираетесь построить алгоритм перебора, чтобы он сработал на этом группоиде столь же эффективно, сколь и на других? Явно требуются какие-то условия, описывающие класс нужных Вам группоидов, без них он слишком широк.

zkutch в сообщении #424546 писал(а):

Leox в сообщении #423702

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