Форум

Уважаемые посетители. В связи с массовой регистрацией на форуме спамовых и рекламных аккаунтов нам пришлось установить некоторые защитные программные блоки. Если при регистрации на Ваш почтовый адрес не придет письмо с паролем для активации учетной записи, прошу написать на адрес tpp12@rambler.ru или boinc.ru@yandex.ru. Я активирую учетку в ручную и вышлю Вам временный пароль.
Пожалуйста or Регистрация для создания сообщений и тем.

Проект Gerasim@Home

По результатам расчетов в на моей машине и в проекте в OEIS в настоящее время добавлены 4 ряда, связанные со спектрами числовых характеристик ДЛК. Описание рядов было дополнено графическими изображениями спектров и подтверждающими списками (последние на данный момент выложены для размерностей, для которых их формирование завершено).

* https://oeis.org/A344105 — число трансверсалей в ДЛК;
* https://oeis.org/A345370 — число диагональных трансверсалей в ДЛК;
* https://oeis.org/A345760 — число интеркалятов в ДЛК;
* https://oeis.org/A345761 — число ОДЛК для ДЛК.

Array

В ходе расширения спектров числовых характеристик ДЛК порядка 11 найден квадрат

0 1 2 3 4 5 6 7 8 9 10
1 2 3 0 5 7 10 8 9 4 6
10 8 9 4 6 2 7 0 5 1 3
7 0 5 10 3 8 4 6 1 2 9
8 5 1 6 7 9 0 10 2 3 4
6 7 8 9 10 1 3 4 0 5 2
9 10 6 7 8 4 5 2 3 0 1
4 6 0 2 9 10 1 3 7 8 5
5 3 7 8 1 6 2 9 4 10 0
2 9 4 5 0 3 8 1 10 6 7
3 4 10 1 2 0 9 5 6 7 8
у которого 199 диагональных трансверсалей, что позволяет усилить известное верхнее ограничение в ряду https://oeis.org/A287647 с a(11)<=279 до a(11)<=199. Расширение спектров продолжается...
Array
hoarfrost и citerra отреагировали на эту запись.
hoarfrostciterra

Не так давно нами был обсчитан интересный ДЛК порядка 12

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

(впервые найден 18.08.2021 на моей машине в ходе диагонализации предыдущего рекордмена по числу диагональных трансверсалей) на предмет числа ОДЛК у него, в результате чего была получена цифра в 3855938736 ОДЛК (24.10.2021). Цифра вызвала сомнение, т.к. во время расчета были многочисленные аппаратные сбои на сервере. Конкретно, во время расчета WU'шек, соответствующих 1421 трансверсали, было видно, что некоторые результаты битые (ошибка типа SEU), трансверсаль была запущена на перерасчет, в ходе которого было выяснено что старое значение (1802828 ОДЛК) и новое значение (1847414 ОДЛК) для нее не совпадают, т.е. часть сбойных результатов все-таки имела место быть (27.10.2021). Новое значение получилось больше старого на 1847414-1802828=44586 ОДЛК, запомним этот факт... С учетом того, что битые результаты были обнаружены при обработке 1421 трансверсали, никто не гарантировал, что их не могло появиться в составе других трансверсалей, поэтому квадрат в настоящее время отправлен на обработку повторно. Какая из цифр (3855938736 ОДЛК или 3855938736+44586=3855983322 ОДЛК) является верной мы бы не узнали до окончания повторной обработки, если бы не доброволец с ником Mynx (спасибо ему!), который взял найденный нами квадрат и повторил процесс в одиночку с использованием программ поиска ОДЛК на базе кода, выложенного в свободный доступ довольно давно whitefox'ом. И получил Mynx значение 3855983322 ОДЛК (11.11.2021), что в точности совпадает с нашим после корректировки и пересчета части WU'шек битой трансверсали! Соответственно на данный момент времени можно сделать вывод о том, что с большой долей вероятности значение 3855983322 ОДЛК для рекордного на данный момент ДЛК порядка 12 является верным. Окончательную точку в этом вопросе должен поставить текущий расчет, выполняемый в подпроекте GT CL проекта в настоящее время.

Array

На моей машине завершено расширение спектра трансверсалей для ДЛК порядка 11 с использованием хождения по окрестностям путем поворота 1 интеркалята. На это потребовалось 158 часов расчетов в 1 поток на Core i7 4770 (знал бы, что будет так долго, запустил бы в проекте, код для этого уже готов и был апробирован ранее для выполнения аналогичной задачи для порядка 12). В итоге получилось вот что:

Параметры спектра трансверсалей до: Min value = 2477, max value = 37851, width = 35375, cardinality = 3261
Параметры спектра трансверсалей после: Min value = 2091 (!!!), max value = 37851, width = 35761 (!!!), cardinality = 3561 (!!!)

Знаками "!!!" отмечены изменившиеся значения. Таким образом, верхнее ограничение на нижнюю границу числа трансверсалей усилено с a(11)<=2477 до a(11)<=2091 (ряд A287645), соответствующий квадрат ниже:

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

Также изменились ширина и мощность спектра числа трансверсалей в ДЛК, которая теперь составляет 3561 элемент, что позволяет усилить еще одно ограничение в ряду https://oeis.org/A344105: с a(11)>=1158 до a(11)>=3561.

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

Array

 

А так есть ли полная гарантия, что в других подпроектах нет битых результатов (когда месяц назад были сбои на сервере)?

 

 

Array
По итогам нашего Распознавания опубликован сборник трудов, в котором есть тезисы 3 докладов с моим участием

Гвоздева С.Н., Ватутин Э.И. Оценка вероятности досрочного прерывания процесса умножения бинарных матриц от их размера и плотности // Оптико-электронные приборы и устройства в системах распознавания образов и обработки изображений (Распознавание — 2021). Курск, 2021. С. 87–90. http://evatutin.narod.ru/evatutin_matmul_bin_prob.pdf 

 

Ватутин Э.И. О подсчете главных классов циклических диагональных и пандиагональных латинских квадратов // Оптико-электронные приборы и устройства в системах распознавания образов и обработки изображений (Распознавание — 2021). Курск, 2021. С. 77–79. http://evatutin.narod.ru/evatutin_ls_cyclic_main_classes.pdf

 

Пшеничных А.О., Ватутин Э.И. О влиянии стохастического начального заполнения матрицы феромона на качество оценки хроматического числа графа для метода муравьиной колонии // Оптико-электронные приборы и устройства в системах распознавания образов и обработки изображений (Распознавание — 2021). Курск, 2021. С. 206–208. http://evatutin.narod.ru/evatutin_cl_ac_start_tau.pdf

В первой публикации приведены результаты досрочного прерывания процесса умножения бинарных матриц, анализ которых позволяет сделать вывод о целесообразности данного прерывания, т.к. число умножений при его использовании сокращается на несколько порядков. Во второй публикации приведены числовые ряды, соответствующие подсчету главных классов циклических и пандиагональных ЛК/ДЛК, а также краткое описание соответствующих вычислительных экспериментов. Ну а третья публикация адресована на проверку одного интересного эффекта, связанного с притяжением решений в один из бассейнов одного из локальных минимумов целевой функции в задаче раскраски графов с использованием эвристических методов (в данной задаче, как выяснилось, такой эффект отсутствует, в задачах формирования случайных ДЛК эффект ранее наблюдался).
Array
Цитата: Yura12 от 12.11.2021, 22:06

А так есть ли полная гарантия, что в других подпроектах нет битых результатов (когда месяц назад были сбои на сервере)?

 

Полных гарантий никто не даст, но анализ результатов, который я провожу практически каждый день, ничего криминального не выявил. Получаемые квадраты и спектры проходят проверку корректности при постобработке, ошибок в их составе нет и никогда не было замечено до этого. Скажу больше, у меня есть сильное подозрение, что и среди ОДЛК для тяжелого квадрата ошибок тоже не будет за пределами полученной битой 1421-й трансверсали. Однако точно в этом мы убедимся, когда досчитаем текущую партию WU'шек подпроекта GT CL. Ошибки битой памяти на удивление легли очень компактно в небольшую партию заданий, которой видимо "повезло" обрабатываться как раз в этот момент. Я очень боялся за то, что подобные ошибки теоретически могли вообще нарушить целостность связей в БД, т.к. они то могут проявиться в любой таблице БД, не только в результатах, но видимо нам повезло и этого не произошло. Либо помог откат на backup, если таковые ошибки и появились. Т.е. ситуация с ошибками больше не повторяется, и последствия от той серии сбоев сильно меньше, чем могли бы быть.

Array
Yura12 и AenBleidd отреагировали на эту запись.
Yura12AenBleidd

Завтра, а точнее уже сегодня, на базе Тульского государственного университета стартует конференция Интеллектуальные и информационные системы (Интеллект 2021), на которой запланирован пленарный доклад

Ватутин Э.И., Никитина Н.Н., Манзюк М.О., Альбертьян А.М., Курочкин И.И. О построении спектров быстровычислимых числовых характеристик диагональных латинских квадратов малого порядка

представлять который буду я. В докладе будет приведено краткое обобщение того, что было сделано за последние несколько месяцев в плане построения спектров числа трансверсалей, диагональных трансверсалей, интеркалятов и ОДЛК для ДЛК порядков 1—8 и аналогичных спектров для ОДЛК порядков 1—9 (все значения точные, получены полным перебором). Кроме того, планируется коротко обозначить перспективы аппроксимации аналогичных спектров для ДЛК бОльших порядков (соответствующие вычислительные эксперименты частично выполнены, частично выполняются в настоящий момент и частично еще будут выполняться в проектах Gerasim@Home и RakeSearch). Здесь пространство перебора уже слишком велико для исчерпывающего поиска, что однако открывает границы для использования эвристических методов с учетом специфики текущей квадратной задачи 🙂 и знаний, полученных ранее при апробации аналогичных эвристик в задачах поиска кратчайших путей и квазиоптимальных раскрасок в графах (мы когда-то давно выполняли соответствующие эксперименты в проекте Gerasim@home). С презентацией доклада можно ознакомиться тут:

http://evatutin.narod.ru/evatutin_spectra_t_dt_i_o_small_orders.pdf

Если кто-то очень захочет послушать, в личку за ссылкой на подключение.

Загруженные файлы:
  • Вам нужно войти, чтобы просматривать прикрепленные файлы..
Array

В проекте завершен эксперимент по расширению спектра трансверсалей в ДЛК порядка 12 путем анализа окрестностей, получаемых вращением 1 интеркалята от уже известных элементов спектра. В результате получен спектр из 22407 значений, который данным преобразованием уже не расширяется, однако скорее всего может быть слегка расширен другими преобразованиями в перспективе. На данный момент это позволяет заключить, что в ряду https://oeis.org/A344105 a(12) >= 22407 (до этого наиболее сильным было нижнее ограничение a(12) >= 22398, в настоящее время присутствующее в описании ряда в OEIS).

Array
Pavel Kirpichenko отреагировал на эту запись.
Pavel Kirpichenko

Результаты поиска КФ ОДЛК порядка 10 в проекте Gerasim@Home за месяц.

За месяц найдено 107 336 КФ ОДЛК порядка 10 (большую часть времени поиск был приостановлен для того, чтобы быстрее были посчитаны результаты для других экспериментов). Среди наиболее интересных находок:

ONCE (A):1 - 139848, where:
1 CFs - 33160
2 CFs - 106688

LINE3 (B):1 - 99351, where:
2 CFs - 18735
3 CFs - 80616 (+400)

LINE3 (B):2 - 59043, 2:1, where:
2 CFs - 18735
3 CFs - 40308 (+200)

LINE4 (C):1 - 172, where:
2 CFs - 4
4 CFs - 168

LINE4 (C):2 - 172, where:
2 CFs - 4
4 CFs - 168

LINE5 (D):1 - 17, where:
3 CFs - 17

LINE5 (D):2 - 34, where:
3 CFs - 34

LOOP4 (E):2 - 2280, where:
1 CFs - 2
2 CFs - 138
3 CFs - 1464
4 CFs - 676

1TO3 (F):1 - 453, where:
4 CFs - 453

1TO3 (F):3 - 151, where:
4 CFs - 151

1TO4 (G):1 - 1362, where:
3 CFs - 882
5 CFs - 480

1TO4 (G):4 - 561, where:
3 CFs - 441
5 CFs - 120

1TO5 (k):1 - 10, where:
6 CFs - 10

1TO5 (k):5 - 2, where:
6 CFs - 2

1TO6 (H):1 - 42, where:
4 CFs - 24
7 CFs - 18

1TO6 (H):6 - 11, where:
4 CFs - 8
7 CFs - 3

1TO7 (h):1 - 7, where:
8 CFs - 7

1TO7 (h):7 - 1, where:
8 CFs - 1

1TO8 (I):1 - 48, where:
5 CFs - 32
9 CFs - 16

1TO8 (I):8 - 10, where:
5 CFs - 8
9 CFs - 2

RHOMBUS3 (J):2 - 9, where:
5 CFs - 9

RHOMBUS3 (J):3 - 6, where:
5 CFs - 6

RHOMBUS4 (K):2 - 73, where:
3 CFs - 2
4 CFs - 23
5 CFs - 32
6 CFs - 16

RHOMBUS4 (K):4 - 34, where:
3 CFs - 1
4 CFs - 17
5 CFs - 8
6 CFs - 8

FISH (N):1 - 7, where:
4 CFs - 1
6 CFs - 6

FISH (N):2 - 11, where:
4 CFs - 2
6 CFs - 9

FISH (N):4 - 4, where:
4 CFs - 1
6 CFs - 3

TREE1 (V):1 - 2, where:
4 CFs - 2

TREE1 (V):2 - 1, where:
4 CFs - 1

TREE1 (V):3 - 1, where:
4 CFs - 1

CROSS (X):1 - 16, where:
6 CFs - 16

CROSS (X):2 - 4, where:
6 CFs - 4

CROSS (X):4 - 4, where:
6 CFs - 4

DAEDALUS10 (i):1 - 6, where:
12 CFs - 6

DAEDALUS10 (i):2 - 4, where:
12 CFs - 4

DAEDALUS10 (i):4 - 1, where:
12 CFs - 1

DAEDALUS10 (i):10 - 1, where:
12 CFs - 1

FLYER (j):1 - 2, where:
8 CFs - 2

FLYER (j):2 - 3, where:
8 CFs - 3

FLYER (j):4 - 3, where:
8 CFs - 3

VENUS (l):1 - 1, where:
5 CFs - 1

VENUS (l):2 - 3, where:
5 CFs - 3

VENUS (l):4 - 1, where:
5 CFs - 1

DAEDALUS8 (m):1 - 2, where:
6 CFs - 2

DAEDALUS8 (m):2 - 2, where:
6 CFs - 2

DAEDALUS8 (m):4 - 1, where:
6 CFs - 1

DAEDALUS8 (m):8 - 1, where:
6 CFs - 1

RHOMBUS5 (n):2 - 4, where:
5 CFs - 4

RHOMBUS5 (n):5 - 1, where:
5 CFs - 1

1TO10 (o):1 - 5, where:
6 CFs - 5

1TO10 (o):10 - 1, where:
6 CFs - 1

ROBOT (p):1 - 4, where:
5 CFs - 4

ROBOT (p):2 - 4, where:
5 CFs - 4

ROBOT (p):4 - 2, where:
5 CFs - 2

STINGRAY (q):1 - 1, where:
5 CFs - 1

STINGRAY (q):2 - 3, where:
5 CFs - 3

STINGRAY (q):3 - 1, where:
5 CFs - 1

Эксперимент по исследованию свойств окрестностей обобщенных симметрий:
* парастрофический срез 1 [Px Py Pv]: обработка завершена;
* парастрофический срез 3 [Py Px Pv]: пройдено 1170 (+48) окрестностей из 1764 (66,3%, +2,7%).

Спектры числовых характеристик ДЛК порядка 9:
* трансверсали: ширина спектра — 2241-68+1 = 2174, мощность спектра — 359, спектр близок к максимальному;
* диагональные трансверсали: ширина спектра — 333-0+1=334, мощность спектра — 176, запланирован эксперимент по расширению данного спектра;
* интеркаляты: ширина спектра — 72-0+1 = 73, мощность спектра — 62, спектр близок к максимальному;
* ОДЛК: ширина спектра — 614-0+1 = 615, мощность спектра — 99.

Спектры числовых характеристик ДЛК порядка 10:
* трансверсали: ширина спектра — 5504-144+1 = 5361, мощность спектра — 442, спектр близок к максимальному;
* диагональные трансверсали: ширина спектра — 890-3+1=888, мощность спектра — 736, спектр близок к максимальному;
* интеркаляты: ширина спектра — 93-0+1 = 94, мощность спектра — 88, спектр близок к максимальному;
* ОДЛК: ширина спектра — 10-0+1 = 11, мощность спектра — 10, спектр близок к максимальному.

Спектры числовых характеристик ДЛК порядка 11:
* трансверсали: ширина спектра — 37851-2091 = 35761, мощность спектра — 1158, запланирован эксперимент по расширению данного спектра;
* диагональные трансверсали: ширина спектра — 4828-199+1=4630, мощность спектра — 353, запланирован эксперимент по расширению данного спектра;
* интеркаляты: ширина спектра — 94-0+1 = 95, мощность спектра — 100, спектр близок к максимальному;
* ОДЛК: ширина спектра — 32462-0+1 = 32463, мощность спектра — 36.

Спектры числовых характеристик ДЛК порядка 12:
* трансверсали: ширина спектра — 198144-1312+1 = 196833, мощность спектра — 22401 -> 22407 (+6) значений, запланирован эксперимент по расширению данного спектра;
* диагональные трансверсали: ширина спектра — 30192-50+1 = 30143, мощность спектра — 17620 -> 17641 значений, спектр близок к максимальному;
* интеркаляты: ширина спектра — 252-0+1 = 253, мощность спектра — 210, спектр не изменился за месяц и близок к максимальному;
* ОДЛК: ширина спектра — 3855983322-0+1 = 3855983323, мощность спектра — 2501 -> 2782 (+288) значений, расширение спектра в настоящее время выполняется на моей машине в несколько потоков.

Откорректирован рекорд (3855938736 -> 3855983322) на максимальное число ОДЛК для ДЛК порядка 12. Во время соответствующего вычислительного эксперимента на сервере проекта был ряд сбоев, полученное предыдущее значение не вызывало большого доверия, в ходе пересчета ОДЛК для 1421-й трансверсали число ОДЛК было откорректировано следующим образом: 3855938736-1802828+1847414=3855983322. Новое значение подтверждено группой добровольцев (CoolAtchOk, Mynx, etc.) и скорее всего является верным, точку в этом вопросе должен поставить текущий расчет, выполняемый в проекте.

Загруженные файлы:
  • Вам нужно войти, чтобы просматривать прикрепленные файлы..
Array