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

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

Уведомление

Icon
Error

37 Страницы«<2829303132>»
Опции
К последнему сообщению К первому непрочитанному
Offline citerra  
#581 Оставлено : 11 марта 2018 г. 8:13:32(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 493 раз
Поблагодарили: 343 раз в 249 постах
Определитель БС

Введено СНДЛК : 1238324
Найдено БС : 8693

Найдено классов БС

5x5 : 1
9x5 : 30
10x5 : 622
10x9 : 7
10x10 : 26
Offline whitefox  
#582 Оставлено : 12 марта 2018 г. 17:22:07(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 71 раз
Поблагодарили: 177 раз в 111 постах
Автор: citerra Перейти к цитате
Проверены все 604 БС вида nx5.


Вот теперь действительно все блочные ЛК вида nx5 оказались проверены. smile

В двух экспериментах были найдены 3411 классов марьяжных блочных ДЛК вида nx5. В том числе 2749 квазисимметричных в первом эксперименте и 662 не квазисимметричных во втором (к, упомянутым citerra, 131 семейству и 174 КФ нужно добавить ещё одно семейсвто вида 5x5 — JQS и 488 не квазисимметричных КФ из него). Список 662 КФ включил в выложенный ранее архив non_symm.zip, а общий список 3411 КФ — в архив mar_bdlk_nx5_3411.zip

Вот протокол применения Определителя семейств блочных ЛК к этому списку:

Код:
Определитель семейств блочных ЛК

Введено ЛК       : 3411
Из них блочных   : 3411

Найдено семейств блочных ЛК

5x5              : 1
9x5              : 22
10x5             : 338

Время работы     : 1.638 сек


Имена указанных 361 семейства можно взять в архиве imena_sem_mar_bdlk_nx5.zip. Также видим, что указанный ранее список из 14 non_symm_family увеличивается до 44-х имён:



Интересно также посмотреть на все БС присущие данным 3411 ДЛК. Вот протокол работы Определителя БС:

Код:
Определитель БС

Введено СНДЛК    : 3411
Найдено БС       : 8693

Найдено классов БС

5x5              : 1
9x5              : 30
10x5             : 622
10x9             : 7
10x10            : 26

Время работы     : 5.148 сек
Вложение(я):
mar_bdlk_nx5_3411.zip (107kb) загружен 10 раз(а).
imena_sem_mar_bdlk_nx5.zip (2kb) загружен 11 раз(а).
thanks 2 пользователей поблагодарили whitefox за этот пост.
citerra оставлено 12.03.2018(UTC), evatutin оставлено 12.03.2018(UTC)
Offline evatutin  
#583 Оставлено : 18 марта 2018 г. 16:40:01(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 1020 раз
Поблагодарили: 1813 раз в 880 постах
Не так давно было отмечено, что можно подобрать такие функции с координатами ячеек квадрата, что они образуют некоторую симметрию (названную обобщенной), которой, в свою очередь, соответствуют интересные редкие комбинаторные структуры (как минимум много двушек, как максимум — четверки и еще много чего). Таких функций нашлось 5, соответствующие им симметрии сейчас досчитываются в проекте. Нужно двигаться дальше...

А дальше получается так, что каждой функции можно сопоставить некоторую перестановку... Например, функции f(i) = -i+5 соответствует перестановка P=[5 4 3 2 1 0 9 8 7 6], которая фактически представляет собой табличное задание функции. В данной перестановке есть то же свойство, что было изначально предъявлено к функциям: P(P^{-1}) = E. Оно же может быть записано по другому: P[x] = y и P[y] = x для всех x, y от 0 до N-1. Оно же может быть оговорено и еще по другому: перестановка P не может содержать циклов длиной больше 2 (если есть циклы длины 1, т.е. элементы P[x]=x, это называется неподвижными точками, их можно умышленно исключить, т.к. для большинства симметрий, но не для всех, они не помогают).

Ну а дальше дело за малым: сформировать все перестановки P с указанным свойством, построить для них все ДЛК и найти все ОДЛК. Вроде бы просто, но... Для перестановок с неподвижными точками их число равно 9496, без неподвижных точек — 945. Т.е. даже есть мы берем простейший случай без неподвижных точек, мы получаем в итоге 945^2 ~= 893 тыс. симметрий (на гриде мы за ~ 4 месяца расчетов заканчиваем анализ 10-й из них). Одна симметрия — это от нескольких десятков тысяч до нескольких миллионов WU'шек в проекте — все это полностью перебрать наверное не получится, надо будет думать, как к этому вопросу подойти. То ли случайным перебором, то ли еще как, хз...

PS. На самом деле тут еще 3-я перестановка появляется с тем же свойством, она задает соответствие не между координатами, а между значениями элементов в ячейках квадрата, и в таком случае пространство перебора еще возрастает минимум на 3 порядка

PPS. M-преобразования скорее всего делают некоторые симметрии изоморфными друг другу... Но даже в таком случае симметрий останется минимум 945^2/15360 ~= 58, что немало

Отредактировано пользователем 18 марта 2018 г. 17:05:21(UTC)  | Причина: Не указана


kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
thanks 1 пользователь поблагодарил evatutin за этот пост.
whitefox оставлено 20.03.2018(UTC)
Offline whitefox  
#584 Оставлено : 21 марта 2018 г. 12:12:18(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 71 раз
Поблагодарили: 177 раз в 111 постах
Автор: evatutin Перейти к цитате
каждой функции можно сопоставить некоторую перестановку... Например, функции f(i) = -i+5 соответствует перестановка P=[5 4 3 2 1 0 9 8 7 6], которая фактически представляет собой табличное задание функции. В данной перестановке есть то же свойство, что было изначально предъявлено к функциям: P(P^{-1}) = E.
. . . . . .
На самом деле тут еще 3-я перестановка появляется с тем же свойством, она задает соответствие не между координатами, а между значениями элементов в ячейках квадрата


Другими словами, обобщённая симметрия определяется через тройку перестановок P, Q, R таких, что PP = QQ = RR = E (E тождественная перестановка). Согласно этому определению ЛК A будет симметричным относительно <P,Q,R> если для всех i и j из {0,...,N-1} имеет место:
A[i,j] = R(A[P(i),Q(j)]).

А это, в свою очередь, означает, что ЛК A является неподвижной точкой изотопии f, определяемой упорядоченной тройкой перестановок <P',Q',R> (здесь x' означает перестановку обратную перестановке x). Другими словами, ЛК A обладает (внутренней) симметрией f. Причём f является симметричной изотопией, в том смысле, что её график (то есть множество упорядоченных пар <X,f(X)>) является симметричным бинарным отношением на множестве латинских квадратов порядка N.

Таким образом всякая обобщённая симметрия ЛК A является некоторой его автотопией f второго порядка (ff=e).

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

Также полезно считать, что произведение симметрий тоже является симметрией, и в качестве обобщенных симметрий ЛК A рассматривать подгруппу группы автоморфизмов ЛК A, порождаемую автоморфизмами второго порядка. Порядок элементов этой подгруппы уже может отличаться от двух, а потому нет никакой логичной причины исключать из числа обобщённых симметрий автоморфизмы ЛК A не вошедшие в указанную подгруппу.

Окончательно, обобщённые симметрии присущие ЛК A можно определить как элементы группы автоморфизмов ЛК A.

Известно, что группа автоморфизмов ЛК инвариантна (с точность до изоморфизма групп) относительно эквивалентных преобразований ЛК. А именно, если f какой-то автоморфизм ЛК A, а g — изоморфизм переводящий ЛК A в ЛК B, то изоморфизм gfg' (здесь g' обозначает изоморфизм обратный изоморфизму g) будет автоморфизмом ЛК B. Это позволяет сопряженные симметрии рассматривать как эквивалентные. То есть если ЛК A имеет симметрию f_1, а ЛК B имеет симметрию f_2, и f_1 и f_2 сопряжены при помощи какого-то изоморфизма g (то есть принадлежат одному классу сопряжённости F), то мы можем считать, что ЛК A и ЛК B обладают одной и той же симметрией F. То есть мы приходим к пониманию под обобщёнными симметриями классов сопряжённости автоморфизмов.

Классы сопряжённости перестановок однозначно определяются циклической структурой перестановок, а их не так и много — 42:

Автоморфизм ЛК определяется какой-то парастрофией (шесть парастрофий имеют три циклические структуры) и тремя перестановками, то есть число симметрий не превышает 3 * 42^3 = 222264.

Рассматривая ДЛК, возможно, имеет смысл (хотя бы для начала) ограничить множество обобщённых симметрий автоморфизмами ДЛК. Так как существуют ДЛК имеющие тривиальные группы автоморфизмов ДЛК, в то время как их группа автоморфизмов ЛК нетривиальна. Пример такого ДЛК приводил evatutin для иллюстрации симметрии 15 по своей классификации:

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


Группа автоморфизмов этого ЛК содержит два элемента:
Код:
** 0123456789 0123456789 0123456789
** 0123456789 1098765432 1098765432

А группа автоморфизмов этого ДЛК содержит только один элемент:
Код:
* 0123456789 0123456789 0123456789

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

thanks 1 пользователь поблагодарил whitefox за этот пост.
evatutin оставлено 25.03.2018(UTC)
Offline AlexA  
#585 Оставлено : 21 марта 2018 г. 21:05:49(UTC)
AlexA


Статус: Administration

Медали: Переводчику: За помощь в создании сайта

Группы: Editors, Member, Administration, Russia Team Group, Moderators
Зарегистрирован: 02.10.2007(UTC)
Сообщений: 6,139
Мужчина
Российская Федерация
Откуда: "Russia Team"

Сказал «Спасибо»: 1250 раз
Поблагодарили: 1515 раз в 837 постах
Ни фига не понял, но впечатляет smile Понял основное - что я не фига не понимаю smile
Offline oleg25  
#586 Оставлено : 21 марта 2018 г. 22:01:38(UTC)
oleg25


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

Группы: Member
Зарегистрирован: 18.09.2011(UTC)
Сообщений: 106
Мужчина

Сказал «Спасибо»: 11 раз
Поблагодарили: 23 раз в 15 постах
Автор: AlexA Перейти к цитате
Ни фига не понял, но впечатляет smile Понял основное - что я не фига не понимаю smile


да подозреваю что курилка с бабезяном на каком-то коде общаются!надо у них ключи для расшифровки взять smile

Offline whitefox  
#587 Оставлено : 24 марта 2018 г. 13:05:09(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 71 раз
Поблагодарили: 177 раз в 111 постах
Для удобства, выложу полный список изоморфизмов ДЛК10 переводящие СНДЛК в СНДЛК. Число таких изоморфизмов для каждой линейки уже приводил, сами изоморфизмы можно было выдрать из исходников программ Канонизатор ДЛК.

Чтобы найти автоморфизмы ДЛК10, этот список нужно ещё отфильтровать, так как не каждый изоморфизм ДЛК может быть автоморфизмом ДЛК. Например, для второй линейки имеются только два изоморфизма, из них не тождественный изоморфизм автоморфизмом быть не может.
Вложение(я):
izomorf_sndlk10.zip (4kb) загружен 9 раз(а).
Offline citerra  
#588 Оставлено : 25 марта 2018 г. 22:27:43(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 493 раз
Поблагодарили: 343 раз в 249 постах
Всего 1 260 440 КФ ОДЛК
Двушек 6 396


Offline whitefox  
#589 Оставлено : 26 марта 2018 г. 16:37:02(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 71 раз
Поблагодарили: 177 раз в 111 постах
Итак, к СНДЛК10 применимы только 356 нетривиальных изоморфизмов (и все они — изотопии, поэтому в ниже следующем под изоморфизмами и автоморфизмами следует понимать изотопии и автотопии соответственно). Для очищения этого списка от изоморфизмов, которые в принципе не могут быть автоморфизмами, можно воспользоваться следующим ниже необходимым условием. Но сначала несколько определений.

Каждый изоморфизм представлен тремя перестановками, например, единственный нетривиальный изоморфизм, применимый к СНДЛК второй линейки, будет:
Код:
1046273598 8953726401 0164382759

Первая перестановка — это перестановка строк p_r, вторая — перестановка столбцов p_c, а третья — переименование элементов p_v.

Первые две перестановки определяют циклы позиций, то есть если начать с позиции (i,j), то следующей позицией будет (p_r(i),p_c(j)), далее (p_r^2(i),p_c^2(j)) и так далее пока не вернёмся снова в позицию (i,j). Для данного изоморфизма имеется 50 циклов позиций, все длины два. Минимальное число циклов позиций равно 10, а максимальное 68. Наименьшая длина цикла — 1, а наибольшая — 12.

Третья перестановка определяет циклы значений, для чего запишем её в циклической форме:
Код:
(0)(1)(7)(9)(26)(34)(58)

Всего семь циклов, четыре единичной длины и три длины два. Возможное число циклов — от 1 до 8, а длины циклов — от 1 до 10. Занумеруем эти циклы от 0 до 6, и заменим каждый элемент цикла номером цикла, получим мультимножество:
Код:
0123445566

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

Предположим, что во второй линейке найдётся СНДЛК L для которого данный изоморфизм будет автоморфизмом. То есть для всех i и j принадлежащих X={0,1,2,3,4,5,6,7,8,9} имеет место равенство:
L(i,j) = p_v(L(p_r(i),p_c(j)))
Из которого видно, что каждому циклу позиций поставлен в соответствие некоторый цикл значений, причём длина цикла значений является делителем длины соответствующего цикла позиций. Также видим, что если во все позиции каждого цикла позиций записать номер сопоставленного ему цикла значений, то в каждой строке и в каждом столбце и на обеих диагоналях будут стоять элементы приведённого выше мультимножества. Это и есть необходимое условие, для его формулировки обобщим введённое ранее понятие квази-латинского квадрата.

Определение. Квадрат порядка N будем называть квази-латинским квадратом если элементы каждой его строки и каждого его столбца суть элементы одного и того же мультимножества мощности N.

Если все элементы мультимножества имеют кратность 1, то квази-ЛК будет ЛК.

Утверждение. Для того чтобы изоморфизм мог быть автоморфизмом для некоторого ЛК, необходимо, чтобы существовало отображение множества циклов позиций на множество циклов значений, удовлетворяющее условиям:
1) длина каждого цикла позиций делится на длину соответствующего цикла значений;
2) при записи в позиции каждого цикла позиций номера соответствующего цикла значений, получается квази-латинский квадрат соответствующий мультимножеству значений.

Из этого утверждения легко выводится следствие.

Следствие. Если перестановка p_r (p_c) имеет фиксированные элементы, то циклическая структура перестановки p_c (p_r) должна совпадать с циклической структурой перестановки p_v.

Следствие из следствия. Если перестановки p_r и p_c имеют фиксированные элементы, то все три перестановки должны иметь одинаковую циклическую структуру.

356 изоморфизмов имеют 42 различные циклические структуры:



Из них Следствию и Следствию из следствия удовлетворяют только 23:



Это только первый шаг фильтрации, на втором нужно применить само необходимое условие.

Отредактировано пользователем 19 апреля 2018 г. 11:44:48(UTC)  | Причина: Не указана

thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 26.03.2018(UTC)
Offline whitefox  
#590 Оставлено : 27 марта 2018 г. 16:37:01(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 71 раз
Поблагодарили: 177 раз в 111 постах
Утверждение. Изоморфизм ДЛК будет автоморфизмом тогда и только тогда, когда:
1) выполнено необходимое условие;
2) соответствующий квази-ЛК является некоторым аналогом блочной структуры.

Упомянутый аналог БС тоже будем называть БС, только блоками в ней будут не обязательно интеркаляты.

По квази-ЛК Q, соответствующего необходимому условию, построим следующий граф G:
1) вершинами графа G будут клетки квадрата Q;
2) если вершины a и b принадлежат одному циклу позиций, причём a непосредственно предшествует b, то (a,b) ребро, окрасим это ребро в белый цвет;
3) если вершинам a и b сопоставлен один цикл значений и принадлежат они одной строке (одному столбцу) квадрата Q, то (a,b) ребро, окрасим его в чёрный цвет.

В этом графе возможны кратные рёбра и петли, но нам они не помешают.

Каждая компонента связности графа G состоит их нескольких циклов позиций (один — тоже несколько), сопоставленных одному циклу значений, и связанных чёрными рёбрами. Выберем в каждом цикле позиций начальную позицию, а в каждой компоненте связности начальный цикл позиций. Значение начальной позиции однозначно определяет значения всех остальных позиций цикла. Будем считать, что задание значения начальной позиции цикла, определяет его ориентацию. Очевидно, что значения начальных позиций начальных циклов можно выбирать независимо, но значения начальных позиций из одной компоненты связности должны выбираться согласовано. Если циклу позиций сопоставлен цикл значений длины k, то теоретически этот цикл позиций может иметь k ориентаций (для начального цикла это так и есть).

Определение. Совокупность вершин компоненты связности графа G будет блоком в квази-ЛК Q, если можно так выбрать ориентацию всех циклов позиций, входящих в данную компоненту связности, что вершины, связанные чёрным ребром, будут иметь различные значения.

Квази-ЛК Q будет БС если каждая компонента связности графа G определяет блок.
Offline whitefox  
#591 Оставлено : 29 марта 2018 г. 15:55:16(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 71 раз
Поблагодарили: 177 раз в 111 постах
Продолжим.

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

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

Цикл позиций будем называть самосогласованным, если все его внутренние рёбра согласованы.

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

Для проверки согласованности пары смежных циклов позиций, для каждого чёрного ребра, соединяющего эти циклы, определим множество разностей индексов допустимых ориентаций второго цикла относительно первого (множества разностей, для простоты). Пусть чёрное ребро соединяет вершину a первого цикла позиций с вершиной b второго. И пусть d_a будет редуцированным расстояние вершины a в первом цикле позиций, а d_b — редуцированным расстоянием вершины b во втором. Тогда элементы множества разностей определяются по формуле:
(d_a - d_b + i) mod k
здесь k — длина цикла значений сопоставленного данной компоненте связности (всем циклам позиций компоненты связности сопоставляется один цикл значений), а i принадлежит множеству {1,...,k-1}. Например, пусть k = 4, d_a = 1, d_b = 2, тогда множество разностей будет: {0,1,2}.

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

C)
Последовательность трёх и более циклов позиций будем называть замкнутой цепочкой циклов позиций, если первый цикл смежен со вторым, второй — с третьим, . . . , последний — с первым. Пару соседних циклов цепочки будем называть звеном. Для каждого звена найдём множество чёрных рёбер, соединяющие вершины одного цикла позиций звена с вершинами другого, и рассмотрим объединение U этих множеств. Будем говорить, что замкнутая цепочка циклов позиций согласована (с определением блока) если можно так выбрать ориентации этих циклов позиций, что все чёрные рёбра из объединения U будут соединять вершины с различными значениями. Для согласованности замкнутой цепочки необходимо, чтобы каждое её звено было согласованной парой смежных циклов позиций, но этого недостаточно.

Для проверки согласованности замкнутых цепочек циклов позиций, построим вспомогательный взвешенный орграф H. Каждому циклу позиций сопоставим во взаимно-однозначное соответствие одну вершину орграфа H. Пусть циклы позиций A и B смежны, и пусть W обозначает пересечение соответствующих множеств разностей индексов допустимых ориентаций цикла позиций B относительно цикла позиций A, тогда в орграф H входит дуга A->B с множеством весов W. Дугу A->B можно заменить дугой B->A с множеством весов W' (для наших целей это безразлично), где каждому элементу i множества W взаимно-однозначно соответствует элемент (k-i) множества W' (здесь k — длина соответствующего цикла значений).

Каждой замкнутой цепочки циклов позиций взаимно-однозначно соответствует некоторый контур орграфа H. Выберем направление обхода контура, и если направление дуги A->B не совпадает с направлением обхода, то заменим её дугой B->A с соответствующим изменением множества весов. Замкнутая цепочка будет согласованной если для каждой дуги полученного контура можно так выбрать вес из соответствующего множества весов, что их сумма равна нулю по модулю k (длины цикла значений). Будем такой набор весов называть корректным.

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

Пусть, например, несколько контуров орграфа H имеют общую дугу h (и никакие два из этих контуров не имеют других общих дуг). И пусть для каждого из этих контуров существует непустое множество корректных наборов весов, то есть соответствующие замкнутые цепочки циклов позиций согласованы. Для каждого из этих контуров найдем множество корректных весов дуги h, и построим их пересечение. Если пересечение не пусто, то соответствующие замкнутые цепочки циклов позиций согласованы в совокупности.

Проверку согласованности всех замкнутых цепочек и их согласованности в совокупности можно выполнять одновременно. Для этого зафиксируем направления дуг орграфа H. Сопоставим каждой дуге h орграфа H переменную w_h которая может принимать значения только из соответствующего множества весов W_h. Для каждого контура орграфа H составим уравнение Кирхгофа, для чего:
1) выберем направление обхода контура;
2) для каждой дуги h контура добавим в уравнение переменную w_h со знаком "+" если направление дуги h совпадает с направлением обхода контура, и со знаком "-" в противном случае;
3) приравняем полученное уравнение нулю;
4) если дуга h не входит ни в один контур, то добавим к системе уравнение w_h = w_h.

Решим полученную систему уравнений как систему сравнений по модулю k, где k — длина соответствующего цикла значений.
Если система сравнений имеет решение, то все замкнутые цепочки циклов позиций соответствующей компоненты графа G согласованы и согласованы в совокупности.

То есть справедливо следующее утверждение.

Утверждение. Компонента связности K графа G представляет блок квази-ЛК Q тогда и только тогда, когда:
1) все циклы позиций компоненты K самосогласованы;
2) все пары смежных циклов позиций компоненты K согласованы;
3) все замкнутые цепочки циклов позиций компоненты K согласованы и согласованы в совокупности.

Очевидно, что если компонента K графа G представляет блок квази-ЛК Q, то число ориентаций этого блока равно k*T,
где k — длина соответствующего цикла значений, а T — число решений соответствующей системы уравнений Кирхгофа.

Отредактировано пользователем 12 апреля 2018 г. 13:06:25(UTC)  | Причина: Не указана

Offline whitefox  
#592 Оставлено : 31 марта 2018 г. 10:49:57(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 71 раз
Поблагодарили: 177 раз в 111 постах
Пусть A — некоторый цикл длины d_a перестановки строк, а B — некоторый цикл длины d_b перестановки столбцов, соответствующий им цикл позиций C имеет длину
d_c = lcm(d_a, d_b).

Можно показать, что:
1) цикл позиций C имеет внутренние рёбра тогда и только тогда, когда d_a != d_b;
2) цикл позиций 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).

Следствие. Если перестановка p_r имеет цикл длины d_r, а перестановка p_c — цикл длины d_c, причём d_r и d_c взаимно просты, то для того чтобы изоморфизм <p_r,p_c,p_v> был автоморфизмом необходимо, чтобы перестановка p_v имела цикл длины
d_v = d_r * d_c.

Это позволяет исключить ещё две циклические структуры:
Код:
0220000000 0220000000 0220000000 -> {2,3}{2,3}{2,3}
0021000000 0021000000 0021000000 -> {3,4}{3,4}{3,4}


Итого остаётся проверить 167 изоморфизмов в 33 линейках:

Отредактировано пользователем 12 апреля 2018 г. 13:00:28(UTC)  | Причина: изменил определение необходимого и достаточного условия самосогласованности цикла позиций

thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 31.03.2018(UTC)
Offline citerra  
#593 Оставлено : 9 апреля 2018 г. 10:00:08(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 493 раз
Поблагодарили: 343 раз в 249 постах
Всего 1 270 708 КФ ОДЛК
Двушек 6 418

Offline citerra  
#594 Оставлено : 19 апреля 2018 г. 16:33:11(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 493 раз
Поблагодарили: 343 раз в 249 постах
Всего 1 325 357 КФ ОДЛК
Двушек 6 507

Offline citerra  
#595 Оставлено : 27 апреля 2018 г. 11:04:08(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 493 раз
Поблагодарили: 343 раз в 249 постах
Найдены новые типы ОДЛК
Семерка и Десятка
thanks 1 пользователь поблагодарил citerra за этот пост.
evatutin оставлено 28.04.2018(UTC)
Offline evatutin  
#596 Оставлено : 29 апреля 2018 г. 8:05:52(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 1020 раз
Поблагодарили: 1813 раз в 880 постах
Автор: citerra Перейти к цитате
Найдены новые типы ОДЛК
Семерка и Десятка


Подправил соответствующую последовательность в OEIS: https://oeis.org/A287695

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline whitefox  
#597 Оставлено : 7 мая 2018 г. 10:44:27(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 71 раз
Поблагодарили: 177 раз в 111 постах
Представляю программу klpmd, которая фактически есть программа family_mar из которой выброшена проверка ДЛК на квазисимметричность и изменён консольный вывод. Другими словами, это Канонизатор_ЛК_по_ДЛК и Ортогон_У в "одном флаконе".

Файл readme.txt



Ранее представлял пакет программ под общим названием Канонизатор_ЛК_по_ДЛК. Добавил в него программу klpmd, скорость работы значительно возросла. Для запуска используйте файл kanon_new.bat.

Файл readme_new.txt



Если klpmd использовать самостоятельно, то нужный для работы файл hash_tabl.bin можно взять из упомянутого выше пакета программ.
Вложение(я):
klpmd.zip (52kb) загружен 5 раз(а).
thanks 2 пользователей поблагодарили whitefox за этот пост.
evatutin оставлено 14.05.2018(UTC), citerra оставлено 22.05.2018(UTC)
Offline citerra  
#598 Оставлено : 8 мая 2018 г. 13:46:14(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 493 раз
Поблагодарили: 343 раз в 249 постах
Статистика к списку из 2 000 697 КФ ОДЛК
(скачать по ссылке в подписи )

Распределение по линейкам

- самые населенные, более 100000

1034685972 142 966
1034678952 141 785
1032675894 139 594
1034678925 132 489
1034628975 130 748
1230675948 108 583

- самые редкие, менее 4000

1204635978 3 161
1034275698 3 391
1234078956 3 692
1037892654 3 695


Самые маленькие первые КФ в линейке
( в скобках - номер в текущем списке )


1034268957

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

1034278965 ( #3 )

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

1034278956 ( #4 )

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

1034268975 ( #9 )

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

1034728956 ( #964 )

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

Самые большие среди первых

1037685924 ( #855886 )

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


1034687925 ( #872422 )

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

1034685927 ( #873204 )

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


Самые большие КФ в линейках



1230675948

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

1034689572 ( -254 )
-254 означает 254 КФ с конца в данном списке

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

1034678925 ( -263 )

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


1034685972 ( -277 )

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

1034678952 ( -278 )

0 9 8 7 6 4 5 2 3 1
9 1 5 4 8 7 3 6 0 2
1 6 2 9 0 8 7 3 5 4
7 0 6 3 2 9 4 5 1 8
8 3 7 5 4 6 1 9 2 0
4 8 3 0 7 5 2 1 9 6
3 2 0 8 9 1 6 4 7 5
5 4 9 2 1 0 8 7 6 3
6 5 4 1 3 2 9 0 8 7
2 7 1 6 5 3 0 8 4 9
Offline citerra  
#599 Оставлено : 14 мая 2018 г. 9:59:34(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 493 раз
Поблагодарили: 343 раз в 249 постах
Четверок стало 250, а двушек 8888
Offline whitefox  
#600 Оставлено : 14 мая 2018 г. 13:31:37(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 71 раз
Поблагодарили: 177 раз в 111 постах
Продолжим изучение блочных ЛК.

ЛК с блочными структурами вида nx5 рассмотрены полностью. Таких ЛК существует 26045080 с точностью до изоморфизма главных классов. Приступим к изучению блочных ЛК, имеющих только БС старших видов (7x7 и старше).

Нам потребуется уточнить определение нормальной схемы ориентации блоков.

Определение. Будем схему ориентации блоков называть нормальной если определённое число её старших битов нулевые. Число таких битов зависит от вида и подвида соответствующего шаблона БС.

Ранее приводилось определение сильно нормализованного шаблона БС. Согласно этому определению, шаблоны БС видов 7x7, 8x7, 9x7, 9x8 и 9x9 имеют по два подвида, а шаблоны БС вида 8x8 — три. Имеет место следующая зависимость числа значащих битов нормальной схемы от вида и подвида шаблона БС:

Код:
nx5    -> 16
7x7_0  -> 17
7x7_1  -> 16
8x7_0  -> 17
8x7_1  -> 16
9x7_0  -> 17
9x7_1  -> 16
10x7   -> 17
8x8_0  -> 18
8x8_1  -> 17
8x8_2  -> 16
9x8_0  -> 18
9x8_1  -> 17
10x8   -> 18
9x9_0  -> 19
9x9_1  -> 18
10x9   -> 19
10x10  -> 20


Таким образом, например, семейство блочных ЛК вида 10x10 имеет не более 2^20=1048576 существенно различных ЛК.

Определение сильно нормализованного шаблона и способ нумерации блоков были намерено выбраны так, чтобы нормальные схемы ориентации блоков обладали полезным свойством: если шаблон вида nxm имеет k значащих битов в нормальной схеме, то все биты с номерами k и старше будут нулевыми.

Обратите внимание, что если вид имеет несколько подвидов, то чем старше подвид тем меньше значащих битов имеет нормальная схема. Поэтому, в целях уменьшения объёма работы в два - четыре раза, изменим определение канонического шаблона.

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

По старому определению, шаблон назывался каноническим если он был лексикографически наименьшим среди всех эквивалентных сильно нормализованных шаблонов (то есть подвид шаблона не учитывался). Для шаблонов ширины 5 или высоты 10 новое определение равносильно старому, так как различных подвидов такие шаблоны не имеют.

Также изменим упорядочение канонических шаблонов:
1) из двух шаблонов меньше тот у которого меньше ширина;
2) из двух шаблонов одинаковой ширины меньше тот у которого меньше высота;
3) из двух шаблонов одинакового вида меньше тот у которого подвид больше;
4) из двух шаблонов одинакового подвида меньше тот который меньше в лексикографическом порядке.

Соответствующие изменения внесены в программу Определитель семейств блочных ЛК.

Файл readme.txt

Вложение(я):
opred_sem_blk_2.01.zip (129kb) загружен 6 раз(а).
thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 14.05.2018(UTC)
Пользователи, просматривающие эту тему
Guest
37 Страницы«<2829303132>»
Быстрый переход  
Вы не можете создавать новые темы в этом форуме.
Вы не можете отвечать в этом форуме.
Вы не можете удалять Ваши сообщения в этом форуме.
Вы не можете редактировать Ваши сообщения в этом форуме.
Вы не можете создавать опросы в этом форуме.
Вы не можете голосовать в этом форуме.

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