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

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

Уведомление

Icon
Error

29 Страницы«<272829
Опции
К последнему сообщению К первому непрочитанному
Online citerra  
#561 Оставлено : 30 января 2018 г. 17:24:17(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 408 раз
Поблагодарили: 322 раз в 233 постах
Внеочередной
Всего 717 790 КФ ОДЛК
Двушек 4 790
Список КФ ОДЛК https://yadi.sk/d/QwUL-ZHY3R5Nrc ( >500 000 )
Offline evatutin  
#562 Оставлено : 4 февраля 2018 г. 20:48:10(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 973 раз
Поблагодарили: 1669 раз в 805 постах
Динамика находок
Пользователь evatutin прикрепил следующие файлы:
bmp.png

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Online citerra  
#563 Оставлено : 4 февраля 2018 г. 22:50:07(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 408 раз
Поблагодарили: 322 раз в 233 постах
Всего 755 972 КФ ОДЛК
Двушек 4 805

На днях будет найден 1 000 000й КФ ОДЛК

Отредактировано пользователем 5 февраля 2018 г. 4:58:33(UTC)  | Причина: Не указана

Список КФ ОДЛК https://yadi.sk/d/QwUL-ZHY3R5Nrc ( >500 000 )
Online citerra  
#564 Оставлено : 9 февраля 2018 г. 21:13:05(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 408 раз
Поблагодарили: 322 раз в 233 постах
Всего 766 351 КФ ОДЛК
Двушек 5 348
233 четверки ( сразу 9 новых )

1 000 000я КФ ОДЛК найдена.
Но это только стотысячная часть возможных КФ. Поэтому простое пополнение списка теряет свою актуальность. Ну найдем в сто раз больше? А смысл? Все равно это будет только тысячная доля всего. Надо что-то придумывать...
Список КФ ОДЛК https://yadi.sk/d/QwUL-ZHY3R5Nrc ( >500 000 )
Offline whitefox  
#565 Оставлено : 10 февраля 2018 г. 16:18:22(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 45 раз
Поблагодарили: 123 раз в 71 постах
Представляю программу Определитель БС.

Входом служит файл input.txt со списком имён СНДЛК. Для каждого введённого имени строится соответствующий квадрат и находятся все присущие ему блочные структуры. Все найденные БС канонизируются, а канонические шаблоны БС сохраняются в соответствующем виду БС файле.

Под спойлером readme.txt



Приведу протоколы обработки трёх списков имён СНДЛК:
1) список 2749 КФ квазисимметричных ОДЛК;
2) список 507456 КФ ОДЛК;
3) список 711500 КФ ОДЛК.

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

Введено СНДЛК    : 2749
Найдено БС       : 6867

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

5x5              : 1
9x5              : 22
10x5             : 554
10x9             : 7
10x10            : 23

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


Код:
Введено СНДЛК    : 507456
Найдено БС       : 8368

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

5x5              : 1
9x5              : 22
10x5             : 558
10x9             : 7
10x10            : 23

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


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

Введено СНДЛК    : 711500
Найдено БС       : 8368

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

5x5              : 1
9x5              : 22
10x5             : 558
10x9             : 7
10x10            : 23

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


Видим, что основная масса БС приходится на квазисимметричные ДЛК.
Вложение(я):
BS_opred.zip (84kb) загружен 5 раз(а).
BS_711500.zip (7kb) загружен 4 раз(а).
Offline whitefox  
#566 Оставлено : 12 февраля 2018 г. 15:57:56(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 45 раз
Поблагодарили: 123 раз в 71 постах
Поясню, что понимается под сильно нормализованным шаблоном блочной структуры.

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

Определение. Нормализованный шаблон называется сильно нормализованным если его первый столбец и первая строка имеют следующий вид в зависимости от вида БС:
Код:
5x5 — 01234 x 01234
7x5 — 0011234 x 01234
8x5 — 00112234 x 01234
9x5 — 001122334 x 01234
10x5 — 0011223344 x 01234
7x7 — 0011234 x {0011234, 0012234}
8x7 — 00112234 x {0011234, 0012334}
9x7 — 001122334 x {0011234, 0012344}
10x7 — 0011223344 x 0011234
8x8 — 00112234 x {00112234, 00112334, 00123344}
9x8 — 001122334 x {00112234, 00112344}
10x8 — 0011223344 x 00112234
9x9 — 001122334 x {001122334, 001122344}
10x9 — 001122334 x 001122334
10x10 — 0011223344 x 0011223344


Кроме случаев 5x5, 10x5 и 10x10 (для которых каждый нормализованный шаблон автоматически является сильно нормализованным) число сильно нормализованных шаблонов много меньше числа нормализованных. Поэтому канонический шаблон БС и был определён как наименьший в лексикографическом порядке сильно нормализованный шаблон.

Ранее уже приводился список из 1031 представителя классов эквивалентности блочных структур вида nx5. В файле kanon_sh_nx5.zip эти же классы представлены своими каноническими шаблонами.

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

Как уже отмечалось, блочный ЛК может иметь несколько блочных структур. Найдём для каждой такой БС её канонический шаблон. Будем считать, что наименьший из этих канонических шаблонов определяет семейство блочных ЛК которому данный ЛК принадлежит.

Из этого определения следует, что не каждый класс эквивалентности БС определяет семейство блочных ЛК. В частности, уже отмечалось, что ЛК с блочной структурой вида nx5 в одном из срезов обязательно имеет в другом срезе блочную структуру того же вида, шаблон которой получается из шаблона первой БС инверсией строк (то есть, рассматривая строки как перестановки 5-го порядка, заменяем их обратными перестановками). Другими словами, каждый класс эквивалентности БС вида nx5 имеет двойственный ему класс того же вида. Двойственный класс может совпадать с самим классом, что, очевидно, имеет место с единственным классом вида 7x5. Но если эти классы разные, то больший из них не может представлять семейство блочных ЛК, так как всякий ЛК, имеющий БС из этого класса, обязательно имеет БС из меньшего класса.

Файл mlad_kl_nx5.zip содержит младшие члены каждой пары двойственных классов БС вида nx5:
Код:
5x5  — 2
7x5  — 1
8x5  — 7
9x5  — 45
10x5 — 549
всего: 604


Представляю программу Определитель семейств блочных ЛК, которая проверяет является ли введённый ЛК блочным, и если да, то определяет семейство которому данный ЛК принадлежит.

Файл readme.txt



Приведу протоколы работы для двух списков ЛК:
1) список 2749 КФ квазисимметричных марьяжных ДЛК;
2) список 711500 КФ марьяжных ДЛК.

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

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

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

5x5              : 1
9x5              : 16
10x5             : 300

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


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

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

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

5x5              : 1
9x5              : 16
10x5             : 302


Выходные файлы для второго списка в архиве output_nx5.zip

Оба семейства вида 5x5 были полностью проверены, марьяжные ДЛК оказались только в одном из них. Также полностью было проверено единственное семейство вида 7x5, марьяжных ДЛК оно не имеет. Как видим, ещё 318 семейств были проверены частично, вот их-то и нужно допроверить в первую очередь.

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

Вложение(я):
kanon_sh_nx5.zip (10kb) загружен 5 раз(а).
mlad_kl_nx5.zip (6kb) загружен 4 раз(а).
opred_sem_blk.zip (128kb) загружен 5 раз(а).
output_nx5.zip (4kb) загружен 5 раз(а).
thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 12.02.2018(UTC)
Offline whitefox  
#567 Оставлено : 13 февраля 2018 г. 15:39:20(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 45 раз
Поблагодарили: 123 раз в 71 постах
Присвоим имена классам эквивалентности блочных структур вида nx5 так, чтобы:
1) относительный порядок имён совпадал с относительным порядком классов;
2) канонический шаблон легко востанавливался по имени класса.

Покажу на примере единственного класса вида 7x5. Его канонический шаблон
Код:
0 1 2 3 4 
0 1 2 4 3 
1 2 0 3 4 
1 2 0 4 3 
2 3 4 0 1 
3 4 1 2 0 
4 0 3 1 2


Вычеркнем первый столбец, а также первую и последнии строки, получим
Код:
1 2 4 3 
2 0 3 4 
2 0 4 3 
3 4 0 1 
4 1 2 0


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


Заменим каждую перестановку её номером в лексикографическом порядке и запишем эти номера в строку, получим (при нумерации с нуля)
1 6 7 16 21

Теперь заменим номера соответствующими буквами латинского алфавита, получим
BGHQV

Эту строку и примем за имя класса вида 7x5. Очевидно, что оно удовлетворяет двум указанным требованиям (имена сравниваем по длине, а если длины одинаковы, то лексикографически).

Имена всех 1031 классов БС вида nx5 в архиве.
Вложение(я):
imena_kl_bs_nx5.zip (4kb) загружен 4 раз(а).
Offline whitefox  
#568 Оставлено : 17 февраля 2018 г. 16:04:02(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 45 раз
Поблагодарили: 123 раз в 71 постах
И так, для всех 604 возможных семейств блочных ЛК вида nx5 нужно найти принадлежащие им существенно различные ЛК. Один из методов поиска был изложен ранее. Этот метод был усовершенствован, что позволило сократить объём работы в 1000 раз.

Пояснения буду давать на примере семейства BGHQV — единственого семейства вида 7x5. Его канонический шаблон:
Код:
0 1 2 3 4
0 1 2 4 3
1 2 0 3 4
1 2 0 4 3
2 3 4 0 1
3 4 1 2 0
4 0 3 1 2


Расширим его до БС:
Код:
0 0 1 1 2 2 3 3 4 4
0 0 1 1 2 2 4 4 3 3
1 1 2 2 0 0 3 3 4 4
1 1 2 2 0 0 4 4 3 3
2 2 3 3 4 4 0 0 1 1
2 2 3 3 4 4 0 0 1 1
3 3 4 4 1 1 2 2 0 0
3 3 4 4 1 1 2 2 0 0
4 4 0 0 3 3 1 1 2 2
4 4 0 0 3 3 1 1 2 2


И построим на основе БС базовый ЛК:
Код:
0 1 2 3 4 5 6 7 8 9
1 0 3 2 5 4 8 9 6 7
2 3 4 5 0 1 7 6 9 8
3 2 5 4 1 0 9 8 7 6
4 5 6 7 8 9 0 1 2 3
5 4 7 6 9 8 1 0 3 2
6 7 8 9 2 3 4 5 0 1
7 6 9 8 3 2 5 4 1 0
8 9 0 1 6 7 2 3 4 5
9 8 1 0 7 6 3 2 5 4


Все блоки базового ЛК имеют прямую ориентацию (то есть на главной диагонали блока стоит меньший из двух заполнителей). Изменяя ориентацию отдельных блоков, можно построить 2^25 = 33554432 различных ЛК, но многие из них будут изоморфны. Перенумеруем каким-нибудь образом блоки, и будем произвольную 25-битовую строку называть схемой ориентации блоков, полагая, что нулевой бит означает прямую ориентацию соответствующего блока, а единичный — обратную.

Будем называть схему ориентации блоков (схему, для краткости) нормальной если все блоки пересекающиеся с первой строкой и первым столбцом имеют прямую ориентацию. Очевидно, что для произвольно схемы A найдётся такая нормальная схема B, что латинские квадраты, соответствующие схемам A и B, будут изоморфны. Например, ЛК:
Код:
1 0 2 3 4 5 6 7 8 9
0 1 3 2 5 4 8 9 6 7
2 3 4 5 0 1 7 6 9 8
3 2 5 4 1 0 9 8 7 6
4 5 6 7 8 9 0 1 2 3
5 4 7 6 9 8 1 0 3 2
6 7 8 9 2 3 4 5 0 1
7 6 9 8 3 2 5 4 1 0
8 9 0 1 6 7 2 3 4 5
9 8 1 0 7 6 3 2 5 4


приводится переименованием элементов 0<->1 к изоморфному ЛК с нормальной схемой, а ЛК:
Код:
0 1 2 3 4 5 6 7 8 9
1 0 3 2 5 4 8 9 6 7
3 2 4 5 0 1 7 6 9 8
2 3 5 4 1 0 9 8 7 6
4 5 6 7 8 9 0 1 2 3
5 4 7 6 9 8 1 0 3 2
6 7 8 9 2 3 4 5 0 1
7 6 9 8 3 2 5 4 1 0
8 9 0 1 6 7 2 3 4 5
9 8 1 0 7 6 3 2 5 4


приводится к изоморфному ЛК с нормальной схемой переименованием элементов 2<->3 совместно с перестановкой столбцов 2 и 3.

Следовательно для каждого семейства достаточно будет рассмотреть 2^16 = 65536 различных нормальных схем.

Удобно выбрать такую нумерацию блоков, чтобы блоки первой строки и первого столбца имели наибольшие номера, например (при нумерации с 0):
Код:
24 23 22 21 20
16  ?  ?  ?  ?
17  ?  ?  ?  ?
18  ?  ?  ?  ?
19  ?  ?  ?  ?


а остальные блоки занумеровать по мере появления верхнего левого угла каждого блока при сканировании БС сверху вниз слева направо:
Код:
24 23 22 21 20
16 00 04 08 12
17 01 05 09 13
18 02 06 10 14
19 03 07 11 15


Для наглядности, заменим в БС элементы каждого блока номером соответствующего блока:
Код:
24 24 23 23 22 22 21 21 20 20
24 24 23 23 22 22 08 08 12 12
16 16 00 00 04 04 21 21 20 20
16 16 00 00 04 04 08 08 12 12
17 17 01 01 05 05 09 09 13 13
17 17 01 01 05 05 09 09 13 13
18 18 02 02 06 06 10 10 14 14
18 18 02 02 06 06 10 10 14 14
19 19 03 03 07 07 11 11 15 15
19 19 03 03 07 07 11 11 15 15

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

Будем называть две схемы A и B эквивалентными, если существует изоморфизм соответствующих ЛК, переводящий БС в себя с сохранением однотипности блоков. Другими словами, группа эквивалентных преобразований схем состоит из автоморфизмов БС и изменяющих ориентацию блоков переименований элементов ЛК. Эту группу можно представить в виде прямого произведения группы трансформаций и группы инверсий. Трансформации это, по сути, автоморфизмы шаблона БС, они переставляют блоки и, иногда, могут изменить ориентацию отдельных блоков. Инверсии только изменяют ориентацию блоков.

Всякая инверсия является комбинацией элементарных инверсий. Каждому типу блоков соответствует своя элементарная инверсия, изменяющая ориентацию всех блоков данного типа. Каждой паре одинаковых столбцов БС соответствует своя элементарная инверсия, изменяющая ориентацию всех блоков принадлежащих этой паре столбцов. Каждой паре одинаковых строк БС соответствует своя элементарная инверсия, изменяющая ориентацию блоков принадлежащих этой паре строк. Пять типов блоков имеются всегда, все БС вида nx5 имеют по пять пар одинаковых столбцов, БС вида 7x5 (а также 7x7) имеют три пары одинаковых строк, то есть группа инверсий для вида 7x5 порождается 13 элементарными инверсиями, а общее число инверсий равно 2^13 = 8192.

Использование нормальных схем (вместо сбалансированных, как предлагалось в предыдущем варианте метода) позволяет ограничиться только инверсиями переводящими нормальные схемы в нормальные, а их всего 8 для вида 7x5 (4 для 8x5, 2 для 9x5, 1 для 10x5).

Найдём автоморфизмы канонического шаблона вида 7x5, их всего 6:
Код:
0123456 01234 01234
2301465 02143 10243
0123645 12034 20134
2301654 10243 21043
0123564 20134 12034
2301546 21043 02143


В первой колонке — перестановки строк, во второй — перестановки столбцов, в третей — переименования элементов шаблона. Им соответствуют следующие трансформации схем:
Код:
00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24 : 0
22,05,07,06,23,01,03,02,12,13,15,14,08,09,11,10,24,17,19,18,21,20,00,04,16 : 3150080
04,07,05,06,16,19,17,18,08,11,09,10,12,15,13,14,00,03,01,02,20,21,24,22,23 : 0
24,19,18,17,22,07,06,05,12,15,14,13,08,11,10,09,23,03,02,01,21,20,04,16,00 : 3150080
16,18,19,17,00,02,03,01,08,10,11,09,12,14,15,13,04,06,07,05,20,21,23,24,22 : 0
23,02,01,03,24,18,17,19,12,14,13,15,08,10,09,11,22,06,05,07,21,20,16,00,04 : 3150080


Здесь до двоеточия идёт перестановка битов схемы, а после — маска, определяющая инвертируемые биты. Если S — схема, p — перестановка битов, m — маска, то схема после трансформации определяется по формуле:
S' = p(S) xor m.

Если до трансформации схема была нормальной, то после она может уже не быть таковой. Нужно привести схему к нормальному виду. Для этого потребуются элементарные инверсии:
Код:
t_0=16794136, t_1=8464448, t_2=4359169, t_3=2363522, t_4=1573156
c_0=17760256, c_1=8388623, c_2=4194544, c_3=2100992, c_4=1110016
r_2=139810,   r_3=279620,  r_4=559240

Здесь в первой строке — маски элементарных инверсий для типов, во второй — маски элементарных иверсий для столбцов, в третьей — маски элементарных инверсий для строк.

Алгоритм приведения схемы к нормальному виду следующий:
1) составим последовательность t_1, t_2, t_3, t_4, c_4, c_3, c_2, c_1, t_0;
2) просканируем биты 16 .. 24 включительно, строго в этом порядке;
3) если при сканировании попадается единичный бит, то применяем к схеме соответствующую инверсию из составленной выше последовательности.

Например, пусть установлен бит 17, а остальные старшие биты сброшены. Следовательно к схеме нужно применить второй член последовательности — t_2. При этом бит 17 сбросится, а бит 22 установится. При дальнейшем сканировании будет обнаружено, что бит 22 установлен, то есть к схеме нужно применить седьмой член последовательности — c_2. При этом бит 22 сбросится и никакие другие биты установлены не будут. В результате получим нормальную схему:
S' = S xor t_2 xor c_2.

Группа из восьми инверсий, переводящих нормальные схемы в нормальные, порождается следующими тремя инверсиями:
Код:
inv_2 = t_2 xor c_2 xor r_2
inv_3 = t_3 xor c_3 xor r_3
inv_4 = t_4 xor c_4 cor r_4

Таким образом класс эквивалентности схем ориентации блоков для семейства BGHQV содержит не более 48 нормальных схем, наименьшую из них выберем в качестве канонической схемы. Всего для этого семейства имеется 1440 классов эквивалентности схем. Ранее уже приводился список из 1440 представителей классов эквивалентности схем для единственного семейства вида 7x5, те представители были выбраны другим способом.

Списки канонических схем для всех семейств видов nx5 (кроме 5x5) можно взять здесь.

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

Последнее происходит потому, что ЛК может иметь несколько эквивалентных, но не сводимых друг к другу БС, которые могут дать разные канонические схемы. Так, например, семейство BGHQV имеет 1440 канонических схем, но только 796 существенно различных ЛК. Поэтому нужна ещё дополнительная фильтрация канонических схем.
thanks 2 пользователей поблагодарили whitefox за этот пост.
citerra оставлено 17.02.2018(UTC), evatutin оставлено 18.02.2018(UTC)
Online citerra  
#569 Оставлено : 19 февраля 2018 г. 19:05:17(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 408 раз
Поблагодарили: 322 раз в 233 постах
После бурного старта, в эксперименте е44 пошли повторы
Всего 767 429 КФ ОДЛК
Двушек 5 352


Список КФ ОДЛК https://yadi.sk/d/QwUL-ZHY3R5Nrc ( >500 000 )
Пользователи, просматривающие эту тему
Guest
29 Страницы«<272829
Быстрый переход  
Вы не можете создавать новые темы в этом форуме.
Вы не можете отвечать в этом форуме.
Вы не можете удалять Ваши сообщения в этом форуме.
Вы не можете редактировать Ваши сообщения в этом форуме.
Вы не можете создавать опросы в этом форуме.
Вы не можете голосовать в этом форуме.

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