2014 dxdy logo

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

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




На страницу Пред.  1 ... 44, 45, 46, 47, 48, 49, 50 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение03.07.2012, 07:08 
Nataly-Mak в сообщении #591500 писал(а):
Вы читать умеете? :D
Написано "решения для C=15, 21... получаю из решений для C=14, 20...". Что непонятно?
Где вы видите "решение для C=15, 21x21"???
Поясняю ещё раз: решение для C=15 (N=184x184) получаю из решения для С=14 (N=183x183), добавляя строку и столбец.

Не, ну на самом деле: "С=14, 183" понятно, "С=15, 184" тоже понятно (респект за высокие результаты), "C=15, 21" - объясните пожалуйста, что в этой записи значит цифра 21?


Цитата:
В конце концов, и решение для C=15, 21x21 (если уж вы так прочитали - дописали - мой текст) можно получить из решения для C=14, 20x20, добавляя строку и столбец. Разве нет? :D

Дарю :D C=15, 21х21 без добавления строки и столбца:

Изображение

 
 
 
 Re: Новый конкурс программистов
Сообщение03.07.2012, 07:11 
Аватара пользователя
Nataly-Mak в сообщении #591347 писал(а):
Докажите, что решения C=10, N=100x100С=12, N=144х144С=14, N=196x196C=15, N=225x225C=18, N=324x324C=20, N=400x400C=21, N=441x441существуют / не существуют. Тогда можно будет их искать в случае, если они существуют, и не искать в противном случае.


В известной всем ёжикам статье, глава 2 посвящена определению верхней оценки задачи. Главная лемма 2.7. Из которой следует. Что нельзя построить кавадрат C^2+C для C-coloring задачи. Доказательство очень красивое, рекомендую всем ёжикам разобраться.
Улучшить эту оценку будет очень трудно. В той же статье доказательство G(11,10)
is not 3-colorable (лемма 7.4) занимает несколько страниц!

С нижней оценкой все просто! :D Достаточно разработать алгоритм построения квадрата, заявленных размеров! Таблица рекордов текущего конкурса является нижней оценкой для C=2-21.

-- Вт июл 03, 2012 09:38:58 --

Алгоритм, с помощью которого получены последние результаты достаточно переспективен для получения новых результатов. Нет проблем с количеством колонок. Фактически получается довольно длинный прямоугольник. Приходится лишние колонки отрезать. Есть возможности и для увеличения количества строк, надо только решить технические трудности. Назвать алгоритм достраиванием наверно нельзя. За основу берется комплект ортогональных латинских квадратов для некоторого С=p^s, где p простое. В результате получается квадрат для количества цветов С+1 или С+2.
Кстати идея алгоритма пришла в результате подсказки-намека Сергея Беляева. В этом деле главное вовремя подставить голову под падающее яблоко.

Так как шкодю медленно, вбрасываю еще идею. С помощью диагональных алгоритмов построить прямоугольник 100х20 удовлетворяющий условиям теоремы 4.3 (усиленный вариант). Это же намного быстрее чем строить квадрат 100х100. Во-первых размеры меньше. Во-вторых требования жестче, значит отсечений вариантов при переборе будет больше.

 
 
 
 Re: Новый конкурс программистов
Сообщение03.07.2012, 07:59 
Аватара пользователя
Pavlovsky в сообщении #591513 писал(а):
В известной всем ёжикам статье, глава 2 посвящена определению верхней оценки задачи. Главная лемма 2.7. Из которой следует. Что нельзя построить кавадрат C^2+C для C-coloring задачи.

Вы про верхнюю оценку ещё в прошлом году сказали :D
Я вас не о верхней оценке спрашиваю, а о существовании решений C^2xC^2 для С=10,12,14,18,20.

Цитата:
Кстати идея алгоритма пришла в результате подсказки-намека Сергея Беляева. В этом деле главное вовремя подставить голову под падающее яблоко.

Ну все подсказки-намёки вы у нас с полунамёка понимаете :D
И в кого только вы такой умный уродились?
Сам svb, небось, свою подсказку-намёк и не понял. Как в случае с dimkadimon получается :-) Возвращайте теперь svb его подсказку-намёк :wink:

Цитата:
С помощью диагональных алгоритмов построить прямоугольник 100х20 удовлетворяющий условиям теоремы 4.3 (усиленный вариант). Это же намного быстрее чем строить квадрат 100х100. Во-первых размеры меньше. Во-вторых требования жестче, значит отсечений вариантов при переборе будет больше.

Zealint тут утверждал, что это не проще, а даже сложнее, чем делать перебор в квадрате 100х100. Посмотрите его сообщения по данному вопросу.
Мне тоже кажется, что с прямоугольником 100х20 работать проще, чем с квадратом 100х100. Но мало что кому кажется. Примеры давайте конкретные, результаты экспериментов.

-- Вт июл 03, 2012 09:20:05 --

svb в сообщении #589865 писал(а):
...Требование же, быть полем, слишком сильное для нашей задачи.

Мне этот намёк очень нравится :-)
Тут что-то есть!
Знать бы ещё, что значит "требование быть полем" :-(

 
 
 
 Re: Новый конкурс программистов
Сообщение03.07.2012, 08:28 
Аватара пользователя
Может кто поможет.
http://dic.academic.ru/dic.nsf/enc_math ... 0%98%D0%99
ЛАТИНСКИЙ ПРЯМОУГОЛЬНИК
Цитата:
На Л. п. распространяются нек-рые понятия и теоремы, связанные с латинскими квадратами. Так, два Л. п. размера наз. ортогональными, если все пары вида различны. Множество Л. п. (mxn, m<=n), в к-ром любые два Л. п. ортогональны, имеет не более m-1 Л. п.


Возник такой вопрос. Как пострить множество m-1 ортоганальных латинских прямоугольников размером mxn, m<=n? В статье есть ссылка на Риордана. Скачал эту книжку, как построить нужное множество ЛП там нет.

Например элементарно построить p-1 ортогональных латинских квадратов размером pxp (p простое).
А как построить p-1 ортогональных латинских прямоугольников размером px(p+1)??

-- Вт июл 03, 2012 11:07:56 --

Nataly-Mak в сообщении #591515 писал(а):
svb в сообщении #589865 писал(а):...Требование же, быть полем, слишком сильное для нашей задачи.
Мне этот намёк очень нравится Тут что-то есть!Знать бы ещё, что значит "требование быть полем"


Это Сергей об алгебру ударился. Для построения разбиений в случае С=p^s, где p простое s>1, используется хитрый алгебраический алгоритм основанный на конечных полях Галуа. Сергей писал, что разобрался в этом алгоритме. Читал этот алгоритм. Разбираться не стал. Мне хватило комплектов ЛК из ваших статей.

 
 
 
 Re: Новый конкурс программистов
Сообщение03.07.2012, 10:44 
Аватара пользователя
Несколько диагональных решений для С=5, может быть, пригодятся для анализа.
Начала с самого минимального, 3х3, далее строила все подряд в программе Эда, дошла до 17х17. Дальше уже туго строятся.

Изображение

Характеристическая строка:
Код:
1,2,3,4,5


Изображение

Характеристическая строка:
Код:
1,2,3,4,5,1,2


Изображение

Характеристическая строка:
Код:
1,2,3,4,5,1,2,3,4


Изображение

Характеристическая строка:
Код:
1,2,3,4,5,1,2,3,2,1,5


Изображение

Характеристическая строка:
Код:
1,2,3,4,5,1,2,3,2,1,5,5,1


Следующие квадраты не показываю, сразу 17х17:

Изображение

Для сравнения интернетовское решение 17х17:

Изображение

У меня получилось оригинальное решение отличное от интернетовского.
Подозреваю, что таких решений можно много построить.

Может быть, примитивные эксперименты, но мне всё равно интересно.
А диагональное решение C=7, N=49x49 построил кто-нибудь?

 
 
 
 Re: Новый конкурс программистов
Сообщение03.07.2012, 12:00 
Аватара пользователя
Для С=6 аналогичные эксперименты, легко дошла до решения 21х21:

Изображение

Красивые решения получаются.
Не удивительно, что svb легко нашёл по программе решение 36х36.

 
 
 
 Re: Новый конкурс программистов
Сообщение03.07.2012, 13:16 
Аватара пользователя
Диагональный прямоугольник 50х20 10-coloring, в нескольких местах диагональность нарушается - диагональ меняет цвет.

Изображение

Прямоугольник построился очень легко в программе Эда. Можно продолжить построение до 100 строк.

Очень интересен вопрос: много ли в этом прямоугольнике несоответствий требованиям усиленного варианта леммы 4.3 :?:
И второй вопрос: можно ли его привести в соответствие с этими требованиями :?:

 
 
 
 Re: Новый конкурс программистов
Сообщение03.07.2012, 13:35 
С14 100х100 неактуально?

 
 
 
 Re: Новый конкурс программистов
Сообщение03.07.2012, 13:44 
Аватара пользователя
Это для кого как :-)

 
 
 
 Re: Новый конкурс программистов
Сообщение03.07.2012, 13:55 
У меня программа перебора такой составила, целых пол-часа думала. На экране он ессно целиком не помещается. Куда его теперь - в топку?

 
 
 
 Re: Новый конкурс программистов
Сообщение03.07.2012, 15:00 
Аватара пользователя
Nataly-Mak в сообщении #591515 писал(а):
Мне этот намёк очень нравится :-)
Тут что-то есть!
Знать бы ещё, что значит "требование быть полем" :-(
Дык... в первом классе проходили таблицу умножения - помните, в наше время на обложке тонких тетрадей печатали эту таблицу. Можно рассматривать эти таблицы по модулю - получим кольца с двумя операциями + и x, но в них могут появиться делители 0, но не всегда. Применительно к нашим квадратам, вписываем в маленький квадрат таблицу умножения, а далее используем таблицу сложения :-)

 
 
 
 Re: Новый конкурс программистов
Сообщение03.07.2012, 15:12 
Аватара пользователя
Alexu007 в сообщении #591585 писал(а):
У меня программа перебора такой составила, целых пол-часа думала. На экране он ессно целиком не помещается. Куда его теперь - в топку?

Зачем в топку? Отправьте на конкурс :D

-- Вт июл 03, 2012 16:19:15 --

Достроила прямоугольник 100х20 10-coloring:

Изображение

Такой красавец! Как бы его... преобразовать, чтобы он удовлетворял требованиям нашей леммы :roll:

Сейчас прямо из этого (неправильного) попробую квадрат 100х100 построить.
Интересно: много в этот раз ошибок будет.

-- Вт июл 03, 2012 16:24:20 --

svb в сообщении #591617 писал(а):
Дык... в первом классе проходили таблицу умножения - помните, в наше время на обложке тонких тетрадей печатали эту таблицу.

Таблицу умножения вроде помню :D

Я в одной статье описывала построение группы из 5 попарно ортогональных ЛК 12-го порядка из какой-то книги. По-моему, там это самое применяется, тоже какая-то таблица умножения. Мне тогда на форуме объяснили, как этой таблицей надо пользоваться.

А, нет, там абелева группа, а не поля Галуа.
Вот в этой статье:
http://www.natalimak1.narod.ru/mols12.htm

 
 
 
 Re: Новый конкурс программистов
Сообщение03.07.2012, 15:28 
Аватара пользователя
svb в сообщении #591617 писал(а):
рассматривать эти таблицы по модулю


Поле Галуа какое то хитрое, не совсем сложение по модулю. Там a+a=0 для любого a.

 
 
 
 Re: Новый конкурс программистов
Сообщение03.07.2012, 15:33 
Nataly-Mak в сообщении #591624 писал(а):
Alexu007 в сообщении #591585 писал(а):
У меня программа перебора такой составила, целых пол-часа думала. На экране он ессно целиком не помещается. Куда его теперь - в топку?

Зачем в топку? Отправьте на конкурс :D

Так там для С=15 200х200 котируются, кому нужен мой скромный 100х100? Или с таким результатом тоже есть смысл? И где я буду - на последнем месте? Да ещё и региться для этого надо!

Далее, чтобы отправить на конкурс, нужно квадрат в файл скинуть, как я понимаю - чтобы "программа Эда" его приняла. Какие требования к этому файлу? Текстовый? Разделители между цифрами? Разделители между строками?

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


Цитата:
Такой красавец! Как бы его... преобразовать, чтобы он удовлетворял требованиям нашей леммы :roll:
Так легко же. Уберите пересечения... :D

 
 
 
 Re: Новый конкурс программистов
Сообщение03.07.2012, 15:44 
Аватара пользователя
Квадраты на конкурс отправлять очень просто. Числа разделяются запятыми, вот и все премудрости.

Цитата:
Такой красавец! Как бы его... преобразовать, чтобы он удовлетворял требованиям нашей леммы :roll:

Цитата:
Так легко же. Уберите пересечения... :D

Так нету у меня программы :-( Писать её ещё надо.
К тому же Zealint писал, что не преобразовываются эти прямоугольники. А почему бы им не преобразовываться?

 
 
 [ Сообщений: 1937 ]  На страницу Пред.  1 ... 44, 45, 46, 47, 48, 49, 50 ... 130  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group