2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 58, 59, 60, 61, 62, 63, 64 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение14.07.2012, 15:39 
Аватара пользователя


21/02/10
1594
Екатеринбург
Похоже С10N100 у меня не будет. :-( Максимум чего смог выжать из своего подхода С10N91. Так бывает. Зато согрелся.

-- Сб июл 14, 2012 17:55:32 --

Вот такая строка для С=10 получилась. Закономерностей море.

(Оффтоп)

Изображение

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


19/12/10
1546
Складывается впечатление, что редукцией задачу C5N26 не решить.

Выскажу гипотезу:
Любой 5-сильно окрашенный прямоугольник 26х6 имеет не менее 15 ошибок.

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


22/03/08

7154
Саратов
whitefox
попробуйте искать прямоугольник 26x11 с (5,2)-раскраской по нашей лемме.

Гарантии никакой!

Интересный момент, я его уже отмечала выше: в случае (5,2)-раскраски в соответствии с требованиями нашей леммы размножение происходит не 2 и не 3 раза, а именно 2,5 раза!
То есть в данном случае 27 столбцов гарантированы.
Можно попробовать на прямоугольнике nx11 (n<26) с (5,2)-раскраской по нашей лемме. Должен получиться прямоугольник nx27 5-coloring.

Нет, не получилось 27 столбцов. Что-то я тут напутала, надо разбираться. Вот с этой целой частью [5/2]. Был у меня выше аналогичный пример, значит, аналогия не полная.
Или же исходный прямоугольник сейчас составила неправильно.

whitefox
можете проверить мой прямоугольник 15х11?

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

Удовлетворяет ли он требованиям (5,2)-раскраски по нашей лемме?
У меня что-то сегодня совсем голова не варит, с утра жара жарит :-(

Если удовлетворяет, то как его размножать? Сколько будет столбцов в итоговом прямоугольнике? Прибавлять по 2?

Где я ошиблась?

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


19/12/10
1546
Nataly-Mak
Подозреваю, что при $\mathrm{N}>\mathrm{C^2}$ редукция в принципе не возможна, ни при использовании
сильной $\mathrm{C}$-раскраски ни при использовании сильной $(\mathrm{C}{,}\mathrm{C'})$-раскраски.

Для получения этих решений нужно использовать какие-то, совершенно другие, идеи.

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


22/03/08

7154
Саратов
У меня лемма не работает :-(
Из приведённого выше прямоугольника я даже один раз не могу прибавить столбцы, то есть получить прямоугольник 15х22 5-coloring. Получается куча ошибок.
В чём причина? Исходный прямоугольник 15х11 правильный?

Совсем, похоже, перегрелась :D

-- Вс июл 15, 2012 07:57:21 --

Вот нашла аналогичный пример, это прямоугольник 16х10 с (5,2)-раскраской в соответствии с требованиями нашей леммы:

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

Этот-то прямоугольник у меня размножился! И в итоговом прямоугольнике получилось 25 столбцов! И он получился 5-coloring, без ошибок!

Сейчас ещё раз применю к нему лемму, может тогда ошиблась тоже.

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


19/12/10
1546
Nataly-Mak в сообщении #595378 писал(а):
whitefox
можете проверить мой прямоугольник 15х11?

Проверил, этот прямоугольник (5,2)-сильно раскрашенный (по МБ-лемме).

-- 15 июл 2012, 07:12 --

Нда-а-а :shock:
Что-то редукция не получается.
Возможно в моей программе проверки ошибка,
и на самом деле прямоугольник не (5,2)-сильно раскрашенный.

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


22/03/08

7154
Саратов
Вот результат применения леммы - прямоугольник 16х25 5-coloring:

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

Проверила в программе Эда, всё правильно, ошибок нет:

Код:
25,16,A,A,A,A,A,B,B,B,B,B,C,C,C,C,C,D,D,D,D,D,E,E,E,E,E,A,D,B,C,B,B,E,C,D,C,C,A,D,E,D,D,B,E,
A,E,E,C,A,B,A,A,C,D,B,C,B,D,E,C,D,C,E,A,D,E,D,A,B,E,A,E,B,C,A,B,A,B,C,D,D,B,C,D,E,E,C,D,E,A,A
,D,E,A,B,B,E,A,B,C,C,B,B,B,B,A,C,C,C,C,B,D,D,D,D,C,E,E,E,E,D,A,A,A,A,E,B,C,A,D,B,C,D,B,E,C,D,
E,C,A,D,E,A,D,B,E,A,B,E,C,A,B,D,C,A,C,C,E,D,B,D,D,A,E,C,E,E,B,A,D,A,A,C,B,E,B,B,A,D,C,D,C,B,E
,D,E,D,C,A,E,A,E,D,B,A,B,A,E,C,B,C,C,C,C,C,A,D,D,D,D,B,E,E,E,E,C,A,A,A,A,D,B,B,B,B,E,C,B,D,A,
B,D,C,E,B,C,E,D,A,C,D,A,E,B,D,E,B,A,C,E,A,C,A,B,D,C,D,B,C,E,D,E,C,D,A,E,A,D,E,B,A,B,E,A,C,B,
C,D,A,B,D,D,E,B,C,E,E,A,C,D,A,A,B,D,E,B,B,C,E,A,C,D,D,D,D,A,E,E,E,E,B,A,A,A,A,C,B,B,B,B,D,C,
C,C,C,E,D,A,C,B,B,E,B,D,C,C,A,C,E,D,D,B,D,A,E,E,C,E,B,A,A,D,B,A,C,C,E,C,B,D,D,A,D,C,E,E,B,E,
D,A,A,C,A,E,B,B,D,C,B,A,D,E,D,C,B,E,A,E,D,C,A,B,A,E,D,B,C,B,A,E,C

Так почему же с прямоугольником 15х11 ни черта не получается? :-(

У меня только одна версия: этот прямоугольник неправильно составлен, то есть он не удовлетворяет требованиям (5,2)-раскраски по нашей лемме.

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


19/12/10
1546
Nataly-Mak в сообщении #595385 писал(а):
У меня только одна версия: этот прямоугольник неправильно составлен, то есть он не удовлетворяет требованиям (5,2)-раскраски по нашей лемме.

Ничего не понимаю.
МБ-лемма безусловно верна.
Прямоугольник 15х11 проверил двумя разными программами,
обе ответили, что этот прямоугольник (5,2)-сильно раскрашен в соответствии
с МБ-леммой.
Но редукция не проходит :shock:

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

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #595382 писал(а):

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


Число 5 нельзя разложить на сомножетели. Поэтому МБ-лемму надо применять осторожно. С числом 5 не должно быть полу-прямоугольников. Для оставшихся чисел 1-4 применяем МБ-лемму.

-- Вс июл 15, 2012 09:52:27 --

whitefox в сообщении #595381 писал(а):
Подозреваю, что при редукция в принципе не возможна, ни при использовании
сильной -раскраски ни при использовании сильной -раскраски.

Для получения этих решений нужно использовать какие-то, совершенно другие, идеи.


Полностью согласен.

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #595388 писал(а):
Число 5 нельзя разложить на сомножетели. Поэтому МБ-лемму надо применять осторожно. С числом 5 не должно быть полу-прямоугольников. Для оставшихся чисел 1-4 применяем МБ-лемму.

Ничего не поняла! Каких не должно быть полу-прямоугольников с числом 5?

Я же привела совершенно аналогичный пример с прямоугольником 16х10 тоже с (5,2)-раскраской. И в этом примере всё получилось.
И в нём есть прямоугольники с вершинами (5,5), например, такой:

Код:
4 5
4 5

Так почему же в этом примере всё получилось?

Вы вот как раз и процитировали прямоугольник 16х10, с которым всё получилось!
А не получается с прямоугольником 15х11.
Вот с этим:

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

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


19/12/10
1546
Нет, в моей программе ошибки нет.
Зато МБ-лемма нуждается в уточнение.
Так в первых двух строчках встречаются:
Код:
1  4
1  4
которые при редукции на 2 переходят в:
Код:
3  1
3  1
а при редукции на 3 переходят в
Код:
4  2
4  2
В обоих случаях имеем монохромный прямоугольник.

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #595382 писал(а):
Вот нашла аналогичный пример, это прямоугольник 16х10 с (5,2)-раскраской в соответствии с требованиями нашей леммы:
Этот-то прямоугольник у меня размножился! И в итоговом прямоугольнике получилось 25 столбцов! И он получился 5-coloring, без ошибок!


25 столбцов это как? После репликации количество столбцов должно быть кратно 10.

-- Вс июл 15, 2012 10:14:45 --

whitefox

А кто разрешил делать 3 редукции? Можно делать только две.

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #595394 писал(а):
Nataly-Mak в сообщении #595382 писал(а):
Вот нашла аналогичный пример, это прямоугольник 16х10 с (5,2)-раскраской в соответствии с требованиями нашей леммы:
Этот-то прямоугольник у меня размножился! И в итоговом прямоугольнике получилось 25 столбцов! И он получился 5-coloring, без ошибок!


25 столбцов это как? После репликации количество столбцов должно быть кратно 10.

Да очень просто! Обрезала 5 столбцов! Хотя надо проверить, может и с 30 столбцами будет нормально.
А 16х25 точно 5-coloring. Не придерётесь. в программе Эда проверено.

-- Вс июл 15, 2012 09:16:20 --

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

whitefox

А кто разрешил делать 3 редукции? Можно делать только две.

Дык в этом примере и две редукции не получаются!!! :-(

-- Вс июл 15, 2012 09:18:29 --

Pavlovsky
вы бы уж проверили оба примера, прежде чем выдавать какие-то заключения с наскоку.
Во втором примере (с прямоугольником 16х10) у меня прошли 2,5 редукции! Не 2!

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


21/02/10
1594
Екатеринбург
Pavlovsky в сообщении #587516 писал(а):
Макарова-Беляев (c,k)-coloring это когда в каждом полу-прямоугольнике с левой стороной цвета A и правой стороной цвета B. A и B дают различные остатки при делении на k. В частном случае, при k=2 имеют разную четность.


Когда это формулировал, неявно полагал, что C lделится на k на цело. При этом допускается С/k репликаций. Если C не делится на k, то количество допустимых репликаций целая часть от C/k.

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


22/03/08

7154
Саратов
whitefox в сообщении #595393 писал(а):
Зато МБ-лемма нуждается в уточнение.
Так в первых двух строчках встречаются:
Код:
1  4
1  4
которые при редукции на 2 переходят в:
Код:
3  1
3  1


Так какое же это должно быть уточнение :?:

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 58, 59, 60, 61, 62, 63, 64 ... 130  След.

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



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

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


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

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