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

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

Уведомление

Icon
Error

19 Страницы«<1314151617>»
Опции
К последнему сообщению К первому непрочитанному
Offline citerra  
#281 Оставлено : 6 апреля 2017 г. 7:28:14(UTC)
citerra


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

Медали: Первооткрывателю: Результат в проекте SAT@homeДонор: За финансовую помощь сайту

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

Сказал(а) «Спасибо»: 330 раз
Поблагодарили: 308 раз в 223 постах
Эксперимент зациклился. Значительного прироста не удалось получить, вернусь к нему позже.
Нашлась 47я КФ ОДЛК. А Общее кол-во перевалило за 46тыс. ( добровольцы и проект Gerasim@Home продолжают радовать ) - 46021
Offline citerra  
#282 Оставлено : 7 апреля 2017 г. 22:33:55(UTC)
citerra


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

Медали: Первооткрывателю: Результат в проекте SAT@homeДонор: За финансовую помощь сайту

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

Сказал(а) «Спасибо»: 330 раз
Поблагодарили: 308 раз в 223 постах
На данный момент число КФ ОДЛК достигло 46299, в.ч. двушек 2621
Offline citerra  
#283 Оставлено : 11 апреля 2017 г. 10:12:20(UTC)
citerra


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

Медали: Первооткрывателю: Результат в проекте SAT@homeДонор: За финансовую помощь сайту

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

Сказал(а) «Спасибо»: 330 раз
Поблагодарили: 308 раз в 223 постах
Уже более 47тыс - 47045 ( 2621 двушек )
Offline citerra  
#284 Оставлено : 12 апреля 2017 г. 8:29:03(UTC)
citerra


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

Медали: Первооткрывателю: Результат в проекте SAT@homeДонор: За финансовую помощь сайту

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

Сказал(а) «Спасибо»: 330 раз
Поблагодарили: 308 раз в 223 постах
50я КФ ОДЛК
Цитата:
0 1 2 3 4 5 6 7 8 9
1 2 0 4 3 6 5 9 7 8
2 0 1 5 6 3 4 8 9 7
3 5 7 8 2 9 1 0 6 4
7 8 5 6 9 2 3 1 4 0
6 7 8 9 5 4 0 2 1 3
5 6 9 0 8 1 7 4 3 2
9 4 6 7 1 8 2 3 0 5
8 3 4 2 0 7 9 6 5 1
4 9 3 1 7 0 8 5 2 6
Следом и 51я
Всего 47057
Offline citerra  
#285 Оставлено : 14 апреля 2017 г. 21:25:08(UTC)
citerra


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

Медали: Первооткрывателю: Результат в проекте SAT@homeДонор: За финансовую помощь сайту

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

Сказал(а) «Спасибо»: 330 раз
Поблагодарили: 308 раз в 223 постах
Есть 48 000 КФ ОДЛК
Offline citerra  
#286 Оставлено : 20 апреля 2017 г. 11:33:49(UTC)
citerra


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

Медали: Первооткрывателю: Результат в проекте SAT@homeДонор: За финансовую помощь сайту

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

Сказал(а) «Спасибо»: 330 раз
Поблагодарили: 308 раз в 223 постах
Положение на текущий момент:
Всего 49 056 КФ ОДЛК
двушек - 2 708
четверок - 213
54 КФ с самого начала

Среди симметричных
1687 двушек
138 четверок

Отредактировано пользователем 20 апреля 2017 г. 11:55:17(UTC)  | Причина: Не указана

Offline citerra  
#287 Оставлено : 22 апреля 2017 г. 7:30:35(UTC)
citerra


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

Медали: Первооткрывателю: Результат в проекте SAT@homeДонор: За финансовую помощь сайту

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

Сказал(а) «Спасибо»: 330 раз
Поблагодарили: 308 раз в 223 постах
55я КФ ОДЛК
Цитата:
0 1 2 3 4 5 6 7 8 9
1 2 0 4 3 6 5 9 7 8
2 0 1 5 6 3 4 8 9 7
3 5 7 9 8 1 2 0 4 6
7 9 8 0 5 4 3 6 1 2
8 6 4 2 0 7 9 5 3 1
6 7 5 1 9 0 8 4 2 3
9 4 6 8 7 2 1 3 5 0
4 3 9 7 2 8 0 1 6 5
5 8 3 6 1 9 7 2 0 4


Offline whitefox  
#288 Оставлено : 25 апреля 2017 г. 14:23:45(UTC)
whitefox


Статус: Интересующийся

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

Сказал(а) «Спасибо»: 25 раз
Поблагодарили: 79 раз в 48 постах
Представляю новую версию Канонизатора ДЛК. Объём работы существенно сократился — вместо проверки 15360 изоморфов теперь достаточно проверить не более 47. Для этого потребовалось изменить определение канонической формы, а точнее, определение нормализованного ДЛК. Будем говорить, что ДЛК сильно нормализован если его главная диагональ имеет вид 0123456789, а побочная один из следующих 67 видов:


Этот список разделён на две части не случайно (но об этом и всей теории в другой раз).

Каноническую форму ДЛК определим как наименьший в лексикографическом порядке сильно нормализованный ДЛК. Оказывается, что любой главный класс ДЛК содержит не более 48 сильно нормализованных ДЛК, а некоторые так и вовсе по одному.
thanks 2 пользователей поблагодарили whitefox за этот пост.
citerra оставлено 25.04.2017(UTC), AlexA оставлено 25.04.2017(UTC)
Offline citerra  
#289 Оставлено : 26 апреля 2017 г. 11:05:22(UTC)
citerra


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

Медали: Первооткрывателю: Результат в проекте SAT@homeДонор: За финансовую помощь сайту

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

Сказал(а) «Спасибо»: 330 раз
Поблагодарили: 308 раз в 223 постах
Превышен порог 50 000 КФ ОДЛК
Выкладываю список в новом формате
В нем
47054 однушек
2732 двушек
1 тройка
218 четверок
6 шестерок
4 восьмерки
В этом же списке и 58 первых КФ ОДЛК в лексикографическом порядке
Всего 50 015
Вложение(я):
cf50015.rar (2,383kb) загружен 4 раз(а).
thanks 2 пользователей поблагодарили citerra за этот пост.
whitefox оставлено 26.04.2017(UTC), evatutin оставлено 26.04.2017(UTC)
Offline whitefox  
#290 Оставлено : 26 апреля 2017 г. 12:10:29(UTC)
whitefox


Статус: Интересующийся

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

Сказал(а) «Спасибо»: 25 раз
Поблагодарили: 79 раз в 48 постах
Обещанная теория. smile

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

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

Всего двухсторонних беспорядков 10-го порядка имеется 440192. Это и есть исчерпывающий ответ на первый вопрос.

Перейдём ко второму вопросу. Для начала рассмотрим влияние на побочную диагональ М-преобразований с последующей нормализацией. Пусть d обозначает побочную диагональ, а m произвольную М-перестановку (перестановку с условием: m(9 - i) = 9 - m(i)). В результате применения к нормализованному ДЛК М-преобразования, соответствующего М-перестановке m, с последующей нормализацией, побочная диагональ d перейдёт в m'dm, где m' означает перестановку обратную к перестановке m.

d -> m'dm

Другими словами, при М-преобразовании нормализованного ДЛК с последующей нормализацией, побочная диагональ переходит в сопряжённую с ней по М-группе. Что позволяет нам выбрать в каждом классе сопряжённых по М-группе двухсторонних беспорядков по одному представителю и ограничиться рассмотрением только нормализованных ДЛК с побочной диагональю равной одному из этих представителей.

Всего классов сопряженных по М-группе двухсторонних беспорядков имеется 156:
В приведённом списке для каждого класса указана его мощность (count) и представитель (kf). В качестве представителя был выбран наименьший в лексикографическом порядке элемент.

Для произвольного двухстороннего беспорядка p обозначим через C(p) номер его класса сопряжения по М-группе (определённый по указанному выше списку).

М-преобразования не изменяют ролей строк-столбцов и главной-побочной диагоналей. Помимо них нужно рассмотреть преобразования меняющие местами строки-столбцы и/или главную-побочную диагонали. Возьмём, например, транспонирование (меняет местами строки-столбцы, но роли диагоналей сохраняются), вертикальную симметрию (меняет роли диагоналей, но роли строк-столбцов сохраняются) и их всевозможные произведения (что даст группу симметрий квадрата из 8 элементов, но из которых только 4 различных с точностью до поворота на 180 градусов, так как последний является М-преобразованием).

При транспонировании побочная диагональ d переписывается в обратном порядке, например, 1284639075 переходит в 5709364821. Что эквивалентно умножению справа (для определённости, умножение перестановок выполняем справа налево, то есть ab(i) = a(b(i)) для перестановок a b и допустимых i) на М-перестановку g = 9876543210.

d -> dg

При вертикальной симметрии с последующей нормализацией побочная диагональ d переходит в обратную ей перестановку d'.

d -> d'

При совместном применении транспонирования и вертикальной симметрии совершенно не важно в каком порядке они выполняются, так как (dg)' и d'g сопряжены по М-группе ввиду g' = g и (dg)' = g'd', то есть C((dg)' ) = C(d'g).

Для каждого из 156 представителей p определим четыре числа: C(p), C(p' ), C(pg) и C((pg)' ). Пусть A обозначает наименьшее из этих четырёх чисел, и пусть a обозначает представителя класса A. Каждому из 156 классов поставим в соответствие упорядоченную четвёрку <C(a),C(a' ),C(ag),C((ag)' )>. Всего имеется 67 различных четвёрок, причём 56 из них вырождаются в пары (у них первые два числа равны, также как и последние два). Вот полный список (вначале пары):
Собственно говоря, вчерашний список содержит представителей классов, идущих первыми в каждом кортеже.

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

Собственно, это и есть ответ на второй вопрос.

Пояснения по алгоритму канонизации ДЛК, опирающемуся на приведённые идеи, дам в следующий раз.

PS Генерация ДЛК сильно ускорится если генерировать только сильно нормализованные ДЛК. Каждый из 67 представителей даст свою линейку ДЛК.

PPS Ввиду быстроты проверки каноничности сильно нормализованных ДЛК, указанный в PS генератор ДЛК, легко превратить в генератор КФ ДЛК. Который, в свою очередь, можно применить для подсчёта главных классов ДЛК.

Отредактировано пользователем 27 апреля 2017 г. 9:45:05(UTC)  | Причина: Не указана

thanks 3 пользователей поблагодарили whitefox за этот пост.
citerra оставлено 26.04.2017(UTC), AlexA оставлено 26.04.2017(UTC), evatutin оставлено 26.04.2017(UTC)
Offline evatutin  
#291 Оставлено : 26 апреля 2017 г. 14:20:23(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 920 раз
Поблагодарили: 1486 раз в 727 постах
whitefox
1. Как соотносятся классы привычной нам канонизации и предложенные классы? (Строгое соответствие, кто-то в кого-то вложен, пересекаются, ...)
2. Сохраняют ли ДЛК в пределах предложенных классов основные свойства (наличие ОДЛК, число трансверсалей, структура трансверсалей)?

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline whitefox  
#292 Оставлено : 26 апреля 2017 г. 15:39:12(UTC)
whitefox


Статус: Интересующийся

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

Сказал(а) «Спасибо»: 25 раз
Поблагодарили: 79 раз в 48 постах
Автор: evatutin Перейти к цитате
whitefox
1. Как соотносятся классы привычной нам канонизации и предложенные классы? (Строгое соответствие, кто-то в кого-то вложен, пересекаются, ...)
2. Сохраняют ли ДЛК в пределах предложенных классов основные свойства (наличие ОДЛК, число трансверсалей, структура трансверсалей)?


1. Соответствие строгое. Это всё те же главные классы ДЛК. Ведь, что такое КФ? Это всего лишь представитель своего класса эквивалентности. Выбрать же представителя можно множеством способов, одни способы могут быть лучше, другие хуже, но при любом способе представляемый класс остаётся одним и тем же. При старом способе в качестве представителя выбирался наименьший в лексикографическом порядке нормализованный ДЛК, при новом — наименьший в лексикографическом порядке сильно нормализованный ДЛК. При старом определении КФ каждый главный класс ДЛК мог иметь до 15360 нормализованных ДЛК и все их нужно было проверить на минимальность. При новом определении КФ каждый главный класс ДЛК может иметь не более 48 сильно нормализованных ДЛК и их проверка на минимальность выполнится значительно быстрее.

2. Сохраняют, так как классы эквивалентности остаются те же самые, изменяются только представители этих классов. Указанные характеристики являются инвариантом класса эквивалентности, то есть не зависят от выбора представителя, так как присущи любому ДЛК, принадлежащему данному классу. Собственно, именно по этому и можно представлять классы эквивалентности через их представителей, без разницы каким способом эти представители выбраны.

Отредактировано пользователем 26 апреля 2017 г. 16:09:37(UTC)  | Причина: Не указана

thanks 2 пользователей поблагодарили whitefox за этот пост.
evatutin оставлено 26.04.2017(UTC), citerra оставлено 27.04.2017(UTC)
Offline evatutin  
#293 Оставлено : 26 апреля 2017 г. 18:29:49(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 920 раз
Поблагодарили: 1486 раз в 727 постах
whitefox
1. В таком случае получается, что сильно нормализованные ДЛК С1 — это подмножество в составе соответствующего главного класса ДЛК С2, так? А остальные С2\С1 просто неинтересны...
2. Как тогда вы предлагаете формировать главные классы? Первая диагональ фиксирована, вторая выбирается из списка выше и все (остальные элементы не заполняем)? Или все же заполняем всеми возможными способами и получаем разные КФы без дублей? Подозреваю, что последний вариант, но хочу уточнить...

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline whitefox  
#294 Оставлено : 26 апреля 2017 г. 19:45:53(UTC)
whitefox


Статус: Интересующийся

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

Сказал(а) «Спасибо»: 25 раз
Поблагодарили: 79 раз в 48 постах
Автор: evatutin Перейти к цитате

1. В таком случае получается, что сильно нормализованные ДЛК С1 — это подмножество в составе соответствующего главного класса ДЛК С2, так? А остальные С2\С1 просто неинтересны...
Да, это так. Точно так же как и нормализованные ДЛК составляют собственное подмножество в составе главного класса (ведь их не более 15360 в то время как главный класс может содержать до 55738368000 ДЛК). И так как мы интересуемся только инвариантами главного класса, то нам действительно не интересны никакие конкретные ДЛК кроме одного единственного — представителя этого класса, так как все члены главного класса обладают одними и теми же инвариантами.

Автор: evatutin Перейти к цитате

2. Как тогда вы предлагаете формировать главные классы? Первая диагональ фиксирована, вторая выбирается из списка выше и все (остальные элементы не заполняем)? Или все же заполняем всеми возможными способами и получаем разные КФы без дублей? Подозреваю, что последний вариант, но хочу уточнить...
Именно последний вариант, каждый из 67 вариантов побочной диагонали даст свою линейку ДЛК при всевозможных заполнениях остальных 80 ячеек. Ровно для 9 линеек все полученные таким образом сильно нормализованные ДЛК окажутся КФ, 28 линеек потребуют выполнить только одну проверку на минимальность для определения КФ, 21 линейка — 3 проверки ... Полный список следующий:
Код:

count[0] = 9
count[1] = 28
count[3] = 21
count[9] = 1
count[15] = 2
count[19] = 2
count[47] = 4
В квадратных скобках необходимое число проверок для нахождения КФ, во второй колонке — число линеек требующих данного числа проверок для определения КФ.
thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 27.04.2017(UTC)
Offline whitefox  
#295 Оставлено : 27 апреля 2017 г. 9:30:36(UTC)
whitefox


Статус: Интересующийся

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

Сказал(а) «Спасибо»: 25 раз
Поблагодарили: 79 раз в 48 постах
Итак, алгоритм канонизации ДЛК. smile

Пусть у нас имеется нормализованный ДЛК L (в этом посте под нормализацией снова понимается нормализация главной диагонали) с побочной диагональю d. Первое, что нужно сделать — привести L к сильно нормализованному виду. Для этого используется заранее составленная таблица T в которой каждому из 440192 двухсторонних беспорядков поставлен в соответствие изоморфизм приводящий соответствующий нормализованный ДЛК к сильно нормализованному виду (после последующей нормализации). В представленной программе эта таблица загружается из файла hash_tabl.bin. То есть по значению d мы извлекаем из таблицы T изоморфизм I = T[d] который применяем к ДЛК L, результирующий ДЛК I(L) нормализуем. Полученный ДЛК будет сильно нормализован.

Пусть теперь L означает сильно нормализованный ДЛК с побочной диагональю d. И нам нужно найти все сильно нормализованные ДЛК изоморфные L. Алгоритм для d из первой части списка 67 канонических диагоналей
немного отличается от алгоритма для d из второй части списка. Это связано, с упомянутым вчера, вырождением четвёрок в пары. Фактически, для первых 56 канонических диагоналей нам нужно помимо ДЛК L рассмотреть ещё и ДЛК L', получающийся из L вертикальной симметрией с последующей сильной нормализацией. Для последнего можно снова воспользоваться таблицей T, но проще составить отдельную таблицу T1 так как она имеет только 56 входов:
Эти М-перестановки определяют соответствующие М-преобразования. Для получения ДЛК L' нужно выполнить над ДЛК L вертикальную симметрию, затем соответствующее М-преобразование и, в завершение, нормализацию. У полученного ДЛК L' побочная диагональ тоже будет равна d как и у ДЛК L.

Оставшаяся часть алгоритма одинакова для обеих частей списка канонических диагоналей, за тем исключением, что для первых 56 одновременно обрабатываются ДЛК L и L', а для последних 11 — только один ДЛК L.

Мы снова вернулись к задаче перечисления сильно нормализованных ДЛК изоморфных данному сильно нормализованному ДЛК L с побочной диагональю d. Для этого выполним над ДЛК L все возможные М-преобразования (с последующей нормализацией), сохраняющие побочную диагональ.
Соответствующие подгруппы М-перестановок для каждой из 67 канонических диагоналей под спойлером:
Каждой подгруппе М-перестановок предшествует заголовок, напрмер, count[67(125)] = 2. Который означает, что для 67-й канонической диагонали (которая является представителем 125-го класса сопряжения двухсторонних беспорядков по М-группе) порядок соответствующей подгруппы М-перестановок равен 2.

Для первых 56 линеек ДЛК (каждой канонической диагонали соответствует своя линейка ДЛК) общее число число сильно нормализованных ДЛК не превышает удвоенного порядка соответствующей подгруппы М-перестановок), а для последних 11 линеек — не превышает порядка соответствующей подгруппы.

Осталось только выбрать среди найденных сильно нормализованных ДЛК наименьший в лексикографическом порядке. Для чего потребуется не более 47 сравнений в худшем случае.

That's all, folks. smile

Отредактировано пользователем 27 апреля 2017 г. 9:58:13(UTC)  | Причина: Не указана

thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 27.04.2017(UTC)
Offline evatutin  
#296 Оставлено : 27 апреля 2017 г. 14:25:26(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 920 раз
Поблагодарили: 1486 раз в 727 постах
whitefox
А вы не пробовали считать число главных классов (я так понимаю, оно же число различных КФов) для ДЛК малых N? Я на своей программной реализации (через M-преобразования + симметричное отражение + транспонирование + нормализация + куча алгоритмических оптимизаций) посчитал для N от 1 до 7, получилась вот такая последовательность:

1, 0, 0, 1, 2, 2, 972

Для N=8 у меня сейчас считается, по моим прикидкам на полный подсчет надо около 40 часов, через пару дней дам соответствующее значение... Если хотите, можете меня проверить/дополнить своим подходом через диагонали 199.
Для N=9 по моим прикидкам надо где-то около 250 лет счета в 1 поток, что можно где-то за год на гриде пройти...

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
thanks 1 пользователь поблагодарил evatutin за этот пост.
whitefox оставлено 27.04.2017(UTC)
Offline whitefox  
#297 Оставлено : 27 апреля 2017 г. 17:25:59(UTC)
whitefox


Статус: Интересующийся

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

Сказал(а) «Спасибо»: 25 раз
Поблагодарили: 79 раз в 48 постах
Автор: evatutin Перейти к цитате

А вы не пробовали считать число главных классов (я так понимаю, оно же число различных КФов) для ДЛК малых N?
Увы, нет. Всегда, почему-то, находятся более приоритетные задачи. sad

Автор: evatutin Перейти к цитате
Я на своей программной реализации (через M-преобразования + симметричное отражение + транспонирование + нормализация + куча алгоритмических оптимизаций) посчитал для N от 1 до 7, получилась вот такая последовательность:

1, 0, 0, 1, 2, 2, 972

Для N=8 у меня сейчас считается, по моим прикидкам на полный подсчет надо около 40 часов, через пару дней дам соответствующее значение... Если хотите, можете меня проверить/дополнить своим подходом через диагонали 199.
Для N=9 по моим прикидкам надо где-то около 250 лет счета в 1 поток, что можно где-то за год на гриде пройти...
Весьма любопытно. smile

Offline evatutin  
#298 Оставлено : 27 апреля 2017 г. 18:05:28(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 920 раз
Поблагодарили: 1486 раз в 727 постах
Я посмотрел ваши списки (спасибо за них!), среди них находится 1227 браунов (браун в моем понятии — горизонтально-симметричный строчно-инверсный или вертикально-симметричный столбце-инверсный). Судя по тому, что число нечетное, скорее всего это не все КФ браунов Не получается.

[upd]
А может быть и все... Пробежался по списку citerra'ы, у него столько же 199

[upd2]
Для всех браунов мощности классов изоморфизма строго 7680, общее число нормализованных браунов получается 9423360

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


kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline whitefox  
#299 Оставлено : 27 апреля 2017 г. 19:46:16(UTC)
whitefox


Статус: Интересующийся

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

Сказал(а) «Спасибо»: 25 раз
Поблагодарили: 79 раз в 48 постах
Автор: evatutin Перейти к цитате
браун в моем понятии — горизонтально-симметричный строчно-инверсный или вертикально-симметричный столбце-инверсный
Из этого определения следует, что всякий браун является блочным ДЛК вида 5х5. Таких блочных ДЛК имеется два семейства и оба проверены полностью. Так что все марьяжные брауны (ОДЛК) находятся среди 1715 главных классов марьяжных ДЛК первого семейства.
Offline evatutin  
#300 Оставлено : 29 апреля 2017 г. 13:11:50(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 920 раз
Поблагодарили: 1486 раз в 727 постах
Я посчитал число главных классов для N=8, на это потребовалось 28,5 ч в 1 поток, искомое число составляет 4 873 096. Если у кого-то будет желание, меня можно проверить 199. А соответствующая целочисленная последовательность принимает вид

1, 0, 0, 1, 2, 2, 972, 4873096

PS. При N=7 начинается комбинаторный взрыв smile

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
thanks 1 пользователь поблагодарил evatutin за этот пост.
whitefox оставлено 30.04.2017(UTC)
Пользователи, просматривающие эту тему
Guest
19 Страницы«<1314151617>»
Быстрый переход  
Вы не можете создавать новые темы в этом форуме.
Вы не можете отвечать в этом форуме.
Вы не можете удалять Ваши сообщения в этом форуме.
Вы не можете редактировать Ваши сообщения в этом форуме.
Вы не можете создавать опросы в этом форуме.
Вы не можете голосовать в этом форуме.

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