Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

История исследований латинских квадратов



Реферат

по дисциплине: «Математический анализ планов эксперимента»

на тему: «Латинские квадраты»

 

Проверила: Доржиева А.А.

Выполнила: Гаськова А.С.

 

Улан-Удэ

2015 г

Содержание

 

1 Понятие латинского квадрата 3

2 История исследований латинских квадратов 3

3 Отношения эквивалентности на множестве латинских квадратов 6

4 Ортогональные латинские квадраты 7

5 Частичные квадраты 9

Список использованных источников 10


Понятие латинского квадрата

 

Латинский квадрат n-го порядка — таблица L=(lij) размеров n × n, заполненная n элементами множества M таким образом, что в каждой строке и в каждом столбце таблицы каждый элемент из M встречается в точности один раз. Пример латинского квадрата 3-го порядка:

В настоящее время в качестве множества M обычно берётся множество натуральных чисел {1,2,…,n} или множество {0,1,…,n-1}, однако Леонард Эйлер использовал буквы латинского алфавита, откуда латинские квадраты и получили своё название.[1]

Латинские квадраты существуют для любого n, достаточно взять таблицу Кэли аддитивной группы кольца : lij= (i+j-1) mod n.

 

История исследований латинских квадратов

 

Впервые латинские квадраты (4-го порядка) были опубликованы в книге «Шамс аль Маариф» («Книга о Солнце Гнозиса»), написанной Ахмадом аль-Буни в Египте приблизительно в 1200 году.

Пары ортогональных латинских квадратов впервые были упомянуты Жаком Озанамом в 1725 году.[2] В книге, представляющей собой сборник задач по физике и математике, приведена следующая задача:

Необходимо разместить 16 игральных карт из тузов, королей, дам и валетов всех четырёх мастей в виде квадрата так, чтобы все масти и карты всех достоинств встречались в каждой строке и в каждом столбце ровно один раз.

Эта задача имеет 6192 решения (если дополнительно потребовать, чтобы и диагонали квадрата удовлетворяли тому же условию, то число решений уменьшится в 6 раз и станет равным 1152).

Важной вехой в истории исследований латинских квадратов стала работа Эйлера[1]. Он занимался в ней методами построения магических квадратов и предложил метод, основанный на паре ортогональных латинских квадратов. Исследуя такие пары, Эйлер выяснил, что проблема их построения подразделяется на три случая в зависимости от остатка от деления числа n на 4. Он предложил способы построения пар ортогональных квадратов для n, делящихся на 4 и для нечётных n. Очевидно, что при n = 2 таких пар не существует. Ему не удалось построить пары ортогональных латинских квадратов для n = 6, 10 и он высказал гипотезу о том, что не существует пар ортогональных квадратов для n = 4t+2. Для n = 6 он сформулировал «задачу о 36 офицерах»:

Необходимо разместить 36 офицеров шести различных полков и шести различных воинских званий в каре так, чтобы в каждой колонне и в каждом ряду был ровно один офицер каждого полка и каждого воинского звания.

В 1890 году Кэли вывел формулу для числа латинских прямоугольников из двух строк (частный случай классической комбинаторной «задачи о встречах», поставленной P. Montmort в 1708 году).[3]

В 1900 году гипотеза Эйлера для n = 6 была подтверждена G. Tarry.[4] Он построил все 9408 нормализованных латинских квадратов, разбил их на 17 типов и показал, что при любом их сочетании невозможно построить пару ортогональных квадратов. Таким образом, он отрицательно решил «задачу о 36 офицерах».

В 1922 году MacNeish впервые применил теоретико-групповой подход к решению задач относительно латинских квадратов.[5] В частности, он предложил метод конструирования латинских квадратов порядка n1•n2 из латинских квадратов порядков n1 и n2, при этом свойство ортогональности сохраняется.

В 1925 году Fisher предложил использовать ортогональные латинские квадраты для планирования сельскохозяйственных экспериментов.[6]

В 1920—1930 годы стали интенсивно изучаться неассоциативные алгебраические структуры, что привело, в частности, к созданию теории квазигрупп, тесно связанной с изучением латинских квадратов, так как между латинскими квадратами и таблицами Кэли квазигрупп существует взаимно-однозначное соответствие.

В 1959 году Bose и Shrikhande построили 2 ортогональных латинских квадрата для n = 22, а в 1960 году они же и Parker построили с использованием ЭВМ минимальный контрпример для n = 10. Таким образом, спустя 177 лет гипотеза Эйлера была опровергнута.[7]

Число латинских квадратов[править | править вики-текст]

Точная формула для числа L(n) латинских квадратов n-го порядка неизвестна. Наилучшие оценки для L(n) дает формула

[8]

Каждому латинскому квадрату можно поставить в соответствие нормализованный (или редуцированный) латинский квадрат, у которого первая строка и первый столбец заполнены в соответствии с порядком, заданном на множестве M. Пример нормализованного латинского квадрата:

Число R(n) нормализованных латинских квадратов n-го порядка в n!(n-1)! раз меньше, чем L(n).

Точные значения величины L(n) известны для n от 1 до 11:[4]

Число латинских квадратов
n R(n) L(n) Автор и год
 
 
 
 
Euler (1782)
Frolov (1890)

 

Продолжение таблицы

Sade (1948)
Wells (1967)
Bammel и Rothstein (1975)
McKay и Rogoyski (1995)
McKay и Wanless (2005)

 

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.