2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 124, 125, 126, 127, 128, 129, 130  След.
 
 Re: Новый конкурс программистов
Сообщение09.10.2012, 06:49 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
dimkadimon в сообщении #628685 писал(а):
Nataly-Mak в сообщении #628682 писал(а):
Если в вашем решении 740 "дырок", то чем же оно лучше? :D
Если же в вашем примере 740 ошибок, то у меня приведено приближение к решению C10N100, в котором 423 ошибки.


У меня регулярное решение где 740 ошибок, которое базируется на strong 100х10 где 74 ошибки. У вас регулярное решение где 730 дырок и нерегулярное где 423 дырки. Моё решение лучше потому что его можно превратить в решение где будет меньше чем 423 дырки.

Ну, вот когда превратите, тогда и покажете :D
Пока я вижу только решение со 740 ошибками.

Извиняюсь, забыла: в нерегулярном у меня 423 "дырки" на самом деле.

Но всё равно ничего лучшего я пока не вижу.
А даже если и есть у вас лучше, так это же у вас, а не у меня :D

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


01/06/12
1016
Adelaide, Australia
dimkadimon в сообщении #628685 писал(а):
Это глава 7 :D
Книга ещё не закончена. Я же сообщала здесь, что продолжаю писать книгу.
Глава 7 уже написана, вчера поставила в этой главе точку. Могу выложить :D


Выкладывайте! На самом деле эти решение ( и C=15, 21) будут самыми интерсными для будущих учёных в этой области, потому что эти решения не описаны в grid.pdf.

-- 09.10.2012, 12:37 --

Nataly-Mak в сообщении #628687 писал(а):
В нерегулярном приближении у меня 423 ошибки, а не "дырки".
Ну, вот когда превратите, тогда и покажете :D
Пока я вижу только решение со 740 ошибками.


Разве?!? У вас написано: "Ещё есть нерегулярное приближение, в котором 423 дырки, это решение показано на рис. 16."
Похоже что вы сами свою книгу не читали :)

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


22/03/08

7154
Саратов
Ну, вот напишу ещё пару глав, тогда выложу часть третью - главы 7,8,9.
Выкладывать одну главу не хочется. Тем более что читателей-то раз-два и нету :D
Вторую часть на файлообменнике скачали 3 человека, первую часть - 7 человек.

-- Вт окт 09, 2012 07:57:41 --

dimkadimon в сообщении #628688 писал(а):
Разве?!? У вас написано: "Ещё есть нерегулярное приближение, в котором 423 дырки, это решение показано на рис. 16."
Похоже что вы сами свою книгу не читали :)

Я же извинилась за неточность. Материалов у меня столько, что не мудрено что-то забыть или перепутать. Главное, что в книге написано всё правильно.
Ну, свою книгу я не читаю, а пишу :D

А вот как вы умудрились не заметить лемму МБ в целой главе, посвящённой этой лемме? :shock:

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


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #628687 писал(а):
Но всё равно ничего лучшего я пока не вижу.
А даже если и есть у вас лучше, так это же у вас, а не у меня :D

Я думал вы пишите про достижения всех участников, а не только свои достижения?

-- 09.10.2012, 12:47 --

Nataly-Mak в сообщении #628689 писал(а):
А вот как вы умудрились не заметить лемму МБ в целой глве, посвящённой этой лемме? :shock:


Значит плохо у вас написано, если главную идею читатель пропустил, не смотря на то что он её искал :)
Я искал текст с большими буквами "Лемма Макаровой-Беляева", но я его не нашёл.

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


22/03/08

7154
Саратов
dimkadimon в сообщении #628691 писал(а):
Nataly-Mak в сообщении #628687 писал(а):
Но всё равно ничего лучшего я пока не вижу.
А даже если и есть у вас лучше, так это же у вас, а не у меня :D

Я думал вы пишите про достижения всех участников, а не только свои достижения?


Я это ваше достижение пока не вижу :D Вы пишете, что можно превратить, но ведь ещё не превратили?

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

-- Вт окт 09, 2012 08:07:43 --

dimkadimon в сообщении #628691 писал(а):
Значит плохо у вас написано, если главную идею читатель пропустил, не смотря на то что он её искал :)
Я искал текст с большими буквами "Лемма Макаровой-Беляева", но я его не нашёл.

Вы что читали книгу в режиме "поиска"? :D
Я же вам привела цитату, в которой написано "леммой Макаровой-Беляева".
А само название главы - "Расширение области применения теоремы 3.3" вам ни о чём не сказало?

Значит, плохо у меня написано, если "Поиск" не находит нужное название леммы :D

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


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #628692 писал(а):
Я это ваше достижение пока не вижу :D Вы пишете, что можно превратить, но ведь ещё не превратили?


Я ничего не должен превращать. Задача была: уменьшить количество запрещенных прямоугольников, а не уменьшить количество дырок. Это вам надо превращать свои решения с дырками, чтобы узнать сколько там ошибок. Когда вы это сделайте то увидите что их больше чем 740.

-- 09.10.2012, 12:55 --

Nataly-Mak в сообщении #628692 писал(а):
Вы что читали книгу в режиме "поиска"? :D
Я же вам привела цитату, в которой написано "леммой Макаровой-Беляева".
А название самой главы - "Расширение области применения теоремы 3.3" вам ни о чём не сказало?

Значит, плохо у меня написано, если "Поиск" не находит нужное название леммы :D

Я снова прочитал ту главу: Расширение области применения теоремы 3.3. Но опять не нашёл само определение вашей Леммы. Где она?

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


22/03/08

7154
Саратов
dimkadimon
вы хотите, чтобы ваши достижения были помещены в книгу, и в то же время пишете, что ничего не должны превращать. Не должны - не превращайте. Я вас не прошу и не заставляю.
Беспредметный у нас разговор.
Все ваши сегодняшние комментарии, как говорится, мимо кассы. Вы хотя бы прочтите текст внимательно, прежде чем писать, что в тексте чего-то нет.

-- Вт окт 09, 2012 08:20:46 --

dimkadimon в сообщении #628693 писал(а):
Я снова прочитал ту главу: Расширение области применения теоремы 3.3. Но опять не нашёл само определение вашей Леммы. Где она?

А, теперь поняла. Вам нужна формулировка леммы?

Так я её не формулирую и не доказываю. Я просто привожу примеры расширения области применения теоремы 3.3 (бывшей в первом варианте статьи леммой 4.3).
Начинаю с первого примера, который привёл к тому, что лемму можно усилить. Это во-первых. Дальше, я нашла пример (просто конкретный пример!), к которому можно применить теорему 3.3 принципиально по-другому (этот вариант был предложен на форуме alexBlack). То, что я нашла этот пример, уже интересный сам по себе факт.

Я не учёный, который обязан формулировать леммы (теоремы) и доказывать их. Пишу, как умею.

Кстати, и само название "лемма Макаровой-Беляева" я считаю полушутливым названием. Это написано и в книге. Если делать серьёзную заявку на такое название, то да: лемма должна быть сформулирована и доказана.

-- Вт окт 09, 2012 09:05:08 --

dimkadimon в сообщении #628693 писал(а):
Это вам надо превращать свои решения с дырками, чтобы узнать сколько там ошибок. Когда вы это сделайте то увидите что их больше чем 740.

Мне не надо превращать свои решения с "дырками" в решения с ошибками, у меня в архиве уже есть приближение к решению C10N100, в котором 790 ошибок. Распеределение цветов в этом решении: каждый цвет занимает 1000 ячеек.
Решение тоже построено из strong 10-coloring прямоугольника 90х10, в котором 79 ошибок. В вашем прямоугольнике только на 5 ошибок меньше. Ну, если мой прямоугольник "потрясти", может, и меньше 79 ошибок получится :-)
Так что не так уж сильно лучше ваше решение с 740 ошибками моего решения с 790 ошибками. Тот же порядок количества ошибок.

(Оффтоп)

Изображение

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


22/03/08

7154
Саратов
Нашла в архиве решение C10N100 c 391 "дыркой" (заменю в книге решение с 423 "дырками" на это решение, всё-таки меньше "дырок" :-) ). Скормила это решение программе "вытряхивания" ошибок, с ходу выдалось решение с 812 ошибками; ежели потрясти... с недельку непрерывно :D
Ну, конечно, "трясти" не буду. Порядок количества ошибок тот же: что 790, что 812, что 740.

-- Вт окт 09, 2012 10:08:46 --

dimkadimon в сообщении #628685 писал(а):
У меня регулярное решение где 740 ошибок, которое базируется на strong 100х10 где 74 ошибки.

Это не описка? У вас в самом деле strong 10-coloring прямоугольник 100х10?
А почему 100х10, когда достаточно strong 10-coloring прямоугольника 90х10 для построения решения C10N100?
Если вы из прямоугольника 100х10 сделаете прямоугольник 90х10, в нём же может оказаться гораздо меньше ошибок.

Цитата:
Кстати вы не дали определение "регулярному решению" :))))

Я его не знаю :P
А вы знаете?
То определение, которое я привела здесь, Zealint назвал глупым, а не глупое не привёл.

Вот выложу свой прямоугольник strong 10-coloring 90x10 c 79 ошибками:

(Оффтоп)

Код:
10,90,F,F,G,F,I,H,G,H,I,C,D,G,J,A,J,G,C,H,A,J,E,E,A,F,G,I,C,I,B,A,B,A,A,H,H,B,D,H,C,D,F,A,B,I,F,
A,C,J,J,E,A,B,A,J,B,H,H,A,A,E,G,A,F,A,B,I,J,B,I,F,G,F,H,H,C,G,E,I,E,E,H,H,C,F,B,C,D,J,E,J,C,C,B,B
,G,C,H,H,F,B,B,B,F,B,A,D,C,D,E,I,D,F,A,C,D,C,A,D,J,F,I,A,I,B,C,H,A,E,B,J,H,I,I,A,G,J,G,D,G,E,B,I,
J,I,B,E,A,I,F,C,G,E,I,D,J,D,D,A,J,C,E,J,B,C,J,H,J,F,E,D,E,B,H,A,F,C,F,E,C,C,A,H,D,B,J,A,G,I,C,F,E,
D,J,J,C,A,D,D,I,B,H,E,B,J,I,G,A,B,C,H,D,B,E,F,E,A,B,B,F,D,J,I,C,J,F,D,E,H,B,F,A,C,C,C,C,J,C,B,H,C
,H,C,A,I,J,F,E,E,I,G,E,A,C,E,D,G,G,A,F,G,I,C,J,F,D,D,J,G,C,E,I,E,H,C,B,A,I,H,G,G,G,H,G,J,D,E,C,E,
G,D,I,G,A,D,F,E,G,B,E,B,A,A,J,D,I,C,E,F,G,A,D,E,C,B,H,E,F,F,I,E,F,C,D,D,B,G,F,D,D,D,G,D,D,F,F,J
,A,F,A,G,A,D,I,I,D,I,F,H,E,H,I,I,D,H,E,C,C,A,I,H,J,D,A,B,E,G,J,J,G,C,J,A,H,F,J,E,H,D,H,H,E,H,F,D,
E,F,A,H,H,E,J,F,I,E,B,F,C,F,C,B,G,I,A,E,I,A,F,G,H,J,D,A,D,J,G,F,I,G,E,C,B,D,G,E,J,C,I,B,B,E,E,G,G,
B,B,J,E,G,J,H,G,G,C,I,E,H,I,D,C,A,J,C,G,A,H,A,A,A,E,A,F,G,I,J,H,C,J,I,H,G,F,I,H,B,D,F,D,B,A,A,I,H
,B,E,H,I,E,D,A,C,F,B,C,H,J,I,B,C,G,I,E,C,I,H,I,E,I,J,A,F,D,I,G,D,C,I,H,J,C,G,H,G,F,H,D,A,H,F,D,C,I
,F,F,J,J,J,F,J,F,A,E,F,D,I,H,D,H,B,G,J,F,D,F,C,G,E,E,A,C,J,B,F,C,D,G,A,J,E,A,H,B,C,H,J,E,I,G,F,J,J,J
,H,J,H,G,H,F,B,J,G,B,E,D,A,D,H,E,J,H,B,I,D,C,A,I,F,H,I,J,D,D,C,F,E,F,H,D,I,G,H,A,F,B,A,E,E,D,G,B
,G,J,B,B,D,D,B,I,C,I,J,I,B,E,G,G,G,D,F,H,F,B,G,B,F,C,F,F,A,G,F,H,B,D,E,C,E,J,H,J,A,H,D,H,D,H,H,
C,G,F,F,F,H,A,A,C,D,I,F,F,H,H,A,G,C,E,D,F,I,A,B,J,G,D,C,I,I,D,E,F,E,D,D,B,H,B,D,G,E,H,A,C,B,J,C,
H,F,G,J,D,H,F,E,J,E,E,J,H,E,E,F,J,E,F,I,C,C,G,G,A,D,H,F,J,B,F,I,I,A,H,D,A,E,G,H,F,F,J,D,F,J,A,G,H,
E,G,D,A,J,I,D,B,H,I,C,F,G,B,G,I,A,D,H,H,I,I,J,J,A,B,B,A,I,F,F,H,G,I,E,J,B,C,I,F,G,I,B,B,D,E,G,B,J,E
,B,I,D,C,C,D,G,G,J,J,G,H,F,B,J,B,I,C,J,G,I,A,G,D,C,H,F,F,J,C,G,A,B,A,G,G,B,G,C,E,C,A,B,H,C,B,H,
D,J,I,F,E,B,E,B,D,I,C,J,E,D,D,J,I,I,I,I,J,A,B,G,A,J,B,I,D,J

Применяем к этому прямоугольнику теорему 3.3, расширяем вниз на 10 строк добавлением классического латинского квадрата 10-го порядка и получаем решение С10N100, в котором 790 ошибок (ровно в 10 раз увеличилось количество ошибок при репликациях). Это решение показано выше.

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


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #628699 писал(а):
Это не описка? У вас в самом деле strong 10-coloring прямоугольник 100х10?
А почему 100х10, когда достаточно strong 10-coloring прямоугольника 90х10 для построения решения C10N100?
Если вы из прямоугольника 100х10 сделаете прямоугольник 90х10, в нём же может оказаться гораздо меньше ошибок.


Да описка. Я хотел сказать strong 90х10.

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


22/03/08

7154
Саратов
Значит, strong 10-coloring прямоугольники 90х10 у нас почти одинаковые (74 и 79 ошибок).
А что у вас с прямоугольником 85х10? Сейчас нашла в архиве свой, в нём 16 ошибок, получен из 85-символьной строки Pavlovsky.

Изображение

Код:

(Оффтоп)

Код:
10,85,A,A,B,A,C,D,E,B,C,A,A,B,F,F,D,E,B,C,A,G,F,F,C,D,E,B,C,A,G,G,A,C,D,E,B,C,F,G,G,H,C,D,E,
B,C,F,G,G,H,G,D,E,B,C,A,G,G,F,G,B,E,B,C,A,G,G,H,G,B,D,F,C,A,G,G,H,G,B,D,I,C,F,G,G,H,G,B,D,I,
H,A,G,G,H,G,B,D,I,H,B,G,G,H,G,B,D,I,H,B,G,G,H,G,B,D,I,A,B,G,E,H,G,B,D,F,H,B,G,E,E,G,B,D,I,H,
A,G,E,E,A,B,D,I,H,B,G,E,E,A,E,D,I,H,B,G,E,E,A,E,H,I,H,B,G,E,E,F,E,H,D,H,B,G,E,E,F,E,H,D,J,B,G,
E,E,A,E,H,D,J,A,G,E,E,A,E,H,D,J,A,H,E,E,A,E,H,D,J,A,H,E,E,F,E,H,D,J,F,F,E,I,A,E,H,D,J,F,H,E,I,I,E,
H,D,J,A,H,E,I,I,G,H,D,J,A,H,E,I,I,G,I,D,J,A,H,E,I,I,G,I,A,J,A,H,E,I,I,G,I,A,D,A,H,E,I,I,G,I,A,D,C,H,
E,I,I,G,I,F,D,C,G,E,I,I,G,I,F,D,C,G,A,I,I,G,I,A,D,C,G,A,I,I,G,I,A,D,C,G,A,I,J,G,I,A,D,C,G,F,I,J,J,I,A
,D,C,G,F,I,J,J,E,A,D,C,G,A,I,J,J,E,J,D,C,G,A,F,J,J,E,J,G,C,G,A,I,J,J,E,J,G,D,G,F,I,J,J,E,J,G,D,B,A,I,
J,J,E,J,G,D,B,E,I,J,J,E,J,G,D,B,E,G,J,J,E,J,G,D,B,E,G,J,J,E,J,G,D,A,E,G,J,C,E,J,G,D,B,E,G,J,C,C,J,G
,D,B,E,G,J,C,C,I,G,D,B,E,G,J,C,C,I,C,D,B,E,G,J,C,C,I,C,E,B,E,G,J,C,C,I,C,E,D,E,G,J,C,C,I,C,E,D,H,
G,J,C,C,I,C,E,D,H,I,J,C,C,I,C,E,D,H,I,E,C,C,I,C,E,D,H,I,E,C,C,I,C,E,D,H,I,E,C,F,I,C,E,D,H,I,E,C,B,
F,C,E,D,H,I,E,C,B,B,J,E,D,H,I,E,C,B,B,J,B,D,H,I,E,C,B,B,J,F,I,H,I,E,C,B,B,J,B,I,D,I,E,C,B,B,J,B,I,D
,A,E,C,B,B,J,B,I,D,A,J,C,B,B,J,B,I,D,A,J,I,F,B,J,B,F,D,F,J,I,B,F,J,B,I,D,F,J,I,B,H,J,B,I,D,A,J,I,B,H,H
,F,I,D,A,J,I,B,H,H,C,I,D,F,J,I,B,H,H,C,H,D,F,J,I,B,H,H,C,H,J,A,J,I,B,H,H,C,F,J,D,J,I,B,H,H,C,H,J,D,
G,I,B,H,H,C,H,J,D,G,C,F,H,H,C,H,J,D,G,C,J,H,H,C,H,J,D,G,C,J,H,H,C,H,J,D,G,C,J,H,A,C,H,J,D,G,C,
J,F,A,A,H,J,D,G,C,J,H,A,A,B,J,D,G,C,J,H,F,A,B,A,D,G,C,J,H,F,F,B,A,C,G,C,J,H,A,F,B,A,C,D,C,J,H,A,
A,A,F,C,D,E,J,H,A,A,B,F,C,D,E,B,H,F,F,B,A,C,D,E,F,C,B,A,A,F,F,B,D,F,B,C,A,F,A,C,F,A,A,H,A,F,D,D
,D,D,D,D,D,D,D,D,F,G,G,F,I,A,H,F,F,F,B,A,F,D,H,H,A,H,F,B

Если этот прямоугольник реплицировать, в решении 95х100 будет 160 ошибок. После удаления 5 лишних столбцов в решении 95х95 должно остаться меньше ошибок. Сейчас проделаю эту процедуру, посмотрю, сколько будет ошибок в решении 95х95.
Решение 94х94 у меня так и осталось с 28 ошибками, не удалось довести до ума :-(

Прямоугольник 86х10 я не искала.

Проделала процедуру, решение C10N95 получилось со 135 ошибками.

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


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #628746 писал(а):
А что у вас с прямоугольником 85х10? Сейчас нашла в архиве свой, в нём 16 ошибок, получен из 85-символьной строки Pavlovsky.


У меня не намного лучше. Самоё лучшие это strong 85х10 с 15 ошибками, которое даёт 95х95 с 135 ошибками. Самое лучшие C10N95 у меня имеет 54 ошибки.

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


22/03/08

7154
Саратов
"Потрясла" немного один из своих strong 10-coloring прямоугольников 84х10 с 4 ошибками (с добавлением одной строки), нашла strong 10-coloring прямоугольник 85х10 с 15 ошибками:

(Оффтоп)

Код:
10,85,F,A,E,I,B,B,F,A,D,G,E,A,H,G,D,H,B,D,E,I,A,A,A,B,I,J,H,G,C,D,H,A,I,J,F,A,A,H,A,C,I,A,F,A,H,
E,G,I,F,B,D,A,B,H,A,I,C,E,H,A,G,A,G,D,G,F,E,C,I,F,C,A,C,C,E,C,D,B,B,J,J,A,D,F,C,D,I,F,G,H,D,B,H
,D,F,D,F,B,C,B,C,B,G,J,D,E,I,G,H,G,H,B,E,F,H,G,D,J,I,A,I,B,C,B,A,F,B,A,G,E,E,B,J,A,B,I,H,C,A,J,F,
B,A,H,E,A,E,F,J,I,G,B,F,I,C,C,C,H,E,D,A,B,I,G,G,B,G,E,B,H,J,B,B,C,I,H,A,I,D,F,A,C,F,J,A,H,F,F,I,J,
E,J,A,F,G,E,C,B,D,E,D,J,E,G,E,F,I,I,A,D,H,J,C,I,D,D,H,E,F,F,G,J,B,A,F,B,D,G,G,I,F,C,G,B,C,I,A,D,B
,B,J,C,I,H,H,C,B,C,C,G,I,J,H,C,B,G,E,H,H,H,C,C,J,D,I,A,G,A,E,A,F,D,B,J,H,F,H,B,E,H,J,D,C,G,B,A,
C,G,I,B,A,D,H,I,E,E,A,C,G,A,E,D,F,H,F,J,I,A,B,F,G,D,E,C,D,I,J,F,C,E,D,D,G,F,I,B,B,H,J,J,I,D,A,D,C
,H,D,E,A,G,C,D,I,A,A,D,E,D,D,D,H,D,J,B,G,C,F,I,H,I,C,E,H,H,C,B,H,I,I,C,D,E,I,B,B,E,D,F,E,F,H,E,F
,D,E,I,B,G,D,H,G,E,J,G,A,G,A,B,F,G,J,E,A,I,F,F,G,D,H,J,B,E,C,A,G,H,I,H,C,A,E,E,E,E,I,C,E,E,G,B,I,
E,B,F,D,A,F,C,B,D,A,E,G,C,H,D,C,A,A,I,H,F,G,H,B,H,J,B,G,D,C,F,B,I,G,G,B,F,A,B,J,F,E,D,A,E,H,H,
B,I,A,F,C,F,J,I,E,I,E,G,D,F,A,A,D,C,A,A,I,H,E,F,I,C,C,F,F,G,J,A,F,F,F,G,I,D,D,C,H,E,I,F,J,E,E,B,C,D
,C,F,G,F,H,B,H,A,I,E,D,J,D,G,J,I,H,H,E,G,B,E,I,G,G,G,J,C,H,F,D,A,F,G,I,D,D,J,C,I,G,J,J,G,H,E,G,I,
D,A,F,D,A,G,E,A,C,A,B,B,H,F,H,G,A,C,A,B,I,C,E,B,C,G,F,F,B,F,A,E,C,I,G,G,C,H,I,E,F,D,A,H,E,G,B,
B,E,D,G,H,I,G,J,H,F,B,D,B,E,B,A,A,A,H,B,D,B,C,I,J,F,E,C,H,A,G,H,I,F,H,G,F,D,H,C,J,C,G,G,C,D,I,I,
H,E,H,G,D,A,G,E,J,E,H,G,I,A,A,D,I,C,H,G,H,I,F,E,H,H,A,H,B,F,H,J,C,F,E,B,E,I,D,H,H,H,A,I,F,C,F,B,
G,E,I,C,D,H,B,A,F,H,D,A,I,D,H,D,F,D,H,D,B,J,I,G,A,E,G,F,E,E,C,G,I,A,J,B,D,B,I,B,A,C,I,E,B,F,H,C,
C,F,H,D,I,F,C,G,A,H,J,G,G,H,I,B,G,C,E,E,A,C,J,B,I,H,F,A,C,J,G,A,F,I,I,I,I,I,I,I,B,I,I,B,C,D,E,F,G,H,
I,J,E,J,J,J,J,J,J,J,J,J,B,B,B,D,C,J,J,B,D,F,C,F,J,D,E,A,H,G,J,C,C

Сейчас реплицирую его, посмотрю, какое получится решение C10N95.

Далее в продолжение моей гипотезы: если не существует strong 10-coloring прямоугольник 84х10, то не существует и strong 10-coloring прямоугольник 85х10.
Найденный strong 10-coloring прямоугольник 85х10 тоже можно превратить в прямоугольник с "дырками", которому будет соответствовать набор из 10 попарно ортогональных обобщённых латинских прямоугольников 9х10 с неполной последней строкой (но уже в последней строке содержится 5 элементов!) и с несколькими пустыми ячейками, соответствующими "дыркам".

Реплицировала прямоугольник 85х10, решение C10N95 получилось со 130 ошибками.

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


22/03/08

7154
Саратов
На решения C10N94 я смотрела сразу же, как открыли БД конкурса. Сейчас ещё раз посмотрела эти решения, более внимательно.
Интересный момент (кажется, я это уже отмечала, не помню точно): ни из одного решения мне не удалось выделить strong 10-coloring прямоугольник 84х10 без ошибок.
Такие получились прямоугольники:

dimkadimon - 40 ошибок
Nik - 45 ошибок
kfb - 396 ошибок
Zealint - 529 ошибок

Далее весьма любопытным показалось решение Zealint

(Оффтоп)

Изображение


У меня такое впечатление (может быть, ошибочное): это решение построено матричным методом, причём базовая матрица имеет размер 9х8, то есть она не квадратная, а прямоугольная! По заполнении матрицы блоками получено решение 90х80; затем добавлено обрамление, получено решение 100х90; потом справа добавлено 4 столбца, а снизу 6 строк удалено (хорошо видно обрезанное снизу обрамление); ну, и ещё участвовало "вытряхивание" ошибок.

Pavlovsky
вы не пробовали искать прямоугольные базовые матрицы?
К найденной вами базовой матрице 8х8 для С=10 наверняка можно добавить ещё одну строку.

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


22/03/08

7154
Саратов
Цитата:
Циклический ЛК 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

Это пример, выложенный в теме Pavlovsky (стр. 93).
Здесь получается решение C10N90.

(Оффтоп)

Изображение


Со временем это будет классический пример матричного метода для С=10. В свою книгу, конечно, этот пример включила (глава 7, которая ещё не выложена).

А теперь по поводу регулярных и нерегулярных решений.
Возьмём показанное выше решение C10N94 Zealint, удалим в нём 4 строки и 4 столбца (любые) и получим решение C10N90.

Сравните эти два решения C10N90! Разницу чувствуете?
Данное мной здесь определение регулярных решений было названо глупым. Не глупое определение я пока не видела нигде.
Так вот, я утверждаю, что решение Pavlovsky регулярное, а решение Zealint нерегулярное. Есть другие мнения?
Да, в построении решения Pavlovsky тоже присутствует перебор - перебором найдена базовая матрица 8х8. Но! Это решение построено по строгому, чёткому алгоритму. Никакого "вытряхивания" ошибок здесь нет. Посмотрите на это решение. Гармония и красота!

То же самое можно сказать о диагональных решениях - эти решения регулярные. Да, перебор присутствует. Но есть некая идея - идея диагональности. Для этой идеи разработан алгоритм, в котором присутствует перебор. Для строго диагональных решений, например, решения строятся по CDS. Это один из алгоритмов, есть другой вариант - без CDS. Не строго диагональные решения строятся по другому алгоритму: поиск базовой строки длины 2N-1, которая должна удовлетворять определённым условиям. Найдя базовую строку, мы по ней строим само диагональное решение.

Набрать много баллов и занять высокое место - это, конечно, хорошо. Но... мне больше по душе красивые идеи, реализованные в красивые алгоритмы. Уважаю тех конкурсантов, кто не гонится за баллами, а работает "на идею". Большая удача, если работа "на идею" приносит и хорошие баллы, как это случилось, например, у alexBlack.
А вот Tom Sirgedas работал "на идею", но, по его собственному признанию, полезных для конкурса решений не нашёл. Ну и пусть! Зато у него есть замечательные результаты, которые помогут в дальнейшем исследователям данной задачи. Например, его квадраты, заполненные единичками.
Уверена: если бы Том включил программу отжига и непрерывно крутил её неделями, он бы тоже занял высокое место.

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


22/03/08

7154
Саратов
Очень заинтересовало решение первого класса C10N91 (автор Anton Voropaev)

(Оффтоп)

Изображение

Хотелось бы узнать как построено. Матричный метод?
К сожалению, Антон где-то далеко-далеко от этой темы :D

Сравните с моим решением C10N91, представленным на конкурсе:

(Оффтоп)

Изображение

Алгоритм построения этого решения и всех подобных решений первого класса подробно описала в главе 7. Это регулярное решение, здесь вообще нет никакого перебора. Данный алгоритм я нашла с большим трудом; когда додумалась, всё оказалось очень просто и красиво.

Кстати, вот этого моего решения в БД конкурса уже нет, так как там остались только максимальные решения каждого участника. Что, наверное, не есть хорошо :-)

-- Ср окт 10, 2012 21:23:08 --

И ещё одно решение очень занимательное - C10N93 (автор Ярослав Вроблевский):

(Оффтоп)

Изображение

Тоже матричный метод? Хорошо видно внизу обрезанное обрамление.

Как видим, многие конкурсанты в решениях для С=10 искали аналог конечного поля.
Другая часть конкурсантов шла от 10-сильных прямоугольников. К этой части отношусь и я.
Моё решение C10N93 можно посмотреть в БД конкурса. У меня для С=10 это максимальное решение.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 124, 125, 126, 127, 128, 129, 130  След.

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



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

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


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

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