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, Супермодераторы



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

Сейчас этот форум просматривают: Dmitriy40


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

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