2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 102, 103, 104, 105, 106, 107, 108 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение08.09.2012, 06:49 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Вот вторая базовая матрица для той же свёртки блоков, приведена 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.

Следовательно, все базовые матрицы этой группы не годятся для новой свёртки.

Задача (простенький перебор :wink: )

найти для приведённой выше свёртки блоков R+ базовую матрицу Rx.

Не уверена, что задача имеет решение.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение08.09.2012, 08:09 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Не эту ли задачу решал здесь Pavlovsky?

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

С=10
Циклический ЛК 10х10.
0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 0
2 3 4 5 6 7 8 9 0 1
3 4 5 6 7 8 9 0 1 2
4 5 6 7 8 9 0 1 2 3
5 6 7 8 9 0 1 2 3 4
6 7 8 9 0 1 2 3 4 5
7 8 9 0 1 2 3 4 5 6
8 9 0 1 2 3 4 5 6 7
9 0 1 2 3 4 5 6 7 8

Матрица перестановок
2 3 4 5 6 7 8
3 5 9 8 2 4 6
4 9 8 6 5 10 3
5 8 6 2 10 3 7
6 2 5 10 3 9 4
7 4 10 3 9 6 2
8 6 3 7 4 2 9


ЛК 10х10. Таблица сложения.
0 1 2 3 4 5 6 7 8 9
1 2 3 4 0 6 7 8 9 5
2 3 4 0 1 7 8 9 5 6
3 4 0 1 2 8 9 5 6 7
4 0 1 2 3 9 5 6 7 8
5 6 7 8 9 0 1 2 3 4
6 7 8 9 5 1 2 3 4 0
7 8 9 5 6 2 3 4 0 1
8 9 5 6 7 3 4 0 1 2
9 5 6 7 8 4 0 1 2 3

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


По этим матрицам можно получить решение C10N90. Интересно можно ли его нарастить до приличных значений?! Например до C10N94??


Представлены пары матриц R+, Rx для С=10.
Выше описаны эксперименты для С=6.

-- Сб сен 08, 2012 09:53:22 --

Интересен и пример dimkadimon для С=5.

Вот его решение:

Изображение

dimkadimon
только вы перепутали местами матрицы, у вас базовой будет матрица:

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

Вторая матрица - свёртка блоков - у вас задаётся исходным квадратом 5х5 (первый блок), который не является никаким латинским квадратом, и правилом получения следующих блоков.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение08.09.2012, 09:24 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
dimkadimon
это все ваши пять блоков:

(Оффтоп)

Код:
№ 1
5 1 3 2 2
2 2 3 1 5
3 1 5 1 3
5 4 4 1 4
2 4 2 2 3

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

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

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

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

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение08.09.2012, 10:22 
Заслуженный участник
Аватара пользователя


19/12/10
1546
В развитие моего предложения по базовым матрицам перестановок.

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

То есть в каждой клетке базовой матрицы будет стоять перестановка $i\cdot j$, где $i$ - перестановка общая для всех клеток одной строки, а $j$ - перестановка общая для всех клеток одного столбца.

Условие корректности базовой матрицы будет следующим:
для всех $i_1,i_2,j_1,j_2$ перестановка $m=(i_1j_1)(j_2^{-1}i_1^{-1})(i_2j_2)(j_1^{-1}i_2^{-1})$ есть беспорядок.

Очевидна следующая лемма.
Лемма 1: Для любых перестановок $i,m$ перестановка $m$ будет беспорядком тогда и только тогда, когда беспорядком будет перестановка $imi^{-1}$.

Используя лемму 1 приведём условие корректности базовой матрицы к следующему виду:
для всех $i_1,i_2,j_1,j_2$ перестановка $(j_1j_2^{-1})(i_1^{-1}i_2)(j_2j_1^{-1})(i_2^{-1}i_1)$ есть беспорядок.

Будем называть две перестановки не пересекающимися если в одинаковых позициях у них стоят разные числа.
Например, перестановки 2 3 1 5 6 4 и 3 2 1 5 4 6 пересекаются так как в четвёртой позиции у них стоит одно и тоже число -- 5, а перестановки 1 2 3 4 5 6 и 2 3 4 5 6 1 не пересекаются.

Очевидна следующая лемма.
Лемма 2: Для любых перестановок $a,b$ перестановка $ab^{-1}$ будет беспорядком тогда и только тогда, когда перестановки $a,b$ не пересекаются.

Используя лемму 2 преобразуем условие корректности базовой матрицы к виду:
для всех $i_1,i_2,j_1,j_2$ перестановки $(j_1j_2^{-1})(i_1^{-1}i_2)$ и $(i_1^{-1}i_2)(j_1j_2^{-1})$ не пересекаются.

На время забудем о базовых матрицах и будем искать два множества перестановок для которых выполнено следующее условие:
для любых двух различных перестановок $i_1,i_2$ из первого множества и любых двух различных перестановок $j_1,j_2$ из второго множества перестановки $(j_1j_2^{-1})(i_1^{-1}i_2)$ и $(i_1^{-1}i_2)(j_1j_2^{-1})$ не пересекаются.

В частности, если для двух множеств перестановок, каждое по девять перестановок десятого порядка, будет выполнено приведённое выше условие, то решение C10N100 существует и легко строится по этим множествам.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение08.09.2012, 10:37 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox
пока не вникала (пойти пожевать надо, а то умру с голоду за компьютером :D ), но чувствую, что вы в полёте за жар-птицей :wink:

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение08.09.2012, 11:03 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #616114 писал(а):
чувствую, что вы в полёте за жар-птицей :wink:

Жар-птица сиречь мираж?

Возможно. :-)

Не решёнными остаются два вопроса:
1. Каким условиям должны удовлетворять перестановки A и B, чтобы перестановки AB и BA не пересекались?
2. Если первый вопрос решён, то каким условиям должны удовлетворять перестановки $i_1,i_2$, чтобы перестановка $i_1^{-1}i_2$ удовлетворяла условиям из первого пункта?

Решив эти вопросы, можно, либо построить C10N100, либо доказать, что таким методом построить C10N100 невозможно (из чего, впрочем, не будет следовать не существование C10N100).

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение08.09.2012, 11:46 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #616125 писал(а):
Nataly-Mak в сообщении #616114 писал(а):
чувствую, что вы в полёте за жар-птицей :wink:

Жар-птица сиречь мираж?

Не совсем так.

Мираж - обманчивый призрак; нечто, созданное воображением, кажущееся.

Жар-птица - волшебная птица русских народных сказок с сверкающими (горящими как жар) перьями.

На суку извилистом и чудном,
Пёстрых сказок пышная жилица,
Вся в огне, в сиянье изумрудном,
Над водой качается жар-птица.


А. Фет. Фантазия

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

alexBlack в своей статье пишет, что для С=10 удалось сделать полный перебор. Максимальная найденная матрица 8х8, что даёт решение 90х90.

Но тут сразу же возникает вопрос: при каких условиях он сделал полный перебор?
Имеется ли в виду полный перебор только для блоков, строящихся циклическим сдвигом, то есть как раз тех, которые у него показаны в самом начале статьи для С=5?

Если только для таких блоков, то это, разумеется, очень мало, чтобы сделать однозначный вывод о несуществовании решения C10N100.

Я чуть выше показала цитату из сообщения Pavlovsky. Мы видим у него две пары матриц R+, Rx для С=10.
Эти модификации матриц можно продолжить.
Pavlovsky подчёркивает, что очень многое зависит от исходного ЛК.

Ну, и ваше расширение метода тоже, конечно же, надо проработать.
К сожалению, пока мне это всё сложно для понимания.
Может быть, выскажутся коллеги, как они смотрят на ваше расширение.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение08.09.2012, 12:10 
Заслуженный участник
Аватара пользователя


19/12/10
1546
whitefox в сообщении #616125 писал(а):
Каким условиям должны удовлетворять перестановки A и B, чтобы перестановки AB и BA не пересекались?
Вот ответ.

Наложим перестановки $\mathrm{A}$ и $\mathrm{B}$ друг на друга (порядок перестановок важен). Получим множество упорядоченных пар.

Тоже самое проделаем с перестановками $\mathrm{B^{-1}}$ и $\mathrm{A^{-1}}$ (порядок по-прежнему важен). Получим второе множество упорядоченных пар.

Перестановки $\mathrm{AB}$ и $\mathrm{BA}$ не пересекаются тогда и только тогда, когда полученные множества упорядоченных пар не пересекаются.

Не знаю, чем этот ответ лучше вопроса. :-(

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение08.09.2012, 13:11 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Удивительные вещи открываются!
Может быть, я открыла Америку? :?

На это меня натолкнул пример dimkadimon.
Оказывается, матрицы R+ и Rx можно менять местами.
Покажу на примере из статьи alexBlack для С=5.

У него базовая матрица Rx такая:

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

а это свёртка блоков R+:

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

Теперь поменяем местами эти матрицы, базовой матрицей будет свёртка блоков.
А бывшая базовая матрица теперь будет блок №1. А следующие блоки получаются, как у dimkadimon, плюс один цвет.
Всё получается!

Вот готовое решение:

Изображение

У svb есть теорема, там что-то про обращённые матрицы. Может, это как раз то, что я сейчас открыла для себя?

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение08.09.2012, 14:55 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Проделала то же самое в примере dimkadimon: поменяла местами матрицы.
Всё получилось!

Вот решение:

Изображение

dimkadimon
по-моему, это решение симпатичнее получилось :roll:

Ничего не обобщаю, много неясностей у меня. Может быть, менять местами матрицы можно только для С, являющихся простыми числами (?)
Попробовала для классических таблиц сложения и умножения для С=8, ничего не получилось.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение09.09.2012, 02:40 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
alexBlack отмечает в своей статье, что для С=5 достаточно найти базовую матрицу 4х4. В самом деле, потом добавляем обрамление и получаем решение C5N25.

Не помню, приводила ли такой пример. Ну, не беда, если повторю.
Сейчас открыла файл, в котором этот метод у меня описан, и там вижу, что примеры рассматривала и для С=4, и для С=5. Вот для С=4 точно помню, что выкладывала пример.
Но я строила это решение без таблиц сложения и умножения в GF(4), потому что я их просто не знаю.

Внимание!
Подскажите, пожалуйста, таблицы сложения и умножения в GF(4).
В Википедию заглянула, там пример приведён для GF(9).
svb тоже не приводил таблицы сложения и умножения в GF(4).
Как строятся такие таблицы, я пока так и не разобралась. Мудрёно как-то :-(
А мне интересны все примеры, начиная с самых маленьких С.

Итак, решение C5N25, полученное матричным методом.
Базовая матрица Rx:

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

Базовую матрицу я нашла даже не пребором, а просто подбором в программе Эда. Здесь это элементарно.

Свёртка блоков R+:

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

Очевидно, что блоки строятся циклическим сдвигом.

Готовое решение:

Изображение

Очевидно, что матричный метод работает для всех простых С аналогичным образом.
Также матричный метод работает и для степеней простых, как мы уже знаем, тут просто используем таблицы сложения и умножения в соответствующем GF(p^k).
Наконец, мы видели примеры применения матричного метода для С=6, С=10.

Таким образом, матричный метод вообще самый базовый :-) прямо-таки универсальный, годится для всех С.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение09.09.2012, 04:24 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Рассказала о матричном методе на форуме конкурса:
http://infinitesearchspace.dyndns.org/c ... -aftermath

Пожалуйста, покритикуйте перевод (это тоже Google работал).
Могут ли что-то понять иностранцы в моём сообщении? :D

Главное, чтобы поняли приглашение принять участие в решении проблемы :wink:

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение09.09.2012, 05:52 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Для С=7 у нас ещё не было примера :-)

Базовую матрицу взяла в статье alexBlack:

Код:
1 2 3 4 5 6
2 2 7 7 4 4
3 2 4 3 3 2
4 2 1 6 2 7
5 2 5 2 1 5
6 2 2 5 7 3

Блоки строятся циклическим сдвигом.
Решение такое получилось:

Изображение

Цитата:
Очевидно, что матричный метод работает для всех простых С аналогичным образом.

А вообще-то для простых С не надо искать базовую матрицу.
Для таких С тоже ведь существуют конечные поля и таблицы сложения и умножения. Вот их и надо использовать.
Вспомнила, что в самом начале обсуждения этого метода Pavlovsky приводил пример для С=11. Там всё элементарно, не надо искать никакие матрицы. Блоки строятся циклическим сдвигом. Базовая матрица, как написал Pavlovsky, легко угадывается :-)

Не знаю, насколько "легко угадывается" базовая матрица, но я угадала :roll:
Вот она для С=7:

Код:
1 1 1 1 1 1 1
1 2 3 4 5 6 7
1 3 5 7 2 4 6
1 4 7 3 6 2 5
1 5 2 6 3 7 4
1 6 4 2 7 5 3
1 7 6 5 4 3 2

Легко написать базовую матрицу по аналогии для любого простого С.

Решение для С=7, построенное по приведённой базовой матрице (блоки строятся циклическим сдвигом, как и в приведённом выше примере с базовой матрицей из статьи alexBlack):

Изображение

Здесь нет обрамления.
Кому как больше нравится: с обрамлением или без него.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение09.09.2012, 12:12 
Аватара пользователя


01/06/12
1013
Adelaide, Australia
whitefox в сообщении #616111 писал(а):
На время забудем о базовых матрицах и будем искать два множества перестановок для которых выполнено следующее условие:
для любых двух различных перестановок $i_1,i_2$ из первого множества и любых двух различных перестановок $j_1,j_2$ из второго множества перестановки $(j_1j_2^{-1})(i_1^{-1}i_2)$ и $(i_1^{-1}i_2)(j_1j_2^{-1})$ не пересекаются.

В частности, если для двух множеств перестановок, каждое по девять перестановок десятого порядка, будет выполнено приведённое выше условие, то решение C10N100 существует и легко строится по этим множествам.


Спасибо whitefox, теперь я вроде понял о чем вы говорите. Появился такой вопрос:

Почему нельзя зафиксировать одно из етих множеств (например как 123...N, 23..N1, 34..N12 итд.) и искать только второе множество, таким образом сокращая количество работы в 2 раза? Или етого условия будет не достаточно?

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение10.09.2012, 06:24 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
dimkadimon в сообщении #615349 писал(а):
Меня лично диагональные решения не интересуют.
Herbert доказал что строго-диагональных решений C^2 x C^2 нет для N=8, 9 и 10. Скорее всего их нет для C>10 тоже. Если я правильно понимаю, не строго диагональные решения это когда используются все 2N-1 диагонали? В таком случае они меня тоже не интересуют потому что их гораздо сложнее искать чем строго диагональные - количество диагоналей увеличивается от N до 2N-1.

А кто-нибудь доказал, что не существует не строго диагональное решение C10N100?
По-моему, никто не доказал.

По поводу строго диагонального решения C10N100 вопрос давным-давно решил svb, как мне помнится.

Для не строго диагонального решения перебор в лоб будет, разумеется, огромным и невыполнимым за реальное время.
Значит, надо придумать эвристический алгоритм.
А это не менее интересно, чем все другие методы поиска решения C10N100.

У меня вот сейчас вообще чудеса какие-то: никак не могу найти не строго диагональные решения C3N9, C4N16, C5N25, C6N36, C7N49, хотя строго диагональные решения для таких C и N существуют и найдены.

Сейчас запустила программу whitefox на поиск решения C6N36; программа работает, но неизвестно, какое решение она найдёт первым - строго или не строго диагональное (эта программа строит и те, и другие и работает до первого найденного решения).

Решения C3N9, C4N16, C5N25 программа выдаёт строго диагональные.
То же самое делает программа svb.

(Кстати, если кто интересуется, svb выложил ссылки на свои результаты на форуме конкурса.)

Как же построить указанные не строго диагональные решения? Неужели они не существуют?

-- Пн сен 10, 2012 07:36:36 --

Окно программы whitefox:

Изображение

Наблюдаю, как идёт перебор. Идёт он понятно: как только 6 возникает, предыдущая циферка увеличивается на единицу.

Итак, полный перебор в лоб?

Уже запускала программу на поиск решения C6N36, но так и не дождалась результата.
Интересен такой момент: строго диагональное решение C6N36 по программе svb находится мгновенно.
Это легко объясняется: у svb ищутся только строго диагональные решения, а перебор для таких решений в разы меньше, чем для не строго диагональных решений.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 102, 103, 104, 105, 106, 107, 108 ... 130  След.

Модераторы: maxal, Toucan, PAV, Karan, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group