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

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

Уведомление

Icon
Error

37 Страницы«<353637
Опции
К последнему сообщению К первому непрочитанному
Offline whitefox  
#721 Оставлено : 22 сентября 2018 г. 13:26:34(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 71 раз
Поблагодарили: 177 раз в 111 постах
Итак, нашу исходную задачу мы разделили на две подзадачи:

1) для данного x in {2,4,8,16} перечислить всех канонические супершаблоны, определяющие семейства ЛК с симметрий (x,31,31);
2) для данного канонического супершаблона, определяющего семейство ЛК, перечислить все ЛК, принадлежащие этому семейству.

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

Строки супершаблона относятся к одному из трёх типов, которые обозначим: 0, 1, 2. Строки супершаблона, которым соответствуют вертикально симметричные строки БС, отнесём к типу 2.

Остальные строки объединим в пары: i'ую строку с (9-i)'ой, например, для супершаблона:

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


получим три пары:

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

2 0 1 0 1
3 4 3 4 2

1 0 0 2 3
4 2 1 3 4


Для каждой пары подсчитаем число различных столбцов. В приведённом примере, первые две пары строк имеют по четыре различных столбца, а третья пара — пять. Пару строк с четырьмя различными столбцами отнесём к типу 0, а пару строк с пятью различными столбцами — к типу 1.

Очевидно, что распределение строк супершаблона по типам является инвариантом класса эквивалентности супершаблонов. Другими словами, паттерн супершаблона не изменяется при эквивалентных преобразованиях. Паттерн супершаблона будем обозначать по числу пар строк типа 1. Так, например, для симметрии (2,31,31) возможны два паттерна:

— одна пара строк типа 0 и восемь строк типа 2;
— одна пара строк типа 1 и восемь строк типа 2.

Раньше эти паттерны были обозначены как 44323 и 43423 соответственно, теперь обозначим их как 0 и 1. Для симметрии (4,31,31) имеется три паттерна — 0, 1 и 2, которые раньше были обозначены как 44323, 44323+ и 43423 соответственно.

Пусть k обозначает число пар центрально симметричных строк БС. Для нормализованного супершаблона примем чтобы первые k строк были упорядочены по неубыванию типа строк. Например, для симметрии (8,31,31) нормализованный супершаблон должен иметь следующие распределения строк по типа в зависимости от паттерна:

Код:
0    0    0    1
0    0    1    1
0    1    1    1
2    2    2    2
2    2    2    2
2    2    2    2
2    2    2    2
0    1    1    1
0    0    1    1
0    0    0    1


для паттернов 0, 1, 2 и 3 соответствено.

Можно показать, что пара строк (i,9-i) типа 0 эквивалентными преобразованиями приводится к виду:

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


А пара строк типа 1 — к виду:

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

Для нормализованного супершаблона примем, чтобы его первая и последняя строки имели указанный вид. Например, супершаблон:

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

приводится к эквивалентному супершаблону:

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

Первый элемент строки типа 2 назовём определителем (так как он будет определять порядок этой строки среди однотипных ей). Для пары строк типа 0 и типа 1 определителем назовём упорядоченную пару первых элементов строк (i,9-i), i < k. Например, приведёный выше супершаблон имеет следующие определители строк:

— для типа 0: (0,4), (0,3);
— для типа 1: (1,4);
— для типа 2: 1, 2, 2, 3.

В нормализованном супершаблоне пара из первой и последней строк всегда имеет определитель (0,4), но их порядок фиксирован вне зависимости от определителя. Для нормализованного супершаблона примем, чтобы свободные однотипные строки (пары строк для типов 0 и 1) следовали в порядке неубывания из определителей.

Приведённый выше супершаблон отвечает всем трём условиям нормализованного супершаблона.

Теперь первую подзадачу решаем так:

1) перечисляем нормализованные супершаблоны;
2) каждый найденный супершаблон проверяем на каноничность, если нет, то продолжаем перечисление;
3) находим двойственный супершаблон и канонизируем его;
4) сравниваем найденный супершаблон с КФ двойственного ему супершаблона, если больше, то продолжаем перечисление;
5) проверяем соответствует ли найденному супершаблону какой-нибудь суперкласс, если нет, то продолжаем перечисление /*такое теоретически возможно, так как отображение множества суперклассов в множество супершаблонов не обязано быть биекцией, а только инъекцией, хотя, для симметрий (2,31,31) и (4,31,31) оно суть биекция*/;
6) сохраняем найденный супершаблон и продолжаем перечисление.

Замечание по пункту 5). Этот пункт включён только для точного соответствия задачи, решаемой этим алгоритмом, формулировке первой подзадачи. Фактически в нём нет необходимости, так как алгоритм, решающий вторую подзадачу, снова выполнит эту работу вне зависимости от выполнения её алгоритмом первой подзадачи.

Продолжение следует.
Offline whitefox  
#722 Оставлено : 24 сентября 2018 г. 12:19:29(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 71 раз
Поблагодарили: 177 раз в 111 постах
Для каждого x in {2,4,8,16} вторую подзадачу решает следующий алгоритм:

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

Замечание по пункту 1). Уточнение "определяющего семейство ЛК с симметрией (x,31,31)" включено только для точного соответствия формулировке второй подзадачи. Фактически, этот алгоритм применим к любому каноническому супершаблону, и если на первом шаге ни одного канонического шаблона БС найдено не будет, то это означает, что данному каноническому супершаблону никакой суперкласс не соответствует, и алгоритм второй подзадачи на этом завершается, выполняя тем самым работу предусмотренную пунктом 5) алгоритма первой подзадачи.

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

Для стандартных представлений симметрий (x,31,31), x in {2,4,8,16}, условия 1 и 2 выполнены, а в третьем условие достаточно проверить только согласованность замкнутых цепочек циклов позиций (согласованность замкнутых цепочек в совокупности проверять не нужно, так как компонента связности может иметь не более одной замкнутой цепочки).

Как искать замкнутые цепочки покажу на примере рассматривавшегося ранее шаблона БС с симметрией (2,31,31):

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


Заменим точками элементы всех строк типа 2, получим:

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

В каждом столбце заменим непарные элементы точками:

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


В каждой строке i заменим точками элементы, не имеющие пары в этой строке или в строке (9-i):

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

Оставшиеся элементы соединим рёбрами так:

1) соединим ребром два одинаковых элемента одного столбца;
2) соединим ребром два одинаковых элемента одной строки;
3) соединим ребром два одинаковых элемента строк i и (9-i).

Согласованность замкнутой цепочки проверяем так:

1) ребру соединяющему элементы одной строки присвоим вес 1;
2) ребру соединяющему элементы строк i и (9 - i) присвоим вес 1;
3) ребру соединяющему элементы из одной половины столбца (верхней либо нижней) присвоим вес 1;
4) ребру соединяющему элементы из разных половин столбца присвоим вес 0;
5) вес замкнутой цепочки определим как сумму весов входящих в неё рёбер;
6) замкнутая цепочка будет согласованной тогда и только тогда, когда её вес сравним с нулём по модулю два.

В нашем примере имеется три согласованные замкнутые цепочки.

Теперь очевидно как найти все согласованные шаблоны отвечающие данному супершаблону.

Продолжение следует.
thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 24.09.2018(UTC)
Offline whitefox  
#723 Оставлено : 26 сентября 2018 г. 16:39:21(UTC)
whitefox


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

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

Сказал(а) «Спасибо»: 71 раз
Поблагодарили: 177 раз в 111 постах
Рассмотрим второй шаг алгоритма второй подзадачи. Его основой является нахождение всех блоков БС, по которым строится базовый ЛК, и, варьированием ориентаций которых, строятся все ЛК, обладающие данной БС.

С этой целью построим по данному шаблону БС вспомогательный граф G:

1) вершинами графа будем считать ячейки шаблона;
2) пару одинаковых ячеек соединим ребром если они принадлежат:
— одному столбцу;
— одной строке;
— строкам i и (9-i) для i < k, где k равно числу пар центрально симметричных строк БС.

Найдём компоненты связности графа G. Например для шаблона:

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


соответствующий вспомогательный граф имеет следующие компоненты связности:

Код:
тип 0
62,22,71,81,13,03,04,44
30,50

тип 1
40,20,72,82,84,64
31,91,93,53

тип 2
41,21,73,63
32,02,00,80,14,54

тип 3
60,10,12,42
51,01,94,74,23,33

тип 4
61,11,83,43
52,92,90,70,24,34


Здесь числа суть координаты ячеек шаблона. Каждая компонента связности графа G представляет один блок БС. Собственно блок получится если к координатам ячеек компоненты связности присовокупить симметричные им координаты ячеек БС (с подходящей симметрией).

В нашем примере БС, соответствующая данному шаблону, имеет следующие десять блоков:

Код:
тип 0
62,22,71,81,13,03,04,44,67,77,28,18,86,96,95,45
30,50,39,59

тип 1
40,20,72,82,84,64,49,79,27,17,15,65
31,91,93,53,38,08,06,56

тип 2
41,21,73,63,48,78,26,66
32,02,00,80,14,54,37,97,99,19,85,55

тип 3
60,10,12,42,69,89,87,47
51,01,94,74,23,33,58,98,85,25,76,36

тип 4
61,11,83,43,68,88,16,46
52,92,90,70,24,34,57,07,09,29,75,35


Третий шаг алгоритма второй подзадачи тривиален, а четвёртый очевиден.

Конец.
thanks 1 пользователь поблагодарил whitefox за этот пост.
citerra оставлено 27.09.2018(UTC)
Offline citerra  
#724 Оставлено : 3 октября 2018 г. 11:25:33(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 493 раз
Поблагодарили: 343 раз в 249 постах
Реплика к сообщению
Цитата:
I will answer again the question: "Why are there two projects with one task?"

We with Progger know well that the project server is weak. This is the personal Progger server.
Therefore, we sought support from the very beginning.
We contacted for help at the Moscow Computing Center. We were refused.
Then I turned to my colleague Stefano Tognon (ice00) for help.
He kindly agreed to launch a branch of the ODLK project on personal server.
This is how the ODLK1 project came about.
This project is included in the white list of the Gridcoin system.
The Gridcoin team works great in the project.
And not only this team, of course.

I hope that they will no ask a question about two projects again.
The question was discussed a lot and vigorously. But he is asked again and again.

Упускается главное в вопросе "Зачем второй проект, а не , например, два подпроекта в одном". Ведь два проекта для юзера неудобно. Участвуя в двух проекта, он проигрывает в статистике в обоих. Надо больше мощностей на стороне юзера. Но на пользователей похоже положили большой болт.
И вот не ладив работу существующих проектов, уже ищутся кандидаты еще на один проект, на котором будут крутиться "гениальные" эксперименты "ученой проекта".
[ Не решив проблему изоморфизма, все дополнительные мощности уйдут на избыточность. Короче, сила есть, ума не надо]
А факт остается фактом - в последние месяцы ( два - три ) новинок не наблюдается. Все якобы "новинки" уже найдены в Герасиме. Да и ПО используется, которое использовалось боинк проекте в Gerasim@Home.
thanks 2 пользователей поблагодарили citerra за этот пост.
SerVal оставлено 03.10.2018(UTC), evatutin оставлено 03.10.2018(UTC)
Offline evatutin  
#725 Оставлено : 3 октября 2018 г. 19:13:29(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 1020 раз
Поблагодарили: 1813 раз в 880 постах
Цитата:
We contacted for help at the Moscow Computing Center. We were refused.


Вот попросить бы ее еще причину указать, почему она была refused 199 . Как в целом и на многих ресурсах — здесь, MHP, OEIS — все вокруг плохие, мы хорошие

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline citerra  
#726 Оставлено : 3 октября 2018 г. 19:29:26(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 493 раз
Поблагодарили: 343 раз в 249 постах
У нее очередное, осенние, обострение. В который раз, как минимум в третий, они покинула проекты ODLKx. Вроде все на месте, ничего не удалила. Интересно, надолго, до конца года или раньше?
Offline Егор  
#727 Оставлено : 4 октября 2018 г. 6:11:38(UTC)
Егор


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

Группы: Member
Зарегистрирован: 15.01.2017(UTC)
Сообщений: 76
Мужчина
Российская Федерация
Откуда: Ялуторовск

Поблагодарили: 10 раз в 6 постах
Автор: citerra Перейти к цитате
У нее очередное, осенние, обострение. В который раз, как минимум в третий, они покинула проекты ODLKx. Вроде все на месте, ничего не удалила. Интересно, надолго, до конца года или раньше?


А она это кто? в чем суть? можно поподробнее...
Windows 10 64 bit | I5 3570 | HD 7870 | 16 GB RAM | HDD 320
Offline citerra  
#728 Оставлено : 4 октября 2018 г. 8:02:44(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 493 раз
Поблагодарили: 343 раз в 249 постах
Она - Макарова. Известная в интернете скандальная особа.
Занимается магическими квадратами. Возможно и были какие-то достижения, но так все свои достижения, даже примитивные она считает выдающими, то в этой куче трудно выделить что-то.
В последние годы занялась ортогональными диагональными квадратами. Но здесь возникла конкуренция, было с чем сравнить. И М. занервничала. Начала хамить, дерзить. Сначала её поперли с dxdy.ru Потом на нашем сайте нагрубила. Итог бан. Вершина эпопеи - бан на OEIS.org Решила учить как надо вести дела. Бан на год.
Сейчас обитает на форуме боинк проектов. Описывает свои исследования, которые для проектов посторонними. Но это нисколечки не волнует. Там достала администраторов ( Progger и ice00 )/
И вот очередной уход с проектов.
Теперь остался аккаунт на mathhelpplaneta. Но там ограниченные возможности - запрет на ведение блогов, ветка по квадратам закрыта. Как ситуации развернется - посмотрим.
Offline evatutin  
#729 Оставлено : 4 октября 2018 г. 10:44:07(UTC)
evatutin


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

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

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

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


В RakeSearch надо ее пригласить, там она еще кажется не успела отличиться 199

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline Horror245  
#730 Оставлено : 4 октября 2018 г. 11:36:03(UTC)
Horror245


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

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch!

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

Сказал «Спасибо»: 72 раз
Поблагодарили: 56 раз в 47 постах
И Hoarfrost начал штудировать книги по экзорцизму..
thanks 1 пользователь поблагодарил Horror245 за этот пост.
evatutin оставлено 04.10.2018(UTC)
Offline citerra  
#731 Оставлено : 18 октября 2018 г. 9:42:29(UTC)
citerra


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

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

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

Сказал(а) «Спасибо»: 493 раз
Поблагодарили: 343 раз в 249 постах
Автор: evatutin Перейти к цитате
В RakeSearch надо ее пригласить, там она еще кажется не успела отличиться 199
Характеристика модератора форума МНР
Цитата:
Как и ожидалось ваш налёт интеллигенции оказался весьма тонок, а под ним, как водится, базарная баба.
http://mathhelpplanet.com/viewtopic.php?p=347276#p347276
Offline Disel  
#732 Оставлено : 18 октября 2018 г. 16:07:42(UTC)
Disel


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

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

Группы: Member, Russia Team Group
Зарегистрирован: 08.07.2013(UTC)
Сообщений: 3,603
Мужчина
Российская Федерация

Сказал «Спасибо»: 519 раз
Поблагодарили: 427 раз в 327 постах
Да там не одна ветка с ее участием. Вот например.
Ubuntu Linux 18.04 LTS - 64 bit / Boinc 7.9.3(х64) / Core 2 DUO E6300 1.8 Ггц / GeForce GT-630
Пользователи, просматривающие эту тему
Guest
37 Страницы«<353637
Быстрый переход  
Вы не можете создавать новые темы в этом форуме.
Вы не можете отвечать в этом форуме.
Вы не можете удалять Ваши сообщения в этом форуме.
Вы не можете редактировать Ваши сообщения в этом форуме.
Вы не можете создавать опросы в этом форуме.
Вы не можете голосовать в этом форуме.

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