2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 98, 99, 100, 101, 102, 103, 104 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение04.09.2012, 07:28 


26/01/10
959
Nataly-Mak в сообщении #614562 писал(а):
Он же сам признаётся: не знает, что такое регулярные решения.

Ну так и Вы не знаете : ) А когда Вам на это указывают, начинаете негодовать. Верный признак непонимания или нежелания разобраться. Ладно, как хотите; что мне нужно, я выяснил.

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


01/06/12
970
Adelaide, Australia
Nataly-Mak в сообщении #614380 писал(а):
dimkadimon
скажите, пожалуйста, вы получили 10-сильный прямоугольник 84х10?
Или вы достраивали большие квадраты 10-coloring, то есть от квадрата 92х92 к квадрату 93х93, потом к 94х94?
Помнится, вы писали давно, что нашли решение 94х94, а вот 10-сильный прямоугольник 84х10 не нашли. Хочу ещё раз уточнить.

Меня интересует, есть ли у вас опровержение моей гипотезы, что не существует 10-сильный прямоугольник 84х10.


Уточняю ещё раз. Я не получал сильную раскраску 84х10. Она может существовать, а может не существовать. На даный момент нет доказательств ни в одну и ни в другую сторону. Я получил 94х94 от 85-строчки Pavlovsky.

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


22/03/08

7154
Саратов
dimkadimon
спасибо за уточнение.

А у вас есть 10-сильный прямоугольник 84х10 с ошибками?

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


01/06/12
970
Adelaide, Australia
Nataly-Mak в сообщении #614572 писал(а):
dimkadimon
спасибо за уточнение.

А у вас есть 10-сильный прямоугольник 84х10 с ошибками?


Есть, но в нём тоже 4 ошибки:

(Оффтоп)

6,1,2,1,3,4,5,2,5,1,
1,2,1,3,4,5,4,3,1,10,
2,1,3,4,5,2,3,1,10,2,
1,3,6,5,2,3,6,10,10,7,
3,4,5,10,3,6,10,10,7,10,
4,5,2,3,9,10,10,6,10,6,
5,2,3,1,6,10,7,10,2,4,
2,3,1,6,6,7,10,2,4,8,
3,1,10,6,7,10,2,4,3,7,
1,10,10,7,6,2,1,8,7,6,
10,10,7,6,2,4,8,7,2,10,
10,7,10,10,4,8,7,2,10,5,
7,10,2,4,8,7,2,10,6,5,
10,2,6,8,7,2,10,5,6,1,
2,4,8,7,2,10,5,5,1,5,
4,8,7,10,6,5,5,1,6,7,
8,7,2,6,10,5,6,5,7,4,
7,2,10,5,10,6,5,7,4,9,
2,10,4,5,9,5,7,4,9,1,
10,5,5,1,5,7,1,9,1,7,
5,5,1,5,7,4,9,1,7,5,
5,1,4,7,4,9,6,7,6,8,
1,5,7,4,1,6,7,5,8,8,
5,7,6,9,9,7,5,8,8,10,
7,4,9,1,7,5,8,8,10,8,
4,9,1,7,10,8,8,10,8,1,
9,1,7,5,8,8,10,8,1,4,
1,7,4,8,8,10,8,1,4,3,
7,5,8,8,6,8,6,4,5,10,
5,6,8,6,8,6,1,3,10,1,
8,8,10,8,9,4,3,10,1,8,
8,10,8,1,4,1,10,1,8,9,
10,6,1,4,3,10,6,8,9,9,
8,1,6,3,6,6,8,9,9,5,
6,4,3,6,9,8,9,9,6,9,
4,3,10,1,8,9,9,5,9,2,
3,10,1,8,1,9,5,9,10,4,
10,1,8,9,1,5,9,10,4,6,
1,8,9,9,5,9,10,4,2,5,
8,9,9,5,1,10,1,2,6,2,
9,9,4,9,6,4,2,5,10,9,
9,5,9,6,4,2,5,10,9,3,
5,9,10,4,2,5,10,9,5,3,
9,10,6,10,10,10,9,3,5,8,
10,4,2,5,6,9,3,3,8,3,
4,2,4,6,1,3,3,8,5,5,
2,5,10,9,3,1,8,3,6,4,
5,10,9,3,3,8,3,5,4,7,
10,9,3,3,8,1,5,4,7,8,
9,3,3,8,3,5,1,7,8,5,
3,3,8,3,10,4,7,8,6,3,
3,8,3,5,4,7,8,5,5,6,
8,3,5,4,7,8,5,3,2,6,
3,5,6,7,8,5,3,2,2,9,
5,4,7,8,10,3,2,2,9,6,
4,7,8,5,3,2,2,9,2,8,
7,8,5,3,2,2,9,2,8,4,
8,5,3,10,2,9,2,8,4,1,
5,3,2,10,1,2,8,4,1,9,
3,2,2,9,2,8,1,1,9,8,
2,2,9,10,8,4,6,9,8,6,
2,9,2,8,4,6,9,8,2,7,
9,2,8,4,9,9,8,2,7,7,
2,8,6,1,1,8,4,7,7,3,
8,4,1,9,8,2,7,6,5,7,
4,1,9,8,2,7,7,3,7,9,
6,9,8,10,7,7,3,7,9,4,
9,8,2,7,7,3,7,9,4,2,
8,2,7,7,3,7,9,4,10,3,
2,7,7,3,7,9,1,10,5,9,
7,7,3,7,1,4,10,3,9,7,
7,3,7,9,4,10,3,9,7,1,
3,7,9,4,6,3,9,7,1,1,
7,9,6,6,3,9,7,1,1,6,
9,4,10,3,1,7,6,1,2,1,
4,10,3,9,7,6,6,2,1,3,
10,3,9,7,9,6,4,1,3,4,
3,9,7,1,9,2,6,3,4,5,
9,7,1,1,2,6,3,4,6,6,
7,1,1,10,9,3,1,5,2,3,
6,6,10,2,5,3,4,6,8,8,
4,4,6,2,4,4,1,4,4,4,
1,6,5,2,9,1,2,7,5,2,
6,8,4,4,10,1,1,6,3,10

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


22/03/08

7154
Саратов
Да, любопытно, существует ли такой прямоугольник.
Я пробовала искать от самых разных исходных прямоугольников, н-и-ч-е-г-о! Меньше 4 ошибок получить не удалось.

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


01/06/12
970
Adelaide, Australia
Nataly-Mak в сообщении #614642 писал(а):
Да, любопытно, существует ли такой прямоугольник.
Я пробовала искать от самых разных исходных прямоугольников, н-и-ч-е-г-о! Меньше 4 ошибок получить не удалось.

А зачем он вам? Решение 94х94 все равно уже нашли.

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


22/03/08

7154
Саратов
Научный интерес :D

Там получается интересный набор из 10 латинских прямоугольников 9х10 с неполной последней строкой. Вот сделать эти прямоугольники попарно ортогональными равносильно задаче нахождения 10-сильного прямоугольника 84х10.

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


01/06/12
970
Adelaide, Australia
Друзья, я сегодня нашёл C15N198! Значит всё таки можно улучшить старые решения. Как только Нейл откроет доступ к сайту я его выложу.

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


22/03/08

7154
Саратов
dimkadimon в сообщении #614952 писал(а):
Друзья, я сегодня нашёл C15N198!

Здорово! Поздравляю!

Конечно, улучшить можно, я в этом нисколько не сомневаюсь.
Думаю, что и 198х198 не предел.

Меня вот очень интересует метод, который здесь был показан Pavlovsky. Этот метод описан и в статье alexBlack.
Базовые матрицы и блоки, которыми эти базовые матрицы заполняются.

Но меня смущают некоторые расхождения в описании метода Pavlovsky и alexBlack.
Например, первое расхождение:
Pavlovsky пишет, что все элементы в базовой матрице (кроме первой строки и первого столбца) должны быть различны. У alexBlack этого условия нет.

Далее, Pavlovsky приводит ещё одно условие, которому должны удовлетворять элементы базовой матрицы:
A+D-B-C <>0 (mod N).
У alexBlack этого условия нет.

В статье alexBlack написано, что для С=6 было найдено 10 базовых матриц 5х5, что даёт решение C6N36.
Для С=10 тоже удалось сделать полный перебор, максимальная базовая матрица 8х8, что даёт решение C10N90.
Такой же результат получил и Pavlovsky.

А вот какую максимальную базовую матрицу можно получить этим методом для С=15 :?:

Матрица 12х12 дала бы решение C15N195, это уже не актуально.
Матрица 13х13 дала бы решение C15N210 :!:

Но вот возможна ли матрица 13х13 :?:

[Конечно, в этом случае перебор будет огромным, но можно решать задачу вместе. Есть уже хороший пример в Рунете - распределённые вычисления. Силы у нас большие. Стоит только захотеть!]

Кроме того, метод допускает расширение.
Всё описанное выше рассматривалось в предположении, что блоки (в терминологии Pavlovsky - унитарные латинские квадраты) составляются одинаково, а именно: циклическим сдвигом.
Но! У нас есть пример этого же метода в применении к С=8,9 и другим степеням простых, когда блоки составляются иначе, а базовая матрица суть таблица умножения.
Почему бы и для С=15 не попробовать другой способ составления блоков?

[Знаю, что для С=15 не существуют таблицы сложения и умножения.
Вместе с тем, ничто не мешает нам по-другому составлять блоки и для этих блоков искать базовую матрицу. Я не знаю, как именно "по-другому", надо думать.]

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


21/02/10
1594
Екатеринбург
Может кому будет интересно. Алгоритм получения решений третьего класса. С помощью этого алгоритма получены все мои решения в конкурсе.
Берем за основу сильно окрашенный прямоугольник размером (С^2)х(С+1), заполненный С цветами. Для получения решения третьего класса надо добавить две строки, так что бы свойство сильноокрашенности сохранилось. При этом используется дополнительный цвет С+1. Одна строка очевидна - строка заполненная цветом С+1.
Долго безуспешно пытался добавить еще одну строку. Пока не понял в чем проблема. Исходный прямоугольник формировал стандартным образом, так что в нем появлялись длинные одноцветные строки. Когда понял, что они мешают, проблема была легко решена.

Пример для С=5. Красным выделены ячейки, которые надо заменить на число 6.
Изображение

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #615079 писал(а):
Долго безуспешно пытался добавить еще одну строку. Пока не понял в чем проблема. Исходный прямоугольник формировал стандартным образом, так что в нем появлялись длинные одноцветные строки. Когда понял, что они мешают, проблема была легко решена.

А я брала стандартный прямоугольник, мне длинные одноцветные строки нисколько не помешали.

Пример
исходный прямоугольник 9-сильный 81х10, результат - добавлено две строки и один цвет, 10-сильный прямоугольник 83х10:

Изображение

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


21/02/10
1594
Екатеринбург
Покритикуйте плиз качество гуглоперевода.
Цитата:
Description of the algorithm used to obtain all of my solutions in the current competition.
Is taken as the starting C-strong-colored rectangle (C^2)x(C+1). You need to add two lines, so that the property would C-strong-colored preserved. One line is obvious - the string filled with color C+1.

Long tried unsuccessfully to add another line. Until I realized what the problem is. Original rectangle formed in the standard way, so that it appeared the long-color line. When he realized that they were in the way, the problem was easily solved.

Example for C = 5.
http://www.imageup.ru/img221/1034993/plyusodin.jpg
Red color of the cell in which it is necessary to write the number 6.

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


22/03/08

7154
Саратов
Так переводит сам Гугл :D

Цитата:
Длинные безуспешно пытался добавить еще одну строку. Пока я не понял, в чем проблема. Оригинальный прямоугольника, образованного стандартным способом, так, что она появилась в долгосрочной цвет линии. Когда он понял, что они были в пути, эта проблема легко решается.

Я уже насобачилась переводить туда-сюда :-)
Раз этак десять переведу туда-сюда, вроде сносно получается.

Значит так: сначала перевожу свой текст на английский, потом этот английский текст скармливаю Гуглу опять же и перевожу его на русский. Если что-то очень плохо выглядит, тогда делаю изменения в оригинальном русском тексте и снова всё повторяю.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение05.09.2012, 15:54 
Заслуженный участник


04/05/09
4526
Pavlovsky в сообщении #615116 писал(а):
Покритикуйте плиз качество гуглоперевода.

Ужасно. Без оригинала на русском понять практически невозможно.
Немножко поправил, чтобы смысл появился (стилистику ещё бы поправить тоже):

The algorithm I used to obtain all of my solutions in the current competition.
Take a C-strong-colored rectangle (C^2)x(C+1) as a starting grid. Then you need to add two lines so that the property of C-strong-colored is preserved. One line is obvious - it's a string filled with color C+1.

I've tried a long time to add another line without success, until I realized what was the problem - the original rectangle is formed in the standard way so it contains long single-color lines. When I realized that they were in the way the problem was easily solved.

Here is an example for C = 5.
Изображение
The cells that need to be replaced with number 6 are colored red.

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


21/02/10
1594
Екатеринбург
venco Большое спасибо. Согласен, над стилистикой надо поработать. Уж слишком сложные предложения получились. Надо их сделать проще и понятнее. Но увы сам я это не осилию. Я как та собачка все понимаю, но сказать не могу. :-)

PS Еще немного подожду и отправлю как есть.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 98, 99, 100, 101, 102, 103, 104 ... 130  След.

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



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

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


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

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