71825

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

Курсовая

Экономическая теория и математическое моделирование

Найти все множества взаимно ортогональных латинских квадратов порядка n если при наложении одного из них на другой каждая из n возможных пар элементов встречается ровно один раз. Пример латинского квадрата 3го порядка: Точная формула для числа Ln латинских квадратов nго порядка неизвестна.

Русский

2014-11-12

294 KB

8 чел.

ГОУВПО “Воронежский государственный технический университет”

Факультет энергетики и систем управления

Кафедра высшей математики и физико-математического моделирования

Курсовая работа

По дисциплине дискретная математика на тему:

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

Выполнил: студент гр. АТР-131

Юхневич О.С.

Принял: Купцов В.С.

    

Воронеж 2013

Содержание

Условие задачи…………………………………………………………………………….3

Теоретическое введение…………………………………………………………………..4

Практическая часть…………………………………………………………………..…....7

Заключение………………………………………………………………………………...9

Список литературы………………………………………………………………………10

 

Условие задачи

Найти все множества взаимно ортогональных латинских квадратов порядка n, если при наложении одного из них на другой каждая из n возможных пар элементов встречается ровно один раз.

1

2

3

4

4

3

2

1

2

1

4

3

3

4

1

2

1

2

3

4

2

1

4

3

3

4

1

2

4

3

2

1

Теоретические сведения

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

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

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

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

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

Число латинских квадратов

n

R(n)

L(n)

Автор и год

1

1

1

2

1

2

3

1

12

4

4

576

5

56

161280

Euler (1782)

6

9408

812851200

Frolov (1890)

7

16942080

61479419904000

Sade (1948)

8

535281401856

108776032459082956800

Wells (1967)

9

377597570964258816

5524751496156892842531225600

Bammel и Rothstein (1975)

10

7580721483160132811489280

9982437658213039871725064756920320000

McKay и Rogoyski (1995)

11

5363937773277371298119673540771840

776966836171770144107444346734230682311065600000

McKay

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

Два латинских квадрата L=(lij) и K=(kij) n-го порядка называются ортогональными, если все упорядоченные пары (lij,kij) различны. Пример двух ортогональных латинских квадратов и соответствующие им упорядоченные пары:

Эйлер называл такие квадраты "полными". В его честь в научной литературе их раньше называли "эйлеровыми" или "греко-латинскими" (так как Эйлер использовал буквы греческого алфавита для квадрата, ортогонального латинскому).

Ортогональные латинские квадраты существуют для любого n, не равного 2 и 6.

Латинский квадрат L n-го порядка имеет ортогональный ему квадрат тогда и только тогда, когда в L существует n непересекающихся трансверсален.

Особый интерес в связи с многочисленными приложениями вызывают множества из нескольких попарно ортогональных латинских квадратов n-го порядка. Максимально возможная мощность N(n) такого множества равна n-1, в этом случае множество называется полным.

При n, стремящемуся к ∞, величина N(n) тоже стремится к ∞.

Для n, являющегося степенью простого числа, всегда существует полное множество попарно ортогональных латинских квадратов, его можно взаимооднозначно сопоставить с конечной проективной плоскостью порядка n. Для его построения применяется метод Боуза, использующий для заполнения квадратов значения многочленов вида fa(x,y)=ax+y при ненулевом a над полем . Пример построения полного множества попарно ортогональных латинских квадратов 4-ого порядка (d – корень примитивного многочлена x2+x+1 над ):

Если n ≡ 1 (mod 4) или n ≡ 2 (mod 4) и свободная от квадрата часть числа n содержит хотя бы один простой множитель p ≡ 3 (mod 4), то для таких n полного множества попарно ортогональных латинских квадратов не существует.

Известные нижние оценки числа N(n) при n < 33 приведены в следующей таблице (выделены оценки, которые могут быть улучшены):

Нижние оценки числа N(n)

n

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

N(n)≥

2

3

4

6

7

8

2

10

5

12

3

4

15

16

3

18

4

5

3

22

6

24

4

26

5

28

4

30

31

Построение ортогональных квадратов – сложная комбинаторная задача. Для её решения применяются как алгебраические конструкции, так и комбинаторные (трансверсален, ортогональные массивы, дизайны, блок-схемы, тройки Штейнера и др.) Существует несколько подходов к решению этой задачи, их можно разделить на две группы. К первой группе относятся методы, основанные на выборе базового латинского квадрата, к которому отыскиваются изотопные ортогональные латинские квадраты. Например, пять попарно ортогональных латинских квадратов 12-го порядка были найдены в результате построения четырех автоморфизмов абелевой группы, являющейся прямым произведением циклических групп порядков 6 и 2.

Ко второй группе относятся методы, использующие для построения ортогональных латинских квадратов комбинаторные объекты (включая сами латинские квадраты) меньших порядков. Например, два латинских квадрата 22-го порядка были построены Bose и Shrikhande на основе двух дизайнов 15-го и 7-го порядка.

 

Практическая часть

Пусть заданы два латинских квадрата  , где подстановки степени n, удовлетворяющие условиям

Латинские квадраты  Ln  и Ln  называются ортогональными, если для любых упорядоченных различных пар  (i, j) ≠ (k, l) выполнено условие

Если Ln и Ln ортогональны, то этот факт записывается следующим образом:  Ln  Ln. Таблицу (si(j)), i, j=1,2, …, n, латинского квадрата Ln будем обозначать той же самой буквой Ln. Обозначим через (Ln Ln) таблицу, полученную наложением таблицы Ln  на таблицу Ln , т.е. размещением в положении с координатами (i, j) пар (si(j), si(j)). Тогда условие (3.2) означает, что все пары, входящие в (Ln Ln), различны.

Определим операцию умножения латинского квадрата Ln  = [s1, s2, …, sn] слева на подстановку s с помощью равенства sLn = [ss1, ss2, …, ssn]. Если Ln  = [s1, s2, …, sn], Ln  = [s1, s2, …, sn] и Ln  Ln, то для любых подстановок s и ŝ имеем  sLn  ŝLn. В самом деле, для любых пар (i, j) ≠ (k, l) выполнено условие

В противном случае из равенств ssi(j) = ssk(l), ŝsi(j) = ŝsr(l), следовало бы si(j) = sr(l), si(j) = sr(l), что противоречит условию (3.2). Полагая s=s1-1, ŝ = (s1’)-1, из пары ортогональных латинских квадратов Ĺn = s1-1Ln и Ĺ’n =(s1’)-1Ln, таблицы которых имеют одинаковые первые строки вида 1, 2, …, n. Такие латинские квадраты называются полунормализованными.

Пусть {Ln(1), Ln(2), …, Ln(r)} – множество латинских квадратов, таких, что

Покажем, что

Обозначим через Ĺn(i) полунормализованный латинский квадрат, соответствующий Ln(i), 1≤ ir. Тогда Ĺn(i) Ĺn(i), ij, 1≤ I, jr. Наложим таблицы  r  полунормализованных латинских квадратов. Ячейка со входами (1, j) содержит  r  элементов j. В ячейке со входами (2, j) все элементы различны. Действительно, пусть в ячейке (2, j) два элемента равны l, 1≤ ln. Тогда в ячейке (1, l) уже имеется пара элементов, равных l, принадлежащих паре латинских квадратов; получаем противоречие с условием их ортогональности. Ни один из различных элементов в ячейке (2, 1) не может совпадать с элементами ячейки (1, 1). Отсюда следует неравенство (3.4).

Если r = n – 1, то множество попарно ортогональных латинских квадратов  Ln(1), Ln(2), …, Ln(n-1) называется полным.

 

 

Заключение

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

Полученные знания статут существенным подспорьем в понимании раздела математики, структурной единицей которого является комбинаторика. Для достижения поставленной задачи необходимо обозначить итоговые формулы, которые послужат “путеводной звездой” в изучении данного вопроса:

СПИСОК ЛИТЕРАТУРЫ

1.     Энциклопедический словарь юного математика/ сост. А.П. Савин-3-е изд. М., Педагогика-Пресс, 1999-360 с.

2.     Латинские квадраты: Метод. указ. и задачи по факультативному курсу / Гонина Е.Е. Пермь, 1991.

3.     Математика. школьная энциклопедия /гл. ред. С.М. Никольский-М.: Большая российская энциклопедия; Дофа, 1997-527 с.

4.     Комбинаторика/ М. Холл, издательство “Мир”, 1970-266 с.

PAGE   \* MERGEFORMAT1


 

А также другие работы, которые могут Вас заинтересовать

67090. Інтерактивна гра «Як не захворіти на грип» 45 KB
  Оголошення теми і завдання З приходом зими похолодань люди частіше хворіють на грип. Наше завдання вияснити чому виникає грип які шляхи його поширення і що можна зробити щоб не захворіти. Напевно вам доводилося хворіти на грип.
67091. Безпека дітей в Інтернеті. Інтернет – друг чи ворог? 306 KB
  Обладнання: імпровізований мікрофон; кафедра; бейджики із написами «суддя», «адвокат», «прокурор», «свідок», «головуючий», «обвинувачений»; таблички «судді», «обвинувачення», «захист», «свідки та слухачі»; мовленнєві опори, написані на окремих великих аркушах, щоб можна було прикріпити біля дошки...
67092. «Дивись на нас, як на рівних» (сценарій конкурсно-ігрової програми до відзначення Всесвітнього дня інвалідів) 73 KB
  Мета. Ознайомити дітей з Державними програмами соціальної підтримки інвалідів в Україні; дати інформацію про проведення Параолімпійських ігор; формувати в учнів почуття милосердя та солідарності з дітьми з обмеженими фізичними можливостями; виховання толерантного ставлення, підтримки, співчуття до інвалідів.
67093. Історичні пісні 144.5 KB
  Виховувати гордість за український народ який має славне героїчне минуле прищеплювати глибокі почуття любові до пісні рідного краю свого народу. Історичні пісні здебільшого виникали у самому вирі бурхливого життя народу.
67094. Историческая игра «Путешествие в мир истории» 83 KB
  Объявляется первый конкурс конкурс Плутословов Учитель. Начинаем третий конкурс конкурс капитанов. Слово предоставляется нашему высокому ареопагу жюри объявляет результаты 13 конкурсов. Ведущий Следующий конкурс Исторический зоосад.
67095. Игровой урок с будущими первоклассниками 86.5 KB
  Беседа: Приходилось ли вам плакать Почему А какое слово противоположное слову плакать Почему люди плачут или смеются А покажите мне своё настроение с которым вы пришли ко мне на урок. VIII Клуб почемучек а Беседа: Дети к нам пришла умная сова с вопросом. Знаете ли вы какое слово на свете самое любознательное...
67096. Как стать ответственным 52 KB
  Напишите ответственный на доске и попросите учащихся дать определение этому понятию. Спросите учащихся могут ли люди стать более ответственными в своих поступках. Если да то как Например стараться всегда приходить вовремя усердно работать говорить правду осознавать ошибки выражать свои мысли и идеи быть лидером...
67097. Карнавал квітів 25 KB
  Нарешті всі ви завітали А ми боялись заблукали Ласкаво просимо Будьте як вдома Знайомтесь з усіма що ще не знайомі. Сонечко: За горами за лісами За широкими полями Серед квітів і дерев Став палац там неосяжний. Король квітів: Познайомити вже час з вихователями вас.
67098. Свято до дня Валентина «Карнавал квітів» 1.97 MB
  Oh, endless sky, full of light and stars at night Bless our hearts and make them bright We ask for love, on lap we praise Get down here, with all your grace. З'являється "Her Majesty, Love". (господарка свята) - Joy, happiness, beauty I'll send to your hearts I'll make you be sweethearts