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

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

Уведомление

Icon
Error

35 Страницы«<32333435>
Опции
К последнему сообщению К первому непрочитанному
Offline Demis  
#661 Оставлено : 27 июля 2018 г. 14:45:41(UTC)
Demis


Статус: Я тут не впервой

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

Сказал(а) «Спасибо»: 7 раз
Поблагодарили: 7 раз в 7 постах
Автор: whitefox Перейти к цитате
Автор: Disel Перейти к цитате

Попробовал скомпилить, ругнулось на #include <intrin.h>, видимо что-то специфически виндовое. Других "жалоб" от компилятора не поступило.


Это внутренние функции Микрософтовского компилятора. Некоторые сторонние компиляторы их тоже понимают. В программе использована только одна из них — _BitScanForward, которая просто вставляет в код машинную команду bsf.

В качестве паллиатива, функцию _BitScanForward можно определить самостоятельно, например, так:
Код:
void _BitScanForward(unsigned long* x, unsigned long y){
	unsigned long v = y & -(int)y;
	*x = 0;
	if(v & 0xffff0000) *x += 16;
	if(v & 0xff00ff00) *x += 8;
	if(v & 0xf0f0f0f0) *x += 4;
	if(v & 0xcccccccc) *x += 2;
	if(v & 0xaaaaaaaa) (*x)++;
}

Добавлю еще немного палиатива, для тех кто на юникс-подобных машинках...
Не знаю как в линукс, но во FreeBSD подобные функции включены в ядро, примерно, с версии 4.3, т.е. лет более 10 назад.

Общее название FFS (Find first set)
https://en.wikipedia.org/wiki/Find_first_set

В разных системах и на разных языках зовется и вызывается по разному (см. ссылку на вики).

Да и вообще вариантов решения задачки масса, например:
http://graphics.stanford.edu/~seander/bithacks.html

Есть интересное обсуждение на:
https://stackoverflow.com/questions/757059/position-of-least-significant-bit-that-is-set

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

Там, где 32-ух битный вариант, компилируется (в моем случае) такой строкой:
Код:
clang++ -std=c++11 -O3 -s -Wall -Wno-missing-braces -m32 denamer.cpp -o denamer

для х64 так:
Код:
clang++ -std=c++11 -O3 -s -Wall -Wno-missing-braces denamer.cpp -o denamer

Но тогда нужно закоментировать те функции, которые с ассемблером (т.к. там х32 кодинг).

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

thanks 1 пользователь поблагодарил Demis за этот пост.
whitefox оставлено 28.07.2018(UTC)
Online citerra  
#662 Оставлено : 30 июля 2018 г. 8:22:57(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 472 раз
Поблагодарили: 340 раз в 247 постах
Оставил комментарий на сообщение на форуме проекта ODLK@Home.
Не прошло и часа - он был удален.
Конечно, там не нужны другая информация, а свои "уникальные" ( других там нет ) успехи будет выглядит не так ослепительно.
Так что "достижения" там надо делить на десять ( а они иногда бывают ), а то и больше.
Offline whitefox  
#663 Оставлено : 30 июля 2018 г. 16:08:01(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 66 раз
Поблагодарили: 164 раз в 101 постах
Цитата:
Как найти стандартное представление для симметрии?

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

Рассмотрим, например, симметрию (2,31,31). В файле standart.txt уже есть стандартное представление для этой симметрии, сейчас получим ещё одно, которое будет полезно при перечислении всех ЛК, обладающих этой симметрией.

Каждая конкретная автотопия является представителем соответствующей чистой симметрии, так автотопия:

Код:
** 9876543210 9876543210 9123456780


является представителем симметрии (2,31,31), также представителем этой симметрии будет любая упорядоченная тройка перестановок с циклическими структурами №№ 2, 31, 31, взятыми в некотором порядке.

Под №2 обозначена циклическая структура {1,1,1,1,1,1,1,1,2}, а под №31 — {2,2,2,2,2}. Приведённые перестановки в циклическом виде равны:

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


Первые две перестановки определяют циклы позиций, например, ячейка с координатами (2,5) переходит в ячейку с координатами (7,4) и наоборот, так как первая перестановка имеет цикл (27), а вторая — цикл (45), то есть имеется цикл позиций:

Код:
(2,5) <-> (7,4).


Обратите внимание, что циклы первой и второй перестановок были выбраны так специально, чтобы получить центральную симметрию.

Найдём теперь стандартное представление симметрии (2,31,31) которое будет некоторой вариацией вертикальной симметрии, для этого поменяем местами первую и третью перестановки:

Код:
** 9123456780 9876543210 9876543210


Добавим последнее представление в файл standart.txt и выполним программу get_standard для ЛК

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


для симметрии (2,31,31) вторым вариантом получим

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


Симметрия заключается в следующем:
1) первая и последняя строки центрально симметричны;
2) остальные восемь строк вертикально симметричны.

В общем случае, поиск стандартного представления для симметрии полезно начинать с минимальных представителей для соответствующих циклических структур. Такой выбор часто будет удачным, например, для симметрии (27,27,27) минимальный представитель циклической структуры №27 есть 0231564897. Поэтому добавим в файл standart.txt представление:

Код:
** 0231564897 0231564897 0312645978


(здесь 0312645978 есть перестановка обратная к 0231564897).

Запустим get_standard на ЛК:

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


получим для (27,27,27):

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

Симметрия состоит в следующем:
1) в левом верхнем углу стоит 0;
2) оставшиеся девять элементов первой строки составляют три секции по три элемента, одна из них является некоторым циклическим сдвигом строки 123, вторая — циклическим сдвигом строки 456, а третья — строки 789;
3) для первого столбце аналогично первой строке;
4) оставшиеся 81 элемент составляют 9 блоков 3x3:

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

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

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


прямые ломанные диагонали каждого блока могут иметь только один из следующих четырёх видов:
а) 000
б) циклический сдвиг строки 123
в) циклический сдвиг строки 456
г) циклический сдвиг строки 789

Причём все три ломанные диагонали одного блока принадлежат разным видам.
Online citerra  
#664 Оставлено : 2 августа 2018 г. 19:14:53(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 472 раз
Поблагодарили: 340 раз в 247 постах
На начало августа найдено 4,2 млн кф одлк
в т.ч
16951 двушек
90 трешек
346 чеверок
2 пятерки
10 шестерок
1 семерка
8 восьмерок
1 десятка


В последнее время основной поток новинок идет от Geresim@Home, особенно когда поиск начался среди квадратов с обобщенной симметрией.
Пристрелка показала перспективность ЛК данного класса. Вплотную встает вопрос о полном поиске таких ДЛК. Вот такая грандиозная задача для боинк-проекта.
Offline whitefox  
#665 Оставлено : 3 августа 2018 г. 16:19:21(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 66 раз
Поблагодарили: 164 раз в 101 постах
Второе стандартное представление для симметрии (2,31,31) позволяет использовать для перечисления всех существенно различных ЛК, обладающих этой симметрией, технику аналогичную использованной при перечислении блочных ЛК вида nx5, то есть ЛК, обладающих симметрией (1,31,31).

Здесь мы тоже имеем дело с блочными ЛК, только помимо интеркалятов появляются ещё восьмиклеточные блоки. Например, ЛК:

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


имеет двадцать блоков пяти непересекающихся типов, каждый тип имеет по одному восьмиклеточному блоку и по три интеркалята. Так тип {0,9} имеет следующий восьмиклеточный блок:

Код:
{(0,1),(7,1),(7,8),(9,8),(9,2),(5,2),(5,7),(0,7)}

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

Занумеруем типы блоков следующим образом:

Код:
{0,9} -> 0
{1,8} -> 1
{2,7} -> 2
{3,6} -> 3
{4,5} -> 4


и заменим в ЛК элементы каждого блока номером соответствующего типа, получим БС:

Код:
2 0 3 1 1 2 3 0 4 4
0 1 2 3 4 4 3 2 1 0
1 2 3 4 0 0 4 3 2 1
3 4 2 0 1 1 0 2 4 3
0 2 4 1 3 3 1 4 2 0
1 3 0 2 4 4 2 0 3 1
2 1 4 0 3 3 0 4 1 2
3 0 1 4 2 2 4 1 0 3
4 3 1 2 0 0 2 1 3 4
4 4 0 3 2 1 1 3 0 2


Видим, что последняя строка есть обращённая первая, а остальные строки симметричны относительно центра. То есть эта БС однозначно определяется своей левой половиной:

Код:
2 0 3 1 1
0 1 2 3 4
1 2 3 4 0
3 4 2 0 1
0 2 4 1 3
1 3 0 2 4
2 1 4 0 3
3 0 1 4 2
4 3 1 2 0
4 4 0 3 2

Легко показать, что все такие БС отвечают одному из двух паттернов:

Код:
0 0 1 1 2
0 . . . .
1 . . . .
1 . . . .
2 . . . .
2 . . . .
3 . . . .
3 . . . .
4 . . . .
4 4 3 2 3

0 0 1 1 2
0 . . . .
1 . . . .
1 . . . .
2 . . . .
2 . . . .
3 . . . .
3 . . . .
4 . . . .
4 3 4 2 3


Первому удовлетворяют 888960 БС, а второму 888536 БС.

Как и в прошлый раз, найдём классы эквивалентности БС. Для первого паттерна получим:

Код:
Найдено СН БС: 888960
Найдено классов БС: 4856
7x5    - 1
8x5    - 4
9x5    - 139
10x5   - 4712


Для второго приведу в следующий раз, по оценке их будет порядка 10000.

Снова на классах эквивалентности имеется отношение двойственности, так что число семейств будет почти вдвое меньше.

Эти блочные ЛК имеют по 20 блоков, поэтому их схемы ориентации блоков состоят из 20 бит. Очевидно, что произвольный такой блочный ЛК можно привести к форме у которой все восьмиклеточные блоки будут иметь прямую ориентацию. То есть всякое семейство таких блочных ЛК имеет не более 2^15 = 32768 существенно различных квадратов.

В архив pattern_44323.zip (имя по последней строке) включены канонические шаблоны для каждого класса эквивалентности этого паттерна.
Вложение(я):
pattern_44323.zip (36kb) загружен 2 раз(а).
Offline whitefox  
#666 Оставлено : 4 августа 2018 г. 14:13:26(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 66 раз
Поблагодарили: 164 раз в 101 постах
Для паттерна 43423 получили 11587 классов эквивалентности блочных структур.

Код:
Найдено СН БС: 888536
Найдено классов БС: 11587
7x5    - 2
8x5    - 12
9x5    - 371
10x5   - 11202

Канонические шаблоны для этих классов в архиве pattern_43423.zip.

Для желающих проверить корректность программы поиска, выкладываю исходник. Если директиву

Код:
#define PATTERN_44323


закомментировать, то будет обрабатываться паттерн 43423, в противном случае — паттерн 44323.

В папке с исполняемым файлом создайте подпапки:

pattern_44323
pattern_43423

для записи результатов.
Вложение(я):
pattern_43423.zip (85kb) загружен 2 раз(а).
source.zip (4kb) загружен 2 раз(а).
thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 05.08.2018(UTC)
Offline whitefox  
#667 Оставлено : 6 августа 2018 г. 11:05:34(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 66 раз
Поблагодарили: 164 раз в 101 постах
С учётом двойственности классов эквивалентности БС, остаётся 8729 семейств ЛК обладающих симметрией (2,31,31).

Код:
Найдено семейств БС для паттерна 44323:
7x5    - 1
8x5    - 4
9x5    - 80
10x5   - 2482
всего:   2567

Найдено семейств БС для паттерна 43423:
7x5    - 2
8x5    - 11
9x5    - 227
10x5   - 5922
всего:   6162


В приложенном архиве имена этих семейств. Также прилагается исходник для проверки корректности. Алгоритм именования сильно нормализованных шаблонов в основном тот же, что и в прошлый раз — различия ясны из исходника.
Вложение(я):
family_2_31_31.zip (26kb) загружен 3 раз(а).
source.zip (5kb) загружен 3 раз(а).
thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 06.08.2018(UTC)
Online citerra  
#668 Оставлено : 6 августа 2018 г. 11:46:17(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 472 раз
Поблагодарили: 340 раз в 247 постах
Решил посмотреть как дела в проекте ODLK@Home.
И чтобы оценить прогресс, посмотрел какие ОДЛК находятся в приложении odlkmin
Не понял какая стратегия выдачи кандидатов на проверку, но за месяц у маленьких кф одлк первые две строки не изменились.
Да и по сравнению с прошлым годах первая строка не изменилась. т.е от старта недалеко продвинулись.
А вариантов первой строки свыше 6 000. Так что работы проекту хватит на много лет, даже с учетом в прогрессе техники.
Да и в проекте ODLK1@Home, даже учитывая, что в нем участвует мощная команда Gridcoin, выдающая почти всю мощь в проекте,
а вся мощь более 10 раз больше ODLK@Home, работы хватит на сотню лет.
И хотя проект конечный, но практически, никто не доживет до финиша, даже если он не загнется по другим причинам.
Offline whitefox  
#669 Оставлено : 9 августа 2018 г. 10:32:50(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 66 раз
Поблагодарили: 164 раз в 101 постах
Исправил баг в программе find_symm из-за которого при повторном поиске в одном сеансе результат текущего поиска объединялся с результатами всех ранее сделанных в этом сеансе поисков.

Напомню, что в выходной файл записываются только КФ ЛК. Поэтому входной файл, из-за наличия изоморфов, может содержать больше ЛК с данной симметрией чем найдёт find_symm. Если требуется точное соответствие, предварительно канонизируйте входной файл с помощью kanonizator_lk.

Исправленную версию find_symm можно взять в архиве по старой ссылке.
thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 09.08.2018(UTC)
Online citerra  
#670 Оставлено : 10 августа 2018 г. 8:59:31(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 472 раз
Поблагодарили: 340 раз в 247 постах
Перед глобальным поиском ЛК с различными симметриями положение таково:

Квадратов с симметрией (1,31,31) найдено: 948
Квадратов с симметрией (2,31,31) найдено: 34
Квадратов с симметрией (4,31,31) найдено: 2201
Квадратов с симметрией (8,8,8) найдено: 1
Квадратов с симметрией (8,31,31) найдено: 598
Квадратов с симметрией (16,16,16) найдено: 13
Квадратов с симметрией (16,31,31) найдено: 2022
Квадратов с симметрией (21,21,21) найдено: 1
Квадратов с симметрией (21,36,36) найдено: 1
Квадратов с симметрией (27,27,27) найдено: 19
Квадратов с симметрией (41,41,41) найдено: 1
Квадратов с симметрией (41,42,42) найдено: 1

Всего 5840 ЛК с 12 симметриями
thanks 3 пользователей поблагодарили citerra за этот пост.
evatutin оставлено 10.08.2018(UTC), whitefox оставлено 11.08.2018(UTC), AlexA оставлено 12.08.2018(UTC)
Offline whitefox  
#671 Оставлено : 14 августа 2018 г. 17:44:16(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 66 раз
Поблагодарили: 164 раз в 101 постах
Представляю программу gen_2_31_31 которая по имени семейства ЛК с симметрией (2,31,31) находит все существенно различные ЛК, принадлежащие этому семейству.

файл readme.txt


По следующим ссылкам можно почитать об упомянутых программах:
find_symm
sos_operate
klpmd

Файл hash_tabl.bin можно взять в архиве.
Вложение(я):
gen_2_31_31.zip (142kb) загружен 5 раз(а).
Online citerra  
#672 Оставлено : 15 августа 2018 г. 9:13:49(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 472 раз
Поблагодарили: 340 раз в 247 постах
Распределение ЛК по семействам симметрии (2,31,31)
Вложение(я):
stat_2_31_31.txt (168kb) загружен 1 раз(а).
thanks 1 пользователь поблагодарил citerra за этот пост.
whitefox оставлено 15.08.2018(UTC)
Online citerra  
#673 Оставлено : 15 августа 2018 г. 11:01:20(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 472 раз
Поблагодарили: 340 раз в 247 постах
Определили кол-во ЛК, теперь можно и поискать марьяжные.
Набрал разных ( все неподъемно для одного компта ). и что же.
Много пустых семейств. По есть и непутые, но повторные.

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

Пришло время подключаться Герасиму.
Offline whitefox  
#674 Оставлено : 15 августа 2018 г. 13:08:34(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 66 раз
Поблагодарили: 164 раз в 101 постах
citerra, спасибо за статистику. Довольно неожиданные результаты. Оказывается:
1) симметрии (1,31,31) и (2,31,31) несовместны, то есть не существует ЛК обладающего этими симметриями одновременно;
2) симметрия (2,31,31) всегда имеет кратность 1, то есть нет ЛК обладающего несколькими симметриями этого вида (в отличии от симметрии (1,31,31) у которой кратность может достигать 15).
thanks 1 пользователь поблагодарил whitefox за этот пост.
evatutin оставлено 15.08.2018(UTC)
Online citerra  
#675 Оставлено : 15 августа 2018 г. 14:19:11(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 472 раз
Поблагодарили: 340 раз в 247 постах
Исправленный батник dms.bat
thanks 1 пользователь поблагодарил citerra за этот пост.
whitefox оставлено 16.08.2018(UTC)
Offline whitefox  
#676 Оставлено : 16 августа 2018 г. 14:50:38(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 66 раз
Поблагодарили: 164 раз в 101 постах
В программе сбора статистики был баг. Последняя строка файла stat_2_31_31.txt должна быть:

Код:
XKVIPCNZ 1884 0 1


Что означает, что семейство XKVIPCNZ содержит 1884 существенно различных ЛК, обладающих симметрией (2,31,31), причём ни один из них не обладает симметрией (1,31,31), и только один ЛК имеет кратность симметрии (2,31,31) выше единицы. Это ЛК:
Код:

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


Программа avtoizor_2.01 показывает, что у этого ЛК симметрия (2,31,31) имеет кратность пять.
Код:

(1,1,1):     1
(1,41,41):   4
(2,31,31):   5
(7,7,7):     8
(7,41,41):   12
(8,31,31):   5
(8,42,42):   20
(13,42,42):  20
(16,16,16):  25
(1,1,8)+:    1
(2,16,16)+:  5
(4,31,31)+:  6
(4,42,42)+:  24
(7,7,8)+:    8
(8,41,41)+:  16
(13,16,16)+: 20
(24,31,31)+: 4
(24,42,42)+: 16


А программа klpmd показывает, что этот ЛК не имеет изоморфных ему марьяжных ДЛК. Да и всё семейство XKVIPCNZ марьяжных ДЛК не имеет.
Online citerra  
#677 Оставлено : 17 августа 2018 г. 8:22:59(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 472 раз
Поблагодарили: 340 раз в 247 постах
Вчера началась тотальная проверка симметрий.
По порядку (2,31,31).
Ждем результаты.
Offline whitefox  
#678 Оставлено : 18 августа 2018 г. 12:39:37(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 66 раз
Поблагодарили: 164 раз в 101 постах
Перечислим все существенно различные ЛК, обладающие симметрией (4,31,31). Используем метод аналогичный использованному при перечислении ЛК, обладающих симметрией (2,31,31).

Воспользуемся следующим стандартным представлением симметрии (4,31,31):

Код:
** 9823456710 9876543210 9876543210


Получим ЛК у которого первые две строки центрально симметричны двум последним, а остальные строки вертикально симметричны.

Имеем блочный ЛК у которого блоки могут быть четырёхклеточные, восьмиклеточные, 12-клеточные. Причём некоторые восьмиклеточные блоки могут состоять из пары непересекающизся интеркалятов.

И снова БС однозначно определяется своей левой половиной. Но здесь мы имеем уже три паттерна: 44323, 44323+, 43423.

Код:
0 0 1 1 2
a b c d e
A . . . .
B . . . .
C . . . .
D . . . .
F . . . .
G . . . .
f g h i j
4 Y Z 2 3


Здесь abcdefghij есть некоторая перестановка мультимножества 0011223344, причём среди пар (af), (bg), (ch), (di), (ej) нет пары с одинаковыми элементами, а сами эти неупорядоченные пары все различны для паттернов 44323+ и 43423, и ровно две пары равны для паттерна 44323.

aABCDEFGf есть некоторая перестановка мультимножества 01122334, причём a<f, а ABCDEFG идут в неубывающем порядке.

Y=4, Z=3 для паттернов 44323, 44323+, и Y=3, Z=4 для паттерна 43423.

Левую половину БС будем называть шаблоном блочной структуры, и будем называть шаблон нормализованным если он соответствует некоторому паттерну.

Чтобы произвольная матрица, соответствующая паттерну, была шаблоном БС она должна удовлетворять следующим требованиям:

1) все столбцы суть перестановки мультимножества 0011223344;
2) все строки с третьей по восьмую включительно суть перестановки множества 01234;
3) должны выполняться условия:
Код:
    a=0 => g!=0
    b=0 => f!=0
    c=1 => i!=1
    d=1 => h!=1
    e=2 => d!=2
    i=2 => j!=2

4) для паттернов 44323 и 44323+ должны выполняться:
Код:
    f=4 => b!=4
    g=4 => a!=4
    h=3 => e!=3
    j=3 => c!=3

а для паттерна 43423 условия:
Код:
    f=4 => c!=4
    g=3 => e!=3
    h=4 => a!=4
    j=3 => b!=3


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

Зная имя семейства, легко перечислить все ЛК, принадлежащие ему.

Отредактировано пользователем 20 августа 2018 г. 12:10:41(UTC)  | Причина: Не указана

thanks 2 пользователей поблагодарили whitefox за этот пост.
citerra оставлено 18.08.2018(UTC), hoarfrost оставлено 19.08.2018(UTC)
Online citerra  
#679 Оставлено : 20 августа 2018 г. 8:57:37(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 472 раз
Поблагодарили: 340 раз в 247 постах
В симметрии (2,31,31) не нашлось ни чего интересного - ни новых конструкций, ни больших конфигураций. Двоек в пределах обычного.
Теперь надежда на следующую симметрию (4,31,31) - в ней было больше всего находок среди симметрий, да кф одлк разнообразней.
Offline whitefox  
#680 Оставлено : 20 августа 2018 г. 12:33:48(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 66 раз
Поблагодарили: 164 раз в 101 постах
А сколько всего нашлось марьяжных ДЛК с симметрией (2,31,31)? По вашим данным, раньше их было только 34.
Пользователи, просматривающие эту тему
Guest (2)
35 Страницы«<32333435>
Быстрый переход  
Вы не можете создавать новые темы в этом форуме.
Вы не можете отвечать в этом форуме.
Вы не можете удалять Ваши сообщения в этом форуме.
Вы не можете редактировать Ваши сообщения в этом форуме.
Вы не можете создавать опросы в этом форуме.
Вы не можете голосовать в этом форуме.

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