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



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

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


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

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