Российские распределенные вычисления на платформе BOINC
Форум участников распределённых вычислений.

Добро пожаловать, Гость! Чтобы использовать все возможности Вход или Регистрация.

Уведомление

Icon
Error

33 Страницы«<313233
Опции
К последнему сообщению К первому непрочитанному
Offline citerra  
#641 Оставлено : 13 июля 2018 г. 9:36:45(UTC)
citerra


Статус: Старожил

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch!Донор: За финансовую помощь сайту

Группы: Editors, Member, Russia Team Group, Moderators
Зарегистрирован: 02.10.2007(UTC)
Сообщений: 2,219

Сказал(а) «Спасибо»: 454 раз
Поблагодарили: 332 раз в 241 постах
Решил посмотреть, как идут дела в параллельных исследований.
Взял результаты за последний месяц-полтора.
Только две тройки, найденные Demis, найдены на полмесяца раньше, чем они были найдены в Герасиме.
Все остальные сразу повторные. Вот такие "уникальные" кф.
Интересно сравнить находки
Двойки: "не подсчитываются" против 13 873
Тройки: 57 против 85
Четверки: 275 против 338
Пятерки: "пусто" против двух
Шестерки: 7 против 10
Т.е в альтернативных поиске находится то, что уже найдено ранее.
Но это не страшно. Можно взять и переписать историю, записать находки на себя, что и
делает "ученый проекта" Макарова на форуме ODLK@Home (подробнее), предварительно закрыв большинство веток форума.
thanks 1 пользователь поблагодарил citerra за этот пост.
evatutin оставлено 13.07.2018(UTC)
Offline evatutin  
#642 Оставлено : 13 июля 2018 г. 12:10:18(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,566
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 1003 раз
Поблагодарили: 1734 раз в 842 постах
citerra
А нас — рать (с), переживем 199

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline citerra  
#643 Оставлено : 13 июля 2018 г. 12:22:39(UTC)
citerra


Статус: Старожил

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch!Донор: За финансовую помощь сайту

Группы: Editors, Member, Russia Team Group, Moderators
Зарегистрирован: 02.10.2007(UTC)
Сообщений: 2,219

Сказал(а) «Спасибо»: 454 раз
Поблагодарили: 332 раз в 241 постах
evatutin
Печально, что Progger совсем запустил сайт.
Нет никакого развития сайта, а форум превратился в графоманский гадюшник.
Offline evatutin  
#644 Оставлено : 16 июля 2018 г. 16:14:20(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,566
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 1003 раз
Поблагодарили: 1734 раз в 842 постах
Для формул, соответствующих обобщенным симметриями, выше приводилось условие, что f(f(x)) = e. Оно же по сути обозначает, что если ячейке [x,y] соответствует ячейка [x',y'], то и наоборот соответствие справедливо. Другими словами, f([x,y]) = [x',y'] и f([x',y']) = [x,y]. Так вот оказывается, что если баловаться с коэффициентами обобщенных симметрий, то некоторым их наборам данное свойство нехарактерно, при этом от них строятся вполне себе корректные ЛК. Тут соответствие получается как бы одностороннее, т.е. если L[x,y]=a, то L[x',y']=b для всех [x,y] одной половины ЛК (пока так, хотя надо бы формализовать). Примеры привожу ниже, интересен их анализ с точки зрения whitefox199

Код:
0 1 2 3 4 5 6 7 8 9
2 3 0 1 6 7 8 9 4 5
4 5 6 7 8 9 2 1 0 3
8 7 4 9 2 3 0 5 6 1
6 9 8 5 0 1 4 3 2 7
9 0 1 2 3 4 5 6 7 8
5 2 3 0 1 6 7 8 9 4
3 4 5 6 7 8 9 2 1 0
1 8 7 4 9 2 3 0 5 6
7 6 9 8 5 0 1 4 3 2

0 1 2 3 4 5 6 7 8 9
2 3 0 1 6 7 8 9 4 5
4 5 6 7 8 9 2 3 0 1
8 7 4 9 2 1 0 5 6 3
6 9 8 5 0 3 4 1 2 7
9 0 1 2 3 4 5 6 7 8
5 2 3 0 1 6 7 8 9 4
1 4 5 6 7 8 9 2 3 0
3 8 7 4 9 2 1 0 5 6
7 6 9 8 5 0 3 4 1 2

0 1 2 3 4 5 6 7 8 9
2 3 0 1 6 7 8 9 4 5
4 5 6 7 8 9 2 3 0 1
8 9 4 5 2 3 0 1 6 7
6 7 8 9 0 1 4 5 2 3
9 0 1 2 3 4 5 6 7 8
5 2 3 0 1 6 7 8 9 4
1 4 5 6 7 8 9 2 3 0
7 8 9 4 5 2 3 0 1 6
3 6 7 8 9 0 1 4 5 2

0 1 2 3 4 5 6 7 8 9
2 3 0 1 6 7 8 9 4 5
4 5 6 9 8 1 0 3 2 7
8 7 4 5 0 9 2 1 6 3
6 9 8 7 2 3 4 5 0 1
9 0 1 2 3 4 5 6 7 8
5 2 3 0 1 6 7 8 9 4
7 4 5 6 9 8 1 0 3 2
3 8 7 4 5 0 9 2 1 6
1 6 9 8 7 2 3 4 5 0

0 1 2 3 4 5 6 7 8 9
2 3 0 1 6 7 8 9 4 5
4 5 6 9 8 1 0 3 2 7
8 9 4 7 0 3 2 5 6 1
6 7 8 5 2 9 4 1 0 3
9 0 1 2 3 4 5 6 7 8
5 2 3 0 1 6 7 8 9 4
7 4 5 6 9 8 1 0 3 2
1 8 9 4 7 0 3 2 5 6
3 6 7 8 5 2 9 4 1 0


[upd]
Приведенные квадраты получаются без трансверсалей, соответственно канонизировать тут нечего, ОЛК и ОДЛК у них нет. Интересная особенность...

Отредактировано пользователем 16 июля 2018 г. 16:49:57(UTC)  | Причина: Не указана

Пользователь evatutin прикрепил следующие файлы:
1.png

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline whitefox  
#645 Оставлено : 16 июля 2018 г. 16:28:38(UTC)
whitefox


Статус: Частенько заглядывает

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 183

Сказал(а) «Спасибо»: 53 раз
Поблагодарили: 154 раз в 93 постах
На множестве симметрий ЛК10 существует отношение подчинённости. Например симметрия с кодом (31,41,42) подчинена симметрии с кодом (1,31,31) в том смысле, что всякий ЛК с симметрией (31,41,42) также обладает и симметрией (1,31,31). Все симметрии с нетривиальной парострофией (их коды имеют один или два плюса) в совокупности подчинены симметриям, соответствующим автотопиям, (их коды плюсов не имеют). Характер такой подчинённости выяснен ещё не полностью, но уже можно поставить задачу перечисления всех симметрий соответствующих автотопиям.

Теоретически, изотопии могут иметь до 13244 различных кодов симметрии. Отбросим из них те, что заведомо не могут быть кодами автотопий. Сделаем это в три этапа.

На первом этапе проверим выполнение следующего необходимого условия:
если изотопия является автотопией, то каждому циклу позиций C длины d_c сопоставлен цикл значений V длины d_v такой, что:
d_v делит d_c;
d_v не делит d_a * k, для 1 <= k < (d_c / d_a);
d_v не делит d_b * k, для 1 <= k < (d_c / d_b).
Здесь d_a длина какого-то цикла A перестановки строк, а d_b длина какого-то цикла B перестановки столбцов, и цикл позиций C образован циклами A и B, то есть d_c = lcm(d_a, d_b).

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



Здесь нули обозначают пустое множество.

Например, рассмотрим изотопию с кодом (19,32,33), соответствующие циклические структуры суть {1,1,2,6}, {2,2,2,4}, {2,2,3,3}, а их типы — {1,2,6}, {2,4}, {2,3}. Для симметрии не важно какая именно перестановка, из состава изотопии, является перестановкой значений, но это важно для применения критерия. И так как типы циклических структур все разные, то критерий применим трижды, и отвергнем изотопию если она не прошла проверку хотя бы один раз.

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

Возьмём в нашем примере в качестве значений циклическую структуру с типом {1,2,6}, тогда типы {2,3} и {2,4} определяют возможные типы позиций и соответствующие им множества допустимых значений:

Код:
(2,2) -> {1,2}
(2,3) -> {6}
(2,4) -> {4}
(3,4) -> 0

Пересечение этих множеств с множеством {1,2,6} пусто в третьем и четвёртом случаях. То есть изотопия с кодом (19,32,33) отвергается, но для полноты картины приведу и два других возможных выбора множества значений.

Множество значений — {2,4}
Циклы позиций определяются из — {1,2,6} и {2,3}
Типы циклов и соответствующие множества значений:
Код:
(1,2) -> {2}
(1,3) -> {3}
(2,2) -> {1,2}
(2,3) -> {6}
(2,6) -> {3,6}
(3,6) -> {2,6}

Пересечения с множеством значений: {2}, 0, {2}, 0, 0, {2}.
Код симметрии допускается? — Нет.

Множество значений — {2,3}
Циклы позиций определяются из — {1,2,6} и {2,4}
Типы циклов и соответствующие множества допустимы значений:
Код:
(1,2) -> {2}
(1,4) -> {4}
(2,2) -> {1,2}
(2,4) -> {4}
(2,6) -> {3,6}
(4,6) -> 0

Пересечения с множеством значений: {2}, 0, {2}, 0, {3}, 0.
Код симметрии допускается? — Нет.

Всего через этот критерий проходят коды изотопий соответствующие следующим 39 тройкам типов циклических структур:



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

Через эту проверку проходят следующие 67 кодов симметрий:



Третий этап покажу на примере изотопии с кодом (11,33,33). Соответствующие циклические структуры суть {1,1,1,1,6}, {2,2,3,3}, {2,2,3,3}. Снова проверку выполняем для каждого возможного выбора множества значений. Код симметрии отвергается если он не прошёл проверку хотя бы раз.

Построим следующую таблицу для выбора мультимножества длин циклов значений {2,2,3,3}:

Код:
  \  |  2|  2|  3|  3| sum
--------------------------
(1,2)|  2|  2|  0|  0|  16
(1,3)|  0|  0|  3|  3|  24
(2,6)|  0|  0|  6|  6|  24
(3,6)|  6|  6|  0|  0|  36
--------------------------
total| 20| 20| 30| 30| 100


Строки таблицы помечены типами циклов позиций. Каждому типу значений в таблице отведена колонка помеченная длиной соответствующего цикла значений. В клетках таблицы стоит длина соответствующего цикла позиций или ноль если циклу позиций данного типа не может быть сопоставлен цикл значений с соответствующей длиной. В колонке sum стоит число ячеек ЛК занимаемых всеми циклами позиций соответствующего типа. В строке total стоит число ячеек квази-ЛК имеющих значения соответствующего типа (= заголовок колонки умноженный на порядок ЛК). Очевидно, что сумма чисел из колонки sum равна сумме чисел из строки total и равна числу ячеек ЛК.

Сопоставим этой таблице следующую систему уравнений:

Код:
2*X11 + 2*X12 = 16
3*X23 + 3*X24 = 24
6*X33 + 6*X34 = 24
6*X41 + 6*X42 = 36
2*X11 + 6*X41 = 20
2*X12 + 6*X42 = 20
3*X23 + 6*X33 = 30
3*X24 + 6*X34 = 30


Очевидно, что если рассматриваемая изотопия является автотопией, то данная система уравнений имеет решение в целых неотрицательных числах. Это и есть необходимое условие проверяемое на третьем этапе.

Для нашего примера система уравнений вовсе не имеет решений, поэтому изотопия с кодом (11,33,33) отвергается, но для полноты картины приведу соответствующую таблицу для второго возможного выбора мультимножества значений {1,1,1,1,6}:

Код:
  \  |  1|  1|  1|  1|  6| sum
------------------------------
(2,2)|  2|  2|  2|  2|  0|  16
(2,3)|  0|  0|  0|  0|  6|  48
(3,3)|  3|  3|  3|  3|  0|  36
------------------------------
total| 10| 10| 10| 10| 60| 100


Код:
2*X11 + 2*X12 + 2*X13 + 2*X14 = 16
6*X25 = 48
3*X31 + 3*X32 + 3*X33 + 3*X34 = 36
2*X11 + 3*X31 = 10
2*X12 + 3*X32 = 10
2*X13 + 3*X33 = 10
2*X14 + 3*X34 = 10
6*X25 = 60

Эта система тоже не имеет решений.

Всего через третий этап проходят следующие 46 кодов симметрии:



Осталось ещё проверить существование ЛК с соответствующими автотопиями.
Offline whitefox  
#646 Оставлено : 17 июля 2018 г. 15:58:07(UTC)
whitefox


Статус: Частенько заглядывает

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 183

Сказал(а) «Спасибо»: 53 раз
Поблагодарили: 154 раз в 93 постах
Вчера был представлен список 46 вероятных кодов симметрии, и поставлена задача проверки какие из этих кодов действительно являются симметриями. Для начала, нужно как можно больше подтверждённых кодов симметрии из этого списка исключить, а затем запустить тотальную проверку для оставшихся.

Представляю программу avtoizor_2.00, могущую помочь в выполнении первой части задачи. Фактически, это avtoizor с изменённым форматом вывода. Автоморфизмы теперь не выводятся, а коды симметрий группируются и выводится только один из них с указанием его кратности. Сами коды тоже немного изменены, а именно: знаки '+' и '++' заменены кодами соответствующей парастрофии (с опущенным символом '*'wink. Например, (21,21,21)T, (21,21,21)CT. Соответствие с прежними кодами следующее: одной букве соответствует знак '+', а двум — знак '++'.

Для примера в архив включён файл input.txt c ЛК

Код:
0 1 2 3 4 5 6 7 8 9
1 2 3 4 0 6 7 8 9 5
2 3 4 0 1 7 8 9 5 6
3 4 0 1 2 8 9 5 6 7
4 0 1 2 3 9 5 6 7 8
5 9 8 7 6 0 4 3 2 1
6 5 9 8 7 1 0 4 3 2
7 6 5 9 8 2 1 0 4 3
8 7 6 5 9 3 2 1 0 4
9 8 7 6 5 4 3 2 1 0


Это блочный ЛК вида 10x5 из семейства HCNETKVQ. Он имеет 125 интеркалятов и 12000 автоморфизмов, но только 120 различных симметрий. Наибольшая кратность у симметрии (21,36,36) — 750, а у симметрии (1,31,31) — 15, другими словами, этот ЛК является 15-квази-симметричным. smile

Из 120 симметрий 14 являются автотопиями, их коды:

Код:
(1,1,1)
(1,31,31)
(1,41,41)
(7,7,7)
(7,41,41)
(7,42,42)
(16,16,16)
(16,31,31)
(16,42,42)
(21,21,21)
(21,36,36)
(31,41,42)
(41,41,41)
(41,42,42)


Осталось подтвердить 32 кода.
Вложение(я):
avtoizor_2.00.zip (27kb) загружен 2 раз(а).
Offline whitefox  
#647 Оставлено : 17 июля 2018 г. 16:08:13(UTC)
whitefox


Статус: Частенько заглядывает

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 183

Сказал(а) «Спасибо»: 53 раз
Поблагодарили: 154 раз в 93 постах
Спрашивается: как ЛК, обладающий какой-то конкретной симметрией, привести к виду в котором данная симметрия станет очевидной.

Покажу на примере ЛК:

Код:
0 1 2 3 4 5 6 7 8 9
1 0 9 8 7 6 5 4 3 2
2 6 0 7 8 3 1 5 9 4
3 5 7 4 1 0 2 9 6 8
4 8 3 1 0 9 7 2 5 6
5 3 8 6 9 2 0 1 4 7
6 2 4 9 5 1 3 8 7 0
7 9 5 0 3 4 8 6 2 1
8 4 6 5 2 7 9 0 1 3
9 7 1 2 6 8 4 3 0 5


Для него avtoizor выдаёт:

Код:
** 0123456789 0123456789 0123456789 -> (1,1,1)
** 1065832947 1098765432 0123456789 -> (1,31,31)


Симметрию (1,31,31) легче всего увидеть в вертикально симметричном ЛК с нормализованной первой строкой, который должен иметь автоморфизм:

Код:
** 0123456789 9876543210 9876543210

Запишем эти перестановки в циклическом виде:

Код:
0123456789 = (0)(1)(2)(3)(4)(5)(6)(7)(8)(9)
9876543210 = (09)(18)(27)(36)(45)
9876543210 = (09)(18)(27)(36)(45)


А для нашего ЛК получим:

Код:
1065832947 = (01)(26)(35)(48)(79)
1098765432 = (01)(29)(38)(47)(56)
0123456789 = (0)(1)(2)(3)(4)(5)(6)(7)(8)(9)


Нужно найти изоморфизм преобразующий наш ЛК к требуемому виду. Сначала определим нужную парастрофию, очевидно, что это должна быть инверсия столбцов, меняющая местами первую и третью перестановки автоморфизма, причём получим первый элемент автоморфизма уже в нужном виде — 0123456789 и дальнейшие преобразования с ним не нужны, поэтому в качестве первого элемента изоморфизма возьмём тождественну перестановку.

Чтобы найти перестановку переводящую 1098765432 в 9876543210, запишем эти перестановки в циклическом представлении, первую под второй и удалим скобки, получим:

Код:
0918273645
0129384756


Это и есть нужная перестановка в двустрочной записи, после упорядочения её столбцов, вторая строка станет равной 0234567891, это и будет второй элемент изоморфизма.

Применим к нашему ЛК изоморфизм:

Код:
C* 0123456789 0234567891 0123456789


Для чего воспользуемся программой izomorfer, получим ЛК:

Код:
0 2 7 4 3 5 8 9 6 1
1 9 4 3 6 2 5 8 7 0
2 0 9 8 5 3 4 7 1 6
3 4 0 7 2 6 9 1 8 5
4 6 3 0 7 9 1 5 2 8
5 7 8 6 0 1 2 4 9 3
6 8 5 9 1 0 7 3 4 2
7 3 2 1 8 4 0 6 5 9
8 5 1 2 9 7 6 0 3 4
9 1 6 5 4 8 3 2 0 7


Осталось только его нормализовать, для чего обратим перестановку представленную первой строкой, получим 0914358267, что и будет третим элементом нужного нам изоморфизма:

Код:
C* 0123456789 0234567891 0914358267


Применим его к исходному ЛК, получим ЛК требуемого вида:

Код:
0 1 2 3 4 5 6 7 8 9
9 7 3 4 8 1 5 6 2 0
1 0 7 6 5 4 3 2 9 8
4 3 0 2 1 8 7 9 6 5
3 8 4 0 2 7 9 5 1 6
5 2 6 8 0 9 1 3 7 4
8 6 5 7 9 0 2 4 3 1
2 4 1 9 6 3 0 8 5 7
6 5 9 1 7 2 8 0 4 3
7 9 8 5 3 6 4 1 0 2


Для него avtoizor выдаёт:

Код:
** 0123456789 0123456789 0123456789 -> (1,1,1)
** 0123456789 9876543210 9876543210 -> (1,31,31)
Offline whitefox  
#648 Оставлено : 17 июля 2018 г. 16:14:32(UTC)
whitefox


Статус: Частенько заглядывает

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 183

Сказал(а) «Спасибо»: 53 раз
Поблагодарили: 154 раз в 93 постах
Автор: evatutin Перейти к цитате
whitefox
А вы можете посмотреть примеры ЛК в файле, обладающих еще группой обобщенных симметрий, на предмет того, будут ли они давать по вашей классификации коды, отличные от (x,31,31)


Все квадраты кроме одного имеют только по одной симметрии кроме тривиальной. И все эти симметрии имеют код (x,31,31), а именно: (1,31,31), (2,31,31), (4,31,31), (16,31,31). Только один квадрат имеет три нетривиальные симметрии и одна из них имеет код (16,16,16). Подозреваю, что эта симметрия подчинена какой-то из (x,31,31)-симметрий подобно (31,41,42).

Лог out_avtoizor.txt с выводом пакетного файла mass_avtoizor.bat в приложенном архиве.

Файл readme.txt


Вложение(я):
mass_avtoizor.zip (86kb) загружен 4 раз(а).
Offline whitefox  
#649 Оставлено : 17 июля 2018 г. 16:27:00(UTC)
whitefox


Статус: Частенько заглядывает

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 183

Сказал(а) «Спасибо»: 53 раз
Поблагодарили: 154 раз в 93 постах
Автор: evatutin Перейти к цитате
Примеры привожу ниже, интересен их анализ с точки зрения whitefox


Занятно, соответствие есть, а симметрии нет. Не получается

Из пяти ЛК только один имеет нетривиальную симметрию, причем (16,31,31).
Вот, что говорит mass_avtoizor об этих пяти ЛК:

Код:
************* lk_1.txt ************** 
 
(1,1,1):     	1
(16,31,31): 	1
************* lk_2.txt ************** 
 
(1,1,1): 	1
************* lk_3.txt ************** 
 
(1,1,1): 	1
************* lk_4.txt ************** 
 
(1,1,1): 	1
************* lk_5.txt ************** 
 
(1,1,1): 	1
Пользователи, просматривающие эту тему
Guest (2)
33 Страницы«<313233
Быстрый переход  
Вы не можете создавать новые темы в этом форуме.
Вы не можете отвечать в этом форуме.
Вы не можете удалять Ваши сообщения в этом форуме.
Вы не можете редактировать Ваши сообщения в этом форуме.
Вы не можете создавать опросы в этом форуме.
Вы не можете голосовать в этом форуме.

Boinc.ru theme. Boinc.ru
Форум YAF 2.1.1 | YAF © 2003-2018, Yet Another Forum.NET
Страница сгенерирована за 0.309 секунды.