Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 4210 ]  На страницу Пред.  1, 2, 3, 4, 5 ... 421  След.
Автор Сообщение
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 18 янв 2016, 09:39 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 5224
Откуда: Саратов
Cпасибо сказано: 586
Спасибо получено:
411 раз в 346 сообщениях
Очков репутации: 80

Добавить очки репутацииУменьшить очки репутации
Avgust писал(а):
Но разве трудно перелолпатить все-все варианты для n=10 ?

Наверное, трудно, потому что вариантов мириады.
Смотрите: 10 элементов в первой строке, вариантов заполнения только первой строки 10!.
А дальше: вторую строку тоже можно заполнить 10! способами (правда, с некоторым минусом уже - так как конкретное заполнение первой строки уже отсекает некоторые варианты заполнения второй строки), и третью - тоже, и т. д.
Это в одном квадрате. А потом надо к нему подстроить второй квадрат, чтобы пара получилась ортогональная, а потом ещё и третий квадрат найти, чтобы он был ортогонален первым двум.
Если б всё было так просто, давно бы перелопатили.

Для построения пар ОЛК 10-го порядка придумали несколько очень красивых алгоритмов. Об одном из них, связанным с квази-разностной матрицей, я расскажу далее.

Кстати, и для групп MOLS других порядков изобрели немало разных алгоритмов. Вот только для порядка 10 ничего хорошего не изобрели пока. А перебором в лоб тут ничего не сделаешь.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 19 янв 2016, 05:59 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 5224
Откуда: Саратов
Cпасибо сказано: 586
Спасибо получено:
411 раз в 346 сообщениях
Очков репутации: 80

Добавить очки репутацииУменьшить очки репутации
Нашла статью в Интернете
https://cs.anu.edu.au/~./bdm/papers/ls_final.pdf

Цитирую:

Цитата:
Meanwhile, no set of 3 MOLS of order 10 has yet been found, despite a considerable
amount of effort by many people. See [1, 9, 11, 12, 13, 14, 15, 36, 37, 41, 42, 54] for
some representative partial results. In this paper we will add our own contribution to this
quest; namely, we will describe computations that show that none of the 8,500,842,802
main classes of Latin squares with non-trivial autoparatopy groups lie in a set of 3 MOLS
(where the other two squares may have trivial groups). We believe this to be by far the
largest systematic search so far undertaken for 3 MOLS of order 10.

И далее цитирую часть списка литературы - как раз те работы, в которых пытались найти тройку попарно ортогональных ЛК 10-го порядка:

Цитата:
[9] A. E. Brouwer, Four MOLS of order 10 with a hole of order 2, J. Statist. Plann.
Inference, 10 (1984) 203–205.
[11] J. W. Brown, An extension of Mann’s theorem to a triple of mutually orthogonal
Latin squares of order 10. J. Combin. Theory Ser. A, 12 (1972) 316–318.
[12] J. W. Brown and E. T. Parker, A try for three order-10 orthogonal Latin squares,
Congr. Numer., 36 (1982) 143–144.
[13] J. W. Brown and E. T. Parker, Some attempts to construct orthogonal Latin squares,
Congr. Numer., 43 (1984) 201–202.
[14] J. W. Brown and E. T. Parker, An attempt to construct three mols ◦10 with a common
transversal, Algebras Groups Geom., 2 (1985) 258–262.
[15] J. W. Brown and E. T. Parker, More on order 10 turn-squares, Ars Combin., 35
(1993) 125–127.

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 19 янв 2016, 06:16 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 5224
Откуда: Саратов
Cпасибо сказано: 586
Спасибо получено:
411 раз в 346 сообщениях
Очков репутации: 80

Добавить очки репутацииУменьшить очки репутации
Теперь показываю обещанный алгоритм построения пар ОЛК 10-го порядка, основанный на квази-разностной матрице.
Сразу иллюстрация

Изображение

Сверху на иллюстрации вы видите квази-разностную матрицу, далее для краткости будет использоваться аббревиатура КРМ.
Первые две строки КРМ - это координаты; около ЛК координаты - сиреневые строка и столбец, они к ЛК не принадлежат.
Символьный элемент [math]a=9[/math].
Окрашенные в жёлтый цвет ячейки - это то, что заполняется по значениям, соответствующим координатам. Далее заполнение идёт по диагоналям ЛК циклическим сдвигом набора (0, 1, 2, 3, 4, 5, 6, 7, 8).
Первому ЛК соответствует третья строка КРМ, второму ЛК - четвёртая строка КРМ.

Здесь показана пара ОЛК, построенная по данной КРМ.
Строки КРМ должны удовлетворять критерию совместимости: разности между соответствующими элементыми любых двух строк должны быть различными по модулю 9. При этом разности, содержащие символьный элемент, не считаются.
В этом и только в этом случае два ЛК, построенные по КРМ, будут ортогональными.
Ну, и разумеется, все элементы в каждой строке должны быть различные.

Если тут всё понятно и вопросов нет, продолжу чуть позже.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 19 янв 2016, 08:03 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 5224
Откуда: Саратов
Cпасибо сказано: 586
Спасибо получено:
411 раз в 346 сообщениях
Очков репутации: 80

Добавить очки репутацииУменьшить очки репутации
Цитата:
Ну, и разумеется, все элементы в каждой строке должны быть различные.

Тут не совсем точно выразилась: элементов в каждой строке КРМ 11, различными должны быть 10 элементов из 11.
Ну, естественно, первая строка не в счёт, в ней вообще одни нули и символьный элемент a.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 19 янв 2016, 08:41 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 5224
Откуда: Саратов
Cпасибо сказано: 586
Спасибо получено:
411 раз в 346 сообщениях
Очков репутации: 80

Добавить очки репутацииУменьшить очки репутации
А теперь отчёт форумчанина tolstopuz на форуме dxdy.ru об эксперименте:
Цитата:
Итак, найдено:
- 2025 трехстрочных КРМ;
- 3240 четырехстрочных КРМ;
- 0 пятистрочных КРМ.

Естественно, четырехстрочные КРМ попарно связаны перестановкой третьей и четвертой строк, так что интересных из них только 1620.

http://dxdy.ru/post202837.html#p202837

Как видно из отчёта, tolstopuz начинал с поиска трёхстрочных КРM, это значит: к двум координатным строкам КРМ добавляется третья строка, удовлетворяющая критерию совместимости. Это будет соответствовать только одному ЛК, построенному данным способом.
Таких ЛК судя по отчёту найдено 2025 штук. Богато :)
Далее для каждого варианта трёхстрочной КРМ ищется четвёртая строка, если она найдена, это уже получена пара ОЛК. Как видим, пар ОЛК тоже найдено немало - 1620 различных.

А теперь внимание! Самое интересное в эксперименте - попыка добавить в КРМ пятую строку. Это и есть попытка найти тройку попарно ортогональных ЛК. Увы, попытка не увенчалась успехом.
Но можно попытаться по этому алгоритму искать псевдотройки.

К этой КРМ
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

в эксперименте был найден такой вариант четвёртой строки:
0 8 3 6 1 0 5 7 4 2 a

Сейчас попробую по этой строке построить второй ЛК ортогональный первому (первый ЛК остаётся такой же, как показано выше, потому что третья строка КРМ не изменилась).

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 19 янв 2016, 09:15 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 5224
Откуда: Саратов
Cпасибо сказано: 586
Спасибо получено:
411 раз в 346 сообщениях
Очков репутации: 80

Добавить очки репутацииУменьшить очки репутации
КРМ будет такая:

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
0 8 3 6 1 0 5 7 4 2 a

Второй ЛК, соответствующий четвёртой строке КРМ:

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

Всё правильно: этот ЛК ортогонален ЛК, соответствующему третьей строке КРМ (показан выше).

Если кто-нибудь вник в алгоритм, пожалуйста, попробуйте добавление пятой строки к КРМ.
Только надо ослабить критерий совместимости строк, чтобы получить псевдотройки.
То есть надо потребовать ортогональность 1-го и 2-го ЛК, 1-го и 3-го ЛК, а вот 2-ой с 3-им могут быть не ортогональными (третьему ЛК будет соответствовать пятая строка КРМ).

А я сейчас поищу в своих статьях КРМ другого типа.
Кстати, вот мои статьи, посвящённые КРМ:
http://www.natalimak1.narod.ru/quazi.htm
http://www.natalimak1.narod.ru/quazi1.htm
http://www.natalimak1.narod.ru/quazi2.htm


Последний раз редактировалось Nataly-Mak 19 янв 2016, 09:48, всего редактировалось 2 раз(а).
Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Nataly-Mak "Спасибо" сказали:
Avgust
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 19 янв 2016, 09:26 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 19:13
Сообщений: 12428
Откуда: Москва
Cпасибо сказано: 1082
Спасибо получено:
3480 раз в 3056 сообщениях
Очков репутации: 655

Добавить очки репутацииУменьшить очки репутации
Nataly-Mak
Вы так убежали вперед паровоза, что даже в бинокль не угнаться за мыслями :good:

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 19 янв 2016, 09:31 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 5224
Откуда: Саратов
Cпасибо сказано: 586
Спасибо получено:
411 раз в 346 сообщениях
Очков репутации: 80

Добавить очки репутацииУменьшить очки репутации
Avgust
пожалуйста, ваши вопросы.
Я остановлюсь и попробую разъяснить непонятные места.
Мне-то кажется всё простым и очевидным, потому что занималась этим раньше.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 19 янв 2016, 10:05 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 5224
Откуда: Саратов
Cпасибо сказано: 586
Спасибо получено:
411 раз в 346 сообщениях
Очков репутации: 80

Добавить очки репутацииУменьшить очки репутации
Кстати, псевдотройка к нас вроде как уже и получилась: перый ЛК, соответствующий третьей строке КРМ, второй ЛК - соответствующий четвёртой строке КРМ в её первом варианте; эти два ЛК показаны на иллюстрации, они ортогональны.

Теперь построили ещё один ЛК по новой чётвёртой строке КРМ, этот ЛК тоже ортогонален первому ЛК. А вот второму ЛК (см. на иллюстрации) он не ортогонален.

Осталось посмотреть, много ли ошибок в не ортогональной паре ЛК.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 19 янв 2016, 10:24 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 5224
Откуда: Саратов
Cпасибо сказано: 586
Спасибо получено:
411 раз в 346 сообщениях
Очков репутации: 80

Добавить очки репутацииУменьшить очки репутации
Показываю три ЛК полученной псевдотройки:

№1
9 5 8 3 2 7 0 6 4 1
5 9 6 0 4 3 8 1 7 2
8 6 9 7 1 5 4 0 2 3
3 0 7 9 8 2 6 5 1 4
2 4 1 8 9 0 3 7 6 5
7 3 5 2 0 9 1 4 8 6
0 8 4 6 3 1 9 2 5 7
6 1 0 5 7 4 2 9 3 8
4 7 2 1 6 8 5 3 9 0
1 2 3 4 5 6 7 8 0 9

№2
5 8 3 2 7 0 6 4 9 1
9 6 0 4 3 8 1 7 5 2
6 9 7 1 5 4 0 2 8 3
0 7 9 8 2 6 5 1 3 4
4 1 8 9 0 3 7 6 2 5
3 5 2 0 9 1 4 8 7 6
8 4 6 3 1 9 2 5 0 7
1 0 5 7 4 2 9 3 6 8
7 2 1 6 8 5 3 9 4 0
2 3 4 5 6 7 8 0 1 9

№3
3 9 4 7 2 1 6 8 5 0
6 4 9 5 8 3 2 7 0 1
1 7 5 9 6 0 4 3 8 2
0 2 8 6 9 7 1 5 4 3
5 1 3 0 7 9 8 2 6 4
7 6 2 4 1 8 9 0 3 5
4 8 7 3 5 2 0 9 1 6
2 5 0 8 4 6 3 1 9 7
9 3 6 1 0 5 7 4 2 8
8 0 1 2 3 4 5 6 7 9

Это квадрат, составленный из пар соотвествующих элементов не ортогональных ЛК №2 и №3:
53  89  34  27  72  01  66  48  95  10 
96 64 09 45 38 83 12 77 50 21
61 97 75 19 56 40 04 23 88 32
00 72 98 86 29 67 51 15 34 43
45 11 83 90 07 39 78 62 26 54
37 56 22 04 91 18 49 80 73 65
84 48 67 33 15 92 20 59 01 76
12 05 50 78 44 26 93 31 69 87
79 23 16 61 80 55 37 94 42 08
28 30 41 52 63 74 85 06 17 99

Много ошибок?
У меня в программе нет подсчёта повторений, надо добавить, чтобы искала повторения.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.    На страницу Пред.  1, 2, 3, 4, 5 ... 421  След.  Страница 2 из 421 [ Сообщений: 4210 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
О теме "Отрогональные латинские квадраты 10-го порядка"

в форуме Предложения, Замечания, Обратная связь

Nataly-Mak

21

1753

14 июн 2018, 05:28

Ортогональные пространства

в форуме Функциональный анализ, Топология и Дифференциальная геометрия

Avrora

0

274

18 ноя 2014, 18:53

Ортогональные векторы

в форуме Аналитическая геометрия и Векторная алгебра

Alex03889

1

292

23 дек 2012, 15:00

Ортогональные собственные вектора

в форуме Аналитическая геометрия и Векторная алгебра

HJey

0

98

18 апр 2019, 23:18

Ортогональные центральные композиционный план

в форуме Исследование операций и Задачи оптимизации

AHAHAC

2

299

08 дек 2016, 09:20

Ряд Фурье и другие ортогональные разложения

в форуме Ряды Фурье и Интегральные преобразования

Chelovekley

1

397

29 апр 2015, 14:47

Ортогональные проекции вектора на стороны треугольника

в форуме Аналитическая геометрия и Векторная алгебра

dollemika

4

1275

14 дек 2011, 17:38

Левое и правое ортогональные дополнения подпространства

в форуме Линейная и Абстрактная алгебра

TotalRecall

2

594

30 апр 2012, 01:18

Обобщенные вещественно ортогональные формы в радиосвязи

в форуме Линейная и Абстрактная алгебра

mike84

2

356

14 июн 2015, 13:37

Доказать, что ортогональные проекции вершин н-мерного куба

в форуме Геометрия

Arzybek

13

215

18 сен 2020, 21:29


Часовой пояс: UTC + 3 часа [ Летнее время ]



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

Сейчас этот форум просматривают: Alexandrietz, searcher и гости: 10


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

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2020 MathHelpPlanet.com. All rights reserved