2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 33, 34, 35, 36, 37, 38, 39 ... 192  След.
 
 
Сообщение19.03.2009, 07:10 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
tolstopuz
не оставляйте меня, пожалуйста, с катушек слечу :P
Говорят, что если долго мучиться, что-нибудь получится. Я вчера целый день мучилась, но ничего не получилось.
Решала задачу добавления к приведённой выше квази-разностной матрице из 3-х строк четвёртой строки, чтобы получить ортогональный соквадрат 18-го порядка в пару к построенному. Задачу решала подбором. Конечно, по-хорошему, нужна программа...
Подбор шёл долго! Мне удалось добавить строку, но, увы, она оказалась несовместимой с тремя имеющимися строками и поэтому, понятно, квадрат оказался не ортогональным первому квадрату. Вот какая у меня получилась матрица:
Код:
a 11 1 1 b 9 1 2 c 13 8 10 12 5 8 3 7 6 15 4 14
11 a 1 2 9 b 8 1 13 c 1 12 10 8 5 7 3 15 6 14 4
1 1 a 1 1 1 b 1 1 1 c 1 1 1 1 1 1 1 1 1 1
12 14 1 a 15 14 7 b 8 9 10 c 13 4 12 15 1 4 8 11 9

Критерий совместимости строк действительно не выполняется. Зато, представьте, насколько я в это проникла, добавляя четвёртую строку.
Затем пошла по указанной выше ссылке и нашла там пару ОЛК 18-го порядка, тоже состоящую из латинских квадратов, содержащих подквадрат 3х3. Очень интересно! Сразу составила эту пару по приведённой матрице. Первый квадрат в этой паре имеет похожую на мой квадрат структуру, одна главная диагональ (в подквадрате 15х15) тоже состоит из одинакового элемента (одной переменной). Только вот симметричности нет. Я немного преобразовала квази-разностную матрицу этой пары, сделала из неё изоморфную матрицу. Вот она:
Код:
a 6 1 4 b 11 6 14 c 12 15 7 10 13 1 3 9 2 5 15 8
5 a 1 6 9 b 2 15 1 c 5 10 14 4 8 11 3 12 2 13 7
1 1 a 1 1 1 b 1 1 1 c 1 1 1 1 1 1 1 1 1 1
4 11 12 3 13 2 8 a 8 15 10 5 14 b 1 12 6 10 c 7 9

Чертовски похожа эта матрица на мою матрицу! Только в этой матрице все строки совместимы по приведённому выше критерию. Неужели к моему квадрату не удастся построить ортогональный соквадрат? Может быть, кто-нибудь поможет составить программу для добавления к матрице четвёртой строки. Алгоритм ведь абсолютно прозрачен. А у меня уже просто сил нет, совсем вчера измучилась с этим подбором, надо было сразу писать программу.
Понятно, что если моя пара ОЛК будет получена, она будет неизоморфна показанной паре ОЛК.
Да, так вот, значит, получается, что пара ОЛК 18-го порядка из латинских квадратов с подквадратом 3х3 известна, пара ОЛК из латинских квадратов с подквадратом 4х4 тоже известна. А вот пара ОЛК из латинских квадратов с подквадратом 5х5 (какую я построила) известна? Если кто-то найдёт такую пару, покажите, пожалуйста. Очень интересно будет сравнить с моей парой, изоморфны или нет.

 Профиль  
                  
 
 
Сообщение19.03.2009, 14:11 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
А с подквадратом 1х1 есть пара ОЛК 18-го порядка? Вот, например, у Тодорова группа MOLS 14-го порядка состоит из латинских квадратов с подквадратом 1х1, то есть квази-разностная матрица этой группы содержит одну переменную (прочерк).
Листаю свои черновики и нахожу схему, которую я разработала месяца два назад для построения латинского квадрата любого чётного порядка $n = 2k, k>1$ (тогда я ещё ничего не знала о квази-разностных матрицах). И вот чудеса: эта схема как раз соответствует квази-разностной матрице с одной переменной. Вот, например, покажу квази-разностные матрицы для порядков 4 и 8.
Код:
a 0 0 0 0
0 a 1 0 2
1 2 a 0 1

Код:
a 0 0 0 0 0 0 0 0
0 a 3 0 1 2 4 5 6
1 4 a 0 6 5 3 2 1

По этим матрицам вы без труда построите один латинский квадрат порядка 4 и порядка 8.
А теперь ставим задачу: для каждого порядка указанной серии к построенной таким образом квази-разностной матрице добавить четвёртую строку, которая должна удовлетворять приведённому пользователем tolstopuz критерию. Если это удастся сделать, то добавленная четвёртая строка определит ортогональный соквадрат. Для порядка $n = 4$ у меня это получилось с ходу. Вот какая получилась квази-разностная матрица с добавленной четвёртой строкой:
Код:
a 0 0 0 0
0 a 1 0 2
1 2 a 0 1
0 2 0 1 a

По этой матрице получается пара ОЛК 4-го порядка.
Понятно, что порядок 6 пропускаем, потому что для него не существует ни одной пары ОЛК (хотя один латинский квадрат по этой схеме тоже строится). Следующий порядок 8. Тут уже с ходу ничего нельзя решить; подбором, как я вчера с квадратом 18-го порядка провозилась целый день, очень не эффективно действовать. Надо составить программу, которая в миг определит, возможно или невозможно добавление к имеющейся квази-разностной матрице четвёртой строки.
А вот если это вдруг сработает, то представьте, какой мы будем иметь простой алгоритм построения пары ОЛК любого чётного порядка, кроме, разумеется, 2 и 6. Только вряд ли для всех порядков сработает. Но надо проверить, а вдруг... Может быть, для какой-то подгруппы указанной группы порядков удастся такую схему применить. Неужели только для порядка 4 работает?
Однако, задач я тут много предложила, да решать их почему-то никто не желает :?

 Профиль  
                  
 
 
Сообщение20.03.2009, 16:14 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Изложила все свои мысли по поводу построения пар ОЛК чётного порядка по квази-разностной матрице в статье "Побробно о квази-разностной матрице". Написана только первая часть статьи, продолжение следует.
Жду критических замечаний, вопросов и ответов на вопросы статьи.

 Профиль  
                  
 
 
Сообщение22.03.2009, 23:09 
Заслуженный участник


31/12/05
1102
Nataly-Mak писал(а):
Задачу решала подбором. Конечно, по-хорошему, нужна программа...
Для порядка 18, думаю, программа будет работать разумное время. Только вот больше пяти строк в матрице все равно не получится, так что улучшить рекорд таким способом не выйдет.
Nataly-Mak писал(а):
Подбор шёл долго! Мне удалось добавить строку, но, увы, она оказалась несовместимой с тремя имеющимися строками
Значит, не удалось :)
Nataly-Mak писал(а):
Надо составить программу, которая в миг определит, возможно или невозможно добавление к имеющейся квази-разностной матрице четвёртой строки.
Это "вмиг" будет экспоненциально расти с увеличением порядка. Поэтому в статье "The Existence of N_2 Resolvable Latin Squares" так сделали только для шестнадцати порядков (более того, для большинства из них используют дополнительные симметрии типа циклических сдвигов, чтобы сэкономить время), а для остальных занимаются какой-то хитрой склейкой из меньших порядков, в которой я еще не разбирался.
Nataly-Mak писал(а):
Жду критических замечаний, вопросов и ответов на вопросы статьи.
Я особо не вникал, но рис.33 вполне логичен. Но я не уверен, что без дополнительных соображений можно построить таким перебором в лоб пару квадратов порядка 86, даже с использованием циклических сдвигов.

 Профиль  
                  
 
 
Сообщение23.03.2009, 08:08 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
В моей статье (после рис. 33) написано следующее:
"Понятно, что с ростом порядка выполнение такой программы проблематично (по времени выполнения). Именно поэтому необходимо теоретическое доказательство действия приведённого алгоритма для любого чётного порядка (кроме 2 и 6)".
Я вполне понимаю, что с ростом порядка такая программа будет работать год или два :)
Меня интересует принцип алгоритма, заложенный в рис. 33. Предлагается доказать его действие для любого порядка. Или наоборот доказать, что он не работает для всех порядков. Это возможно сделать?
Далее о статье, которую вы приводите. Несмотря на то, что "читать" не умею (кстати, какая свеженькая статья, июль 2008 г), я просмотрела статью, подробно изучила все приложения, поняла о каких латинских квадратах $N_2$ идёт речь в статье. У меня такой вопрос: что говорится в статье о латинских квадратах порядка $n = 4k, k>2$? Почему ортогональных латинских квадратов таких порядков (12, 20, 24) нет в Приложениях (порядки 16 и 32 относятся к группе порядков, являющихся степенью числа 2)? Я построила пару ОЛК 12-го порядка из латинских квадратов, содержащих подквадрат 3-го порядка. (Кстати вся коллекция таких пар ОЛК приведена во второй чаcти моей статьи "Подробно о квази-разностной матрице")
Правда, не исследовала латинские квадраты этой своей пары на предмет того, являются ли они квадратами $N_2$. Ведь для этого надо переставлять всевозможным образом строки и столбцы в латинских квадратах, так сразу подквадратов 2х2 я не увидела в этих латинских квадратах. Однако авторы статьи говорят, что такие пары ОЛК существуют для всех чётных порядков, кроме 2, 4, 6 и 8. Так что же с чётно-чётными порядками? Почему их нет в Приложениях? Не просто же так они пропущены? Как-то нелогично при демонстрации сразу, в самом начале, делать пропуски, показывать порядок 10, а потом сразу порядок 14 (пропуская порядок 12), потом 16, 18 и 22 (пропуская порядок 20).
Я не говорю в этом своём методе о рекорде для порядка 18. В статье речь идёт об алгоритме построения пар ОЛК.
Кстати, о методе авторов статьи. О "хитрой" склейке я тоже видела, для порядка 202, в самом конце Приложений. Если это действительно общий метод построения пар ОЛК любого чётного порядка (кроме 2, 4, 6 и 8) (в указанной вами статье), то можно по этому методу сразу построить пару ОЛК любого порядка. Более того, алгоритм можно формализовать и запрограммировать. Вот тогда можно сказать, что это общий метод построения.
Спасибо вам за ответ! Только вами и дышу :wink:
P.S. Да, а рекорд для порядка 18 можно планировать как раз в рис. 33. Правильно? В этой квази-разностной матрице получится добавить больше пяти строк? Кстати, мне нигде не встречалась пара ОЛК 18-го порядка, состоящая из латинских квадратов с подквадратом 1х1. Известны с подквадратами 3х3, 4х4, 5х5 (мой вариант), а вот с подквадратом 1х1 не видела. Если кто найдёт такую пару ОЛК 18-го порядка, покажите. Я тогда вставлю в свою схематичную квази-разностную матрицу (рис. 33) ещё две строки, напишу программу для добавления следующих строк и получу рекорд :P А пока можно "плясать" в этом методе только от трёх строк в этой квази-разностной матрице.
Как вы думаете, tolstopuz, сработает?

Добавлено спустя 1 час 51 минуту 19 секунд:

Точно! Сейчас переставила столбцы в латинских квадратах своей пары ОЛК 12-го порядка, и в первом латинском квадрате получила подквадраты 2х2. Вот эта пара ОЛК.
Код:
1 0 10 11 9 2 4 3 8 6 5 7
9 2 0 10 11 1 3 4 7 5 6 8
8 1 3 0 10 11 2 5 6 4 7 9
7 9 2 4 0 10 11 6 5 3 8 1
6 8 1 3 5 0 10 7 4 11 9 2
5 7 9 2 4 6 0 8 11 10 1 3
11 6 8 1 3 5 7 9 10 0 2 4
10 11 7 9 2 4 6 1 0 8 3 5
0 10 11 8 1 3 5 2 9 7 4 6
4 5 6 7 8 9 1 0 3 2 10 11
3 4 5 6 7 8 9 11 2 1 0 10
2 3 4 5 6 7 8 10 1 9 11 0

Код:
1 9 8 7 6 5 11 4 0 10 3 2
0 2 1 9 8 7 6 5 10 11 4 3
10 0 3 2 1 9 8 6 11 7 5 4
11 10 0 4 3 2 1 7 8 9 6 5
9 11 10 0 5 4 3 8 1 2 7 6
2 1 11 10 0 6 5 9 3 4 8 7
4 3 2 11 10 0 7 1 5 6 9 8
6 5 4 3 11 10 0 2 7 8 1 9
8 7 6 5 4 11 10 3 9 0 2 1
3 4 5 6 7 8 9 10 2 1 11 0
5 6 7 8 9 1 2 11 4 3 0 10
7 8 9 1 2 3 4 0 6 5 10 11

Так как же с ортогональными латинскими квадратами $N_2$ чётно-чётного порядка в указанной статье? Они существуют или нет? Или я что-то не так поняла насчёт квадратов $N_2$? Я поняла так, что это такие латинские квадраты, в которых не содержится латинских подквадратов 2х2. Правильно?

 Профиль  
                  
 
 
Сообщение23.03.2009, 10:54 
Заслуженный участник


31/12/05
1102
Nataly-Mak писал(а):
У меня такой вопрос: что говорится в статье о латинских квадратах порядка $n = 4k, k>2$?
Степени двойки, начиная с 64, - лемма 5.1. Все прочие четно-четные порядки - теорема 5.2. Но они опираются на построения из разделов 3 и 4, так что вам все равно придется ждать, пока я найду время и либо изложу конструктивную часть статьи (без доказательств) по-русски популярно, либо сам напишу программу, делающую все эти построения для любого порядка. Для этого мне надо найти как минимум пару дней свободного времени, когда это случится - пока не знаю.
Nataly-Mak писал(а):
Если это действительно общий метод построения пар ОЛК любого чётного порядка
Нет, общий метод - это теорема 5.6, которая для четно-нечетных порядков пользуется леммой 4.1.

 Профиль  
                  
 
 
Сообщение23.03.2009, 11:28 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ждать готова, мне торопиться некуда :)
Только вот очень жаль, что другие участники форума совсем не участвуют в обсуждении этой темы. А ведь могли бы! Глядишь, и помогли бы.
shwedka, к вам просьба: не могли бы вы пополнить мой набор статей об ортогональных ЛК? Всё, что вы мне прислали, я почти изучила. Вот меня интересуют конкретно статьи о построении пар ОЛК, состоящих из диагональных ЛК. Есть ли такие (кроме известной статьи Брауна о парах ОЛК 10-го порядка)? Нет ли чего-нибудь "свежее" той статьи, о которой сказал tolstopuz (о построении пар ОЛК любого чётного порядка)? Заранее благодарна.

 Профиль  
                  
 
 
Сообщение23.03.2009, 19:21 
Заслуженный участник


31/12/05
1102
Начнем понемногу. Если не считать нечетные порядки за тривиальностью, алгоритм для четно-четно-нечетных квадратов (порядки 12, 20, 28 и т. д.) на стр. 6 самый простой. Квадраты разбиваются на 16 блоков:
Код:
0H 1A 2B 3D   0B 1D 2C 3A
1D 0A 3H 2B   3B 2C 1A 0D
2B 3A 0D 1H   1C 0D 3A 2A
3C 2H 1C 0C   2A 3A 0B 1A

Цифра умножается на четверть порядка квадрата и прибавляется к каждому элементу матрицы, соответствующей букве. Матрицы легче всего показать на примере для порядка 20:
Код:
A 0 1 2 3 4 B 0 4 3 2 1 C 0 4 3 2 1 D 0 1 2 3 4 E 1 2 3 4 0 F 1 0 4 3 2 G 1 0 4 3 2 H 1 2 3 4 0
  1 2 3 4 0   4 3 2 1 0   1 0 4 3 2   4 0 1 2 3   2 3 4 0 1   0 4 3 2 1   2 1 0 4 3   0 1 2 3 4
  2 3 4 0 1   3 2 1 0 4   2 1 0 4 3   3 4 0 1 2   3 4 0 1 2   4 3 2 1 0   3 2 1 0 4   4 0 1 2 3
  3 4 0 1 2   2 1 0 4 3   3 2 1 0 4   2 3 4 0 1   4 0 1 2 3   3 2 1 0 4   4 3 2 1 0   3 4 0 1 2
  4 0 1 2 3   1 0 4 3 2   4 3 2 1 0   1 2 3 4 0   0 1 2 3 4   2 1 0 4 3   0 4 3 2 1   2 3 4 0 1

Вот результат для порядка 12:
Код:
1  2  0  3  4  5  6  8  7  9 10 11
0  1  2  4  5  3  8  7  6 11  9 10
2  0  1  5  3  4  7  6  8 10 11  9
3  4  5  0  1  2 10 11  9  6  8  7
5  3  4  1  2  0  9 10 11  8  7  6
4  5  3  2  0  1 11  9 10  7  6  8
6  8  7  9 10 11  0  1  2  4  5  3
8  7  6 10 11  9  2  0  1  3  4  5
7  6  8 11  9 10  1  2  0  5  3  4
9 11 10  7  8  6  3  5  4  0  2  1
10  9 11  6  7  8  4  3  5  1  0  2
11 10  9  8  6  7  5  4  3  2  1  0

0  2  1  3  4  5  6  8  7  9 10 11
2  1  0  5  3  4  7  6  8 10 11  9
1  0  2  4  5  3  8  7  6 11  9 10
9 11 10  6  8  7  3  4  5  0  1  2
11 10  9  7  6  8  4  5  3  2  0  1
10  9 11  8  7  6  5  3  4  1  2  0
3  5  4  0  1  2  9 10 11  6  7  8
4  3  5  2  0  1 10 11  9  7  8  6
5  4  3  1  2  0 11  9 10  8  6  7
6  7  8  9 10 11  0  2  1  3  4  5
7  8  6 10 11  9  2  1  0  4  5  3
8  6  7 11  9 10  1  0  2  5  3  4


Четно-четно-четно-нечетные квадраты (24, 40, 56 и т. д.) немногим сложнее. Раскручиваем квазиразностную матрицу
Код:
-  0  0  5  0  1  0  3  0
0  -  5  0  1  0  3  0  0
3C 1C -A 4C 3G 6A 4B 5D 0G
1A 3A 4C -A 6A 3C 5C 4A 0A

И в правый нижний угол дописываем соответственно 7E и 7C. Получаем:
Код:
0G 3G 6C 4B 2D 7A 5A 1C   0A 6A 7A 5C 1A 4C 2C 3A
6A 1G 4G 0C 5B 3D 7A 2C   3C 1A 0A 7A 6C 2A 5C 4A
7A 0A 2G 5G 1C 6B 4D 3C   6C 4C 2A 1A 7A 0C 3A 5A
5D 7A 1A 3G 6G 2C 0B 4C   4A 0C 5C 3A 2A 7A 1C 6A
1B 6D 7A 2A 4G 0G 3C 5C   2C 5A 1C 6C 4A 3A 7A 0A
4C 2B 0D 7A 3A 5G 1G 6C   7A 3C 6A 2C 0C 5A 4A 1A
2G 5C 3B 1D 7A 4A 6G 0C   5A 7A 4C 0A 3C 1C 6A 2A
3C 4C 5C 6C 0C 1C 2C 7E   1A 2A 3A 4A 5A 6A 0A 7C

И вот результат для порядка 24:
Код:
1  0  2 10  9 11 18 20 19 12 14 13  6  7  8 21 22 23 15 16 17  3  5  4
2  1  0 11 10  9 19 18 20 14 13 12  8  6  7 22 23 21 16 17 15  4  3  5
0  2  1  9 11 10 20 19 18 13 12 14  7  8  6 23 21 22 17 15 16  5  4  3
18 19 20  4  3  5 13 12 14  0  2  1 15 17 16  9 10 11 21 22 23  6  8  7
19 20 18  5  4  3 14 13 12  1  0  2 17 16 15 11  9 10 22 23 21  7  6  8
20 18 19  3  5  4 12 14 13  2  1  0 16 15 17 10 11  9 23 21 22  8  7  6
21 22 23  0  1  2  7  6  8 16 15 17  3  5  4 18 20 19 12 13 14  9 11 10
22 23 21  1  2  0  8  7  6 17 16 15  4  3  5 20 19 18 14 12 13 10  9 11
23 21 22  2  0  1  6  8  7 15 17 16  5  4  3 19 18 20 13 14 12 11 10  9
15 16 17 21 22 23  3  4  5 10  9 11 19 18 20  6  8  7  0  2  1 12 14 13
17 15 16 22 23 21  4  5  3 11 10  9 20 19 18  7  6  8  2  1  0 13 12 14
16 17 15 23 21 22  5  3  4  9 11 10 18 20 19  8  7  6  1  0  2 14 13 12
3  5  4 18 19 20 21 22 23  6  7  8 13 12 14  1  0  2  9 11 10 15 17 16
5  4  3 20 18 19 22 23 21  7  8  6 14 13 12  2  1  0 10  9 11 16 15 17
4  3  5 19 20 18 23 21 22  8  6  7 12 14 13  0  2  1 11 10  9 17 16 15
12 14 13  6  8  7  0  1  2 21 22 23  9 10 11 16 15 17  4  3  5 18 20 19
13 12 14  8  7  6  2  0  1 22 23 21 10 11  9 17 16 15  5  4  3 19 18 20
14 13 12  7  6  8  1  2  0 23 21 22 11  9 10 15 17 16  3  5  4 20 19 18
7  6  8 15 17 16  9 11 10  3  4  5 21 22 23 12 13 14 19 18 20  0  2  1
8  7  6 16 15 17 11 10  9  5  3  4 22 23 21 13 14 12 20 19 18  1  0  2
6  8  7 17 16 15 10  9 11  4  5  3 23 21 22 14 12 13 18 20 19  2  1  0
9 11 10 12 14 13 15 17 16 18 20 19  0  2  1  3  5  4  6  8  7 22 23 21
10  9 11 13 12 14 16 15 17 19 18 20  1  0  2  4  3  5  7  6  8 23 21 22
11 10  9 14 13 12 17 16 15 20 19 18  2  1  0  5  4  3  8  7  6 21 22 23

0  1  2 18 19 20 21 22 23 15 17 16  3  4  5 12 14 13  6  8  7  9 10 11
1  2  0 19 20 18 22 23 21 16 15 17  4  5  3 13 12 14  7  6  8 10 11  9
2  0  1 20 18 19 23 21 22 17 16 15  5  3  4 14 13 12  8  7  6 11  9 10
9 11 10  3  4  5  0  1  2 21 22 23 18 20 19  6  7  8 15 17 16 12 13 14
10  9 11  4  5  3  1  2  0 22 23 21 19 18 20  7  8  6 16 15 17 13 14 12
11 10  9  5  3  4  2  0  1 23 21 22 20 19 18  8  6  7 17 16 15 14 12 13
18 20 19 12 14 13  6  7  8  3  4  5 21 22 23  0  2  1  9 10 11 15 16 17
19 18 20 13 12 14  7  8  6  4  5  3 22 23 21  1  0  2 10 11  9 16 17 15
20 19 18 14 13 12  8  6  7  5  3  4 23 21 22  2  1  0 11  9 10 17 15 16
12 13 14  0  2  1 15 17 16  9 10 11  6  7  8 21 22 23  3  5  4 18 19 20
13 14 12  1  0  2 16 15 17 10 11  9  7  8  6 22 23 21  4  3  5 19 20 18
14 12 13  2  1  0 17 16 15 11  9 10  8  6  7 23 21 22  5  4  3 20 18 19
6  8  7 15 16 17  3  5  4 18 20 19 12 13 14  9 10 11 21 22 23  0  1  2
7  6  8 16 17 15  4  3  5 19 18 20 13 14 12 10 11  9 22 23 21  1  2  0
8  7  6 17 15 16  5  4  3 20 19 18 14 12 13 11  9 10 23 21 22  2  0  1
21 22 23  9 11 10 18 19 20  6  8  7  0  2  1 15 16 17 12 13 14  3  4  5
22 23 21 10  9 11 19 20 18  7  6  8  1  0  2 16 17 15 13 14 12  4  5  3
23 21 22 11 10  9 20 18 19  8  7  6  2  1  0 17 15 16 14 12 13  5  3  4
15 16 17 21 22 23 12 14 13  0  1  2  9 11 10  3  5  4 18 19 20  6  7  8
16 17 15 22 23 21 13 12 14  1  2  0 10  9 11  4  3  5 19 20 18  7  8  6
17 15 16 23 21 22 14 13 12  2  0  1 11 10  9  5  4  3 20 18 19  8  6  7
3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20  0  1  2 21 23 22
4  5  3  7  8  6 10 11  9 13 14 12 16 17 15 19 20 18  1  2  0 22 21 23
5  3  4  8  6  7 11  9 10 14 12 13 17 15 16 20 18 19  2  0  1 23 22 21


Добавлено спустя 2 часа 21 минуту 42 секунды:

Кстати, такое сложное построение используется только ради свойства N_2. Если же вам вместо этого нужна диагональность, вы можете взять вместо всех матриц, например, одну матрицу A.

 Профиль  
                  
 
 
Сообщение23.03.2009, 19:34 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
(Я ещё не посмотрела добавление, а написала ответ по поводу первой части вашего сообщения).
Так это же метод составных квадратов, о котором 13 января сего года мной написана статья ”Построение пар ортогональных латинских квадратов методом составных квадратов”. Только, на мой взгляд, у меня всё гораздо проще. Понятно, что этот метод работает для таких порядков, как вы их назвали “чётно-чётно-нечётные, потому что все эти порядки представимы в виде произведения числа 4 на нечётное число. И, кроме того, метод составных квадратов известен очень давно, я его во многих статьях и книгах видела. Так что здесь нет ничего нового и интересного.
Чувствуется, что вы недавно с этой темой начали знакомиться.
Добавление сейчас посмотрю. Кстати, зачем это свойство $N_2$ надо, никак не пойму. Чем плохи ортогональные латинские квадраты, не обладающие этим свойством? Тем более что требование этого свойства, как вы говорите, только усложняет построения.

Добавлено спустя 3 минуты 42 секунды:

Посмотрела добавление. И для таких порядков всё очень просто строится методом составных квадратов. Диагональные ортогональные квадраты получаются, если и базовый и основной латинские квадраты диагональные. В моей статье приведён пример построения пары диагональных ортогональных латинских квдаратов порядка 28. Всё это элементарно.

 Профиль  
                  
 
 
Сообщение23.03.2009, 19:46 
Заслуженный участник


31/12/05
1102
Nataly-Mak писал(а):
И, кроме того, метод составных квадратов известен очень давно, я его во многих статьях и книгах видела. Так что здесь нет ничего нового и интересного.
Да. Интересен только подбор маленьких квадратов, который имеет смысл только для N_2. Ну и еще в вашем описании метода составных квадратов не нашел упоминания того, что каждую клетку можно делать из своей пары маленьких квадратов (хотя для ваших целей это и не нужно).
Nataly-Mak писал(а):
Кстати, зачем это свойство $N_2$ надо, никак не пойму. Чем плохи ортогональные латинские квадраты, не обладающие этим свойством?
Им это нужно зачем-то для каких-то кодов, исправляющих ошибки. Так же как вам подходят только диагональные квадраты, им подходят только N_2. Но раз уж они с таким старанием подобрали компоненты составного квадрата, пусть будет :)

 Профиль  
                  
 
 
Сообщение24.03.2009, 07:52 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
tolstopuz писал(а):
Но раз уж они с таким старанием подобрали компоненты составного квадрата, пусть будет :)

Конечно, пусть будет. Это усложнённый вариант метода составных квадратов. Для тех, кто любит всякие сложности.
А что пишут авторы статьи о построении пар ОЛК из серии порядков $n = 6k + 2$, для которых не работает метод составных квадратов? Для этих порядков и применяется "хитрая склейка"? Я там видела что-то вроде того, что если порядок $n$ не принадлежит тому набору порядков, который показан в Приложениях, то... А вот что "то", и не поняла. Кажется, тогда порядок представляется в виде: $n = ax + b$. Ну, вот для начала: как построить пару ОЛК порядка 86, остающегося у меня на сегодня единственным проблемным в первой сотне порядков. В статье есть метод для такого построения?

Добавлено спустя 9 минут 9 секунд:

Да, спасибо за замечание по поводу моего описания метода составных квадратов. Действительно, я этот момент упустила. Когда буду писать книгу, обязательно добавлю :wink:

 Профиль  
                  
 
 
Сообщение29.03.2009, 12:50 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Мой алгоритм работает! Вот какую группу MOLS 8-го порядка, состоящую из максимального количества квадратов, я получила:
Код:
a 0 0 0 0 0 0 0 0
0 a 0 1 2 3 4 5 6
6 6 a 4 2 1 5 0 3
6 5 3 1 0 4 6 2 a
6 4 0 6 3 5 1 a 2
6 3 5 2 4 0 a 1 6
6 2 1 3 6 a 0 5 4
6 1 2 5 a 6 4 3 0
6 0 4 a 5 3 2 6 1

Понятно, что это квази-разностная матрица, по которой строится данная группа. Матрица рассматриваемого мной вида.
Я написала отдельную программу для добавления каждой новой строки, начиная с третьей. Вариантов квази-разностных матриц получено очень много. На каждом этапе я брала одну из конкретных матриц, полученных на предыдущем этапе.
Стандартная группа MOLS 8-го порядка хорошо известна. Мной получены оригинальные группы MOLS совсем другой структуры.
Теперь надо бы попробовать этот алгоритм для порядка 10 и следующих чётных порядков, но я со своим допотопным Бейсиком вряд ли смогу это сделать. Неужели для порядка 10 такая матрица не допускает добавление пятой строки? Трудно поверить!

 Профиль  
                  
 
 
Сообщение30.03.2009, 10:33 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Попробовала поработать с квази-разностными матрицами (КРМ) для пар ОЛК 10-го порядка. Взяла за основу первый латинский квадрат из пары ОЛК Лямзина. Вот КРМ для этого латинского квадрата:
Код:
a 0 0 0 0 0 0 0 0 0 0
0 a 0 1 2 3 4 5 6 7 8
1 1 a 5 8 3 2 7 0 6 4

Теперь надо добавить к этой КРМ четвёртую строку, чтобы все строки были совместимы по известному критерию. Конечно, по-хорошему надо составить программу, но долго очень такая программа будет выполняться, если составить её в лоб. Нет ли у кого-нибудь идеи оптимизации такой программы? Мне известны два решения задачи. Вот они.
Первое решение:
Код:
a 0 0 0 0 0 0 0 0 0 0
0 a 0 1 2 3 4 5 6 7 8
1 1 a 5 8 3 2 7 0 6 4
1 2 5 a 6 0 4 3 8 1 7

Второе решение:
Код:
a 0 0 0 0 0 0 0 0 0 0
0 a 0 1 2 3 4 5 6 7 8
1 1 a 5 8 3 2 7 0 6 4
2 1 5 8 3 2 7 0 6 4 a

Эти две КРМ определяют две пары ОЛК 10-го порядка; одна из них есть сама пара Лямзина, вторая - её вариант, который я получила перестановкой столбцов.
Само собой, возникает вопрос: есть ли ещё решения у этой задачи?
Ну, это всё касается пар ОЛК 10-го порядка. А вот нельзя ли добавить к приведённым КРМ из четырёх строк пятую строку, чтобы получить третий ортогональный квадрат?
Так-таки никто не хочет решить задачу века :)
Впрочем, она, может быть, уже решена? У меня таблица со значениями $N(n)$ за 2007 год. В этой таблице $N(10) = 2$. Может быть, это уже устаревший результат?

 Профиль  
                  
 
 
Сообщение02.04.2009, 09:54 
Заслуженный участник


31/12/05
1102
Я примерно понял алгоритм из статьи, но у меня сейчас нет времени описывать его полностью, так что пока приведу пример, достаточный для порядка $86=7\cdot12+2$.
Код:
0  6  5  4  3  2  1    0  6  5  4  3  2  1
6  5  4a 3  2b 1  0    1  0  6a 5  4b 3  2
5  4b 3  2  1a 0  6    2  1b 0  6  5a 4  3
4  3  2  1  0  6b 5a   3  2  1  0  6  5b 4a
3  2a 1b 0  6  5  4    4  3a 2b 1  0  6  5
2  1  0  6a 5  4  3b   5  4  3  2a 1  0  6b
1  0  6  5b 4  3a 2    6  5  4  3b 2  1a 0

Делаем аналогично методу составных квадратов, но:
а) для левого верхнего угла берем пару квадратов порядка $14$ и два максимальных числа заменяем на a и b;
б) для клеток с буквой берем пару квадратов порядка $13$ с максимальным числом, стоящим в правом нижнем углу, и заменяем везде это число на эту букву, а сам угол отрезаем;
в) для остальных клеток берем пару квадратов порядка $12$.
Лишние строки и столбцы в а) и б) пишем понятно куда.

Для порядка $86$ мне это строить некогда, но для порядка $9=7\cdot1+2$ это будет выглядеть примерно так:
Код:
0 6 5 4 3 2 1 a b   a 6 5 4 3 2 1 0 b
6 5 a 3 b 1 0 4 2   1 0 a 5 b 3 2 6 4
5 b 3 2 a 0 6 1 4   2 b 0 6 a 4 3 5 1
4 3 2 1 0 b a 5 6   3 2 1 0 6 b a 4 5
3 a b 0 6 5 4 2 1   4 a b 1 0 6 5 3 2
2 1 0 a 5 4 b 6 3   5 4 3 a 1 0 b 2 6
1 0 6 b 4 a 2 3 5   6 5 4 b 2 a 0 1 3
a 2 4 6 1 3 5 b 0   b 3 6 2 5 1 4 a 0
b 4 1 5 2 6 3 0 a   0 1 2 3 4 5 6 b a

Хотя они неортогональны, но дают общее представление об алгоритме. Если все равно непонятно, потом сделаю для $23=7\cdot3+2$.

 Профиль  
                  
 
 
Сообщение02.04.2009, 15:09 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Не-а, ничего не поняла :cry:
Попытаюсь уточнить мою задачу. Мы с вами, по-моему, договорились, что не будем рассматривать нечётные порядки из-за их тривиальности (тогда зачем рассматривать порядки 9 и 23? Да к тому же для порядка 9 результат - неортогональные ЛК).
А среди чётных порядков меня интересует общий метод построения пар ОЛК серии порядков $n = 6k + 2, k>1$. Понятно, что порядок 86 относится к указанной серии порядков. Но можно начать показ с порядка 14, например, чтобы было более наглядно. Как мне кажется, в статье, с которой вы работаете, эти хитрые склейки преследуют несколько другую цель – получение пар ОЛК, обладающих свойством $N_2$. А если отвлечься от этого свойства, то будет ли метод авторов статьи работать для всех порядков указанной мной серии? Ещё раз прошу показать этот метод на примере порядка 14. Если же эти хитрые склейки, о которых пишут авторы статьи, относятся к определённому набору порядков, то это уже не будет общий метод в полном смысле этого слова. Вы согласны с этим?
Описала построение групп MOLS 8-го порядка в статье ”Оригинальные группы MOLS восьмого порядка”. Кто-нибудь может ответить на вопрос: реально ли выполнить всю программу приведённого алгоритма в полном объёме, то есть программу такой структуры: первый блок – добавление в КРМ третьей строки (эта программа выдала 931 решение) ->> подпрограмма для добавления четвёртой строки ->> подпрограмма для добавления пятой строки ->> … ->> подпрограмма для добавления девятой строки? Я выполнила эту программу по шагам. На каждом этапе брала одно решение и выполняла для него следующий этап. Было бы очень интересно выполнить всю программу. Но в лоб это вряд ли реально. Нужна оптимизация. Сейчас написала аналогичную программу для порядка 4. Ещё не ввела её и не попробовала. Получила тоже решение, выполняя программу по шагам. Вот какая получилась КРМ:
Код:
a 0 0 0 0
0 a 0 1 2
0 0 a 2 1
0 1 2 a 0
0 2 1 0 a

Построила по этой КРМ группу MOLS и с удивлением узнала в ней хорошо известную стандартную группу MOLS, только квадраты в построенной группе надо повернуть на 90 градусов вокруг центра против часовой стрелки.
Ну, и, конечно, самый интересный вопрос – реально ли применить алгоритм для порядка 10? Программу для добавления третьей строки я уже составила. Она работает и выдаёт море решений, но я её прервала, потому что конца не видно. Составила и программу для добавления четвёртой строки. Задавая в программе конкретные значения некоторых переменных в циклах, я получила по этой программе уже известные мне решения (КРМ с четырьмя строками; понятно, что эти КРМ определяют известные пары ОЛК 10-го порядка). А вот программу для добавления пятой строки ещё не писала. Но как такую программу выполнять? Ведь неизвестно даже, возможно ли вообще добавление к КРМ пятой строки.
tolstopuz, поскольку весь народ здесь безмолвствует, прошу вас высказать ваше мнение по поводу рассматриваемого мной алгоритма и возможности получить КРМ из пяти строк для порядка 10.
Вообще спасибо вам, что поддерживаете диалог в теме. Без вас она уже давно захирела бы и умерла :)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2870 ]  На страницу Пред.  1 ... 33, 34, 35, 36, 37, 38, 39 ... 192  След.

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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