Новый конкурс программистов

[dimkadimon]

Nataly-Mak в сообщении #623514 писал(а):

Значит ли это, что 19 января 2013 г. стартует новый конкурс Al Zimmermann?

Похоже что да. Надо сообщить Нейлу. Если мы начнём 12 Октября, тогда мы должны закончить до 19 Января и друг другу не помешаем. Ещё будет Google AI Challenge примерно в это время. Будет интенсивное лето :)

[Nataly-Mak]

А разве Neil не в курсе? Я вроде цитату из его сообщения на форуме конкурса привела.

[whitefox]

dimkadimon в сообщении #623521 писал(а):

Будет интенсивное лето :)

Лето?
У антиподов всё с ног на голову поставлено.

[Nataly-Mak]

Al Zimmermann не только возвращает свои конкурсы программистов, но и поддерживает материально конкурсы Neil Brewer. Пожертвовал в фонд конкурса 240 долларов.
И Neil теперь приобретёт футболки для призов победителям конкурса.

alexBlack
покажете нам футболку?

[Nataly-Mak]

Nataly-Mak в сообщении #616079 писал(а):

Вот вторая базовая матрица для той же свёртки блоков, приведена whitefox:

1 1 1 1 1
1 6 3 4 5
1 3 5 2 6
1 2 6 5 4
1 5 4 6 3

-- Сб сен 08, 2012 08:30:30 --

А теперь будем строить блоки 6x6 по-другому.
Предлагаю такую свёртку блоков R+:

6 4 3 2 1 5
5 1 2 3 4 6
3 2 1 5 6 4
1 5 4 6 2 3
4 3 6 1 5 2
2 6 5 4 3 1

Существует ли для такой свёртки базовая матрица?
Я попробовала заполнить блоками, построенными по данной свёртке, базовую матрицу whitefox. Не получилась правильная раскраска.
Попробовала и базовую матрицу alexBlack заполнить такими блоками, тоже не получилась правильная раскраска.
Примечательный факт: в обеих раскрасках одинаковое количество ошибок - 294.
Следовательно, все базовые матрицы этой группы не годятся для новой свёртки.

Кстати, alexBlack, у меня был давно к вам вопрос, я его, кажется, уже озвучивала.
Но коллеги у меня, к сожалению, такие, что приходится задавать вопрос дважды, а то и трижды, чтобы получить ответ.
Итак, вопрос такой. Вы пишете в своей статье, что сделали полный перебор для С=6 и нашли всего 10 базовых матриц размером 5х5. Это был перебор только для блоков одного вида, построенных циклическим сдвигом?

Мне очень интересен этот вопрос. Хочу понять, что будет в случае, если строить блоки по-другому. В приведённой цитате я предложила свёртку блоков. По этой свёртке можно восстановить все 6 блоков 6х6. i-ый элемент в k-ой строке свёртки блоков определяет позицию цвета 1 в i-ой строке k-ого блока.
Существует ли базовая матрица для такого набора блоков и какого размера?

Pavlovsky приводил пример, когда для выбранного набора блоков максимальная базовая матрица найдена только 4х4.

[Pavlovsky]

Я уже писал что проверил все 22 неизоморфных ЛК 6х6 (относительно операций перестановки строк, колонок, символов). Только для трех из них можно построить матрицу 5х5.
Вот эти ЛК:

0,1,2,3,4,5,1,0,3,2,5,4,2,3,5,4,1,0,3,2,4,5,0,1,4,5,1,0,2,3,5,4,0,1,3,2
2,3,4,5,3,2,5,4,4,5,2,6,5,4,6,2

0,1,2,3,4,5,1,5,0,4,3,2,2,4,5,0,1,3,3,0,4,5,2,1,4,3,1,2,5,0,5,2,3,1,0,4
2,3,4,5,3,2,6,4,4,6,2,3,6,4,3,2

0,1,2,3,4,5,1,5,3,0,2,4,2,4,5,1,3,0,3,2,4,5,0,1,4,0,1,2,5,3,5,3,0,4,1,2
2,3,4,5,3,2,5,4,4,5,2,3,5,4,3,2

Первая строка ЛК, вторая строка матрица, в которой нет первой строки и колонки (по умолчанию они заполнены 1).

-- Чт сен 27, 2012 15:02:58 --

Так же проверил все неизоморфные ЛК 7х7 (564шт) и 8х8 (1676267шт). Забавно.
Для ЛК 7х7 есть только один ЛК для которого можно построить матрицу 7х7.
Для ЛК 8х8 есть только один ЛК для которого можно построить матрицу 8х8.

Естественно это ЛК изморфные таблице сложения для соответствующего поля.

Получилось экспериментальное подтверждение теоремы, что все конечные поля порядка n изоморфны.

[alexBlack]

Nataly-Mak в сообщении #623903 писал(а):

Итак, вопрос такой. Вы пишете в своей статье, что сделали полный перебор для С=6 и нашли всего 10 базовых матриц размером 5х5. Это был перебор только для блоков одного вида, построенных циклическим сдвигом?

Да.

(Оффтоп)

Nataly-Mak в сообщении #623903 писал(а):

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

Уж если Вы ссылаетесь на статью, то:

Цитата:

...Так вот, для C = 6 не существует матрицы CxC из рассматриваемых нами блоков...

[Nataly-Mak]

Цитата:

Так вот, для C = 6 не существует матрицы CxC из рассматриваемых нами блоков, зато существует 10 вариантов (C-1)x(C-1). Один из них

Да, это я читала. Но я просила уточнить. Может быть, вы проверяли и другие блоки.
А у вас, как я понимаю, ответ на любой вопрос на вес золота ценится. Тогда простите, больше я вам не буду задавать вопросов.
Спасибо за ответ. Увы, золота нет, чтобы заплатить.

-- Чт сен 27, 2012 15:05:18 --

Цитата:

Теперь простым перебором будем искать матрицу таких блоков проверяя правильность решения с учетом структуры выбранных блоков. Очень быстро такие матрицы находятся для C = 5 и C = 7:

alexBlack
Конечно, базовую матрицу для С=5,7 можно искать перебором.
Но здесь было бы неплохо отметить, что для простых С можно обойтись без всякого перебора, ибо для таких С существуют стандартные базовые матрицы (см. пример Pavlovsky для С=11). Стандартные матрицы для рассматриваемых вами блоков очень просто составляются по определённой схеме. Думаю, что это как-то связано с теми же конечными полями (с таблицами сложения и умножения в конечных полях).

Стандартная базовая матрица для С=5:

1 1 1 1 1
1 2 3 4 5
1 3 5 2 4
1 4 2 5 3
1 5 4 3 2

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

(Оффтоп)

Я понимаю, что в моей книге нет ничего конгениального. Однако... всё равно довольно странно, что ни один коллега по теме даже не заглянул в книгу ни одним глазом. Книгу на файлообменнике скачали 3 раза, при этом два раза - мои хорошие знакомые. Кто был третьим?

Кстати, dimkadimon, я выложила файл в формате pdf по вашей просьбе. Вы не забыли его скачать?
Этот файл не скачан ни разу!

[dimkadimon]

Nataly-Mak в сообщении #623941 писал(а):

Кстати, dimkadimon, я выложила файл в формате pdf по вашей просьбе. Вы не забыли его скачать?
Этот файл не скачан ни разу!

А где он? Можете сюда выложить?

[Nataly-Mak]

dimkadimon

Nataly-Mak в сообщении #623314 писал(а):

Файл (начало книги "Математическая раскраска") в формате pdf готов.
Выложила на файлообменник Народ.ру:
http://narod.ru/disk/61535093001.9b52a5 ... S.pdf.html

Сюда файл выложить не могу. Здесь, кажется, нет такой возможности (?) или я о ней не знаю.

-- Пт сен 28, 2012 07:30:51 --

Neil приобрёл призовые футболки и показал их здесь

Ещё он сообщил, что теперь перерыв между конкурсами на его сайте будет 4 месяца.
Я так понимаю: следующий конкурс с 12 октября пройдёт (по 12 января), потом будет перерыв 4 месяца.
В это время (с 19 января) будет проходить конкурс Al Zimmermann.

[whitefox]

Pavlovsky
Прошлый раз у вас были другие данные по второму третьему квадратам:

0,1,2,3,4,5,1,5,3,0,2,4,2,4,5,1,3,0,3,2,4,5,0,1,4,0,1,2,5,3,5,3,0,4,1,2
0,1,2,3,4,5,1,5,0,4,3,2,2,4,5,0,1,3,3,0,4,5,2,1,4,3,1,2,5,0,5,2,3,1,0,4
2,3,4,5,3,2,5,4,4,5,2,3,5,4,3,2
2,3,4,5,3,2,6,4,4,6,2,3,6,4,3,2

0,1,2,3,4,5,1,5,3,4,2,0,2,3,1,5,0,4,3,4,0,1,5,2,4,2,5,0,1,3,5,0,4,2,3,1
0,1,2,3,4,5,1,5,3,0,2,4,2,4,5,1,3,0,3,2,4,5,0,1,4,0,1,2,5,3,5,3,0,4,1,2
2,3,4,5,3,2,5,4,4,5,2,3,5,4,3,2
2,3,4,5,3,2,5,4,4,5,2,3,5,4,3,2

2 3 4 5    2 3 4 5
3 2 5 4    3 2 5 4
4 5 2 6    4 5 2 3
5 4 6 2    5 4 3 2

2 5
5 2

2-5+2-5=0 (mod 6)

2 3 4 5 
3 2 6 4 
4 6 2 3 
6 4 3 2

3 5
2 4

3-5+4-2=0 (mod 6)

[Pavlovsky]

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

-- Пт сен 28, 2012 15:40:18 --

whitefox в сообщении #624280 писал(а):

2-5+2-5=0 (mod 6)

Такая проверка работает для перестановок, полученных циклическим сдвигом. Или я не прав?
Поэтому я делаю аналогично предложению dimkadimon перед перебором составляю матрицу четверок перестановок и вычисляю их совместимость.

[whitefox]

Pavlovsky в сообщении #624292 писал(а):

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

Нет, не ОК.
Я дополнил своё сообщение.
Ваши базовые матрицы совсем не базовые.

-- 28 сен 2012, 13:44 --

Pavlovsky в сообщении #624292 писал(а):

Поэтому я делаю аналогично предложению dimkadimon перед перебором составляю матрицу четверок перестановок и вычисляю их совместимость.

Я долго отсутствовал в теме.
Дайте, пожалуйста, ссылку на это предложение.

[Pavlovsky]

whitefox в сообщении #624296 писал(а):

Дайте, пожалуйста, ссылку на это предложение.

Разве в этой огромной ветке, можно что то найти. Идея простая. Пребираем все варианты перестановок
AB
CD
И прямой проверкой проверяем их совместимость. 1 или 0 заносим в 4-х мерный массив. При переоборе, просто берем результаты из этого массива.

[whitefox]

А может Вы имели ввиду моё предложение:

whitefox в сообщении #615438 писал(а):

А именно будем заполнять базовую матрицу не числами, а перестановками.

Пусть

A B
C D

некоторый прямоугольник в базовой матрице, где A B C D перестановки.

Прямоугольник будет "разрешённым" если перестановка $\mathrm{M}=\mathrm{A}\mathrm{B^{-1}}\mathrm{D}\mathrm{C^{-1}}$ является беспорядочной, то есть не оставляет на месте ни одно число.