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


 

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

53132. Свята в Німеччині та в Украіні 220.5 KB
  Guten Tag, liebe Kinder und liebe G?ste! Ich freue mich sehr, euch alle zu sehen und ich hoffe, dass ihr gute Zeit haben werdet. Feste und Br?uche spielen eine wichtige Rolle im Leben des Volkes. Und Deutsche haben Feiertage auch sehr gern. Der deutsche Dichter Joseph von Eichendorff hat?ber Feiertage ein Gedicht geschrieben...
53133. Leseverstehen. Das Märchen „Das Salz“ 52 KB
  Die dritte Tochter weinte und verließ ihren Vater. Aber bald sah man keine fröhlichen Menschen mehr. Brot ohne Salz, Fleisch ohne Salz, Gemüse ohne Salz -- das alles schmeckte den Menschen nicht. Sie hatten keinen Appetit mehr, sie wollten nicht mehr essen. Auch die Arbeit bereitete ihnen keine Freude mehr. Der König sah das alles. Das Essen schmeckte ihm auch nicht. Es gab kein Salz im Land mehr.
53135. Йоганн Вольфганг фон Гете – виразник ідей Просвітництва. Творчий і життєвий шлях письменника. Образ Фауста у літературі, музиці, малярстві 82.5 KB
  Liebe Freunde! Ich wünsche euch einen wunderschönen Guten Morgen und freue mich euch wiederzusehen. Wir werden heute über die Gestalt des Faust und den Unterstied dieser Gestalt im Werken von Goethe und Puschkin sprechen und wie diese Gestalt des Faust sich in der Musik und Malerei widergespiegelt hat.
53136. Гетьманщина наприкінці ХVІІ - у першій половині ХVІІІ ст 124.5 KB
  Підручники таблиця Іван Мазепа роздатковий матеріал. Мазепа біографія Дискусійний клуб Обери позицію: дати оцінку діяльності І. Мазепа історична постать неоднозначна таємничо загадкова і до цього часу. В літературних творах оспівано його образ...
53137. Гідросфера. Позакласний захід (КВК) з географії для 6 класу 40.5 KB
  ХІД ГРИ Ведучий: Сьогодні ми проводимо географічний КВК під час вивчення теми Гідросфера. Одиниця вимірювання солоності води проміле. На Дніпрі споруджено 6 великих водосховищ які створюють величезний запас води для більш посушливих південних і східних областей України. Значна кількість дніпровської води подається каналами і трубопроводами в південні і східні регіони України з постійним дефіцитом прісної води.
53138. РОЗРОБКА УРОКУ – ГРИ «СВИСТАТИ ВСІХ НАГОРУ!» (УЗАГАЛЬНЮЮЧИЙ УРОК З ГЕОГРАФІЇ У 7 КЛАСІ) 249 KB
  Мета уроку: навчальна: повторити, узагальнити та систематизувати знання учнів з теми «Гідросфера»; вдосконалювати навички та вміння використовувати набуті знання на практиці у нестандартних ситуаціях; підвищити інтерес до вивчення географії за допомогою ігрової форми,
53139. Гідросфера. Узагальнення (урок – гра у 6 класі) 89.5 KB
  Якщо тему добре знаєш То мене ти відгадаєш Запитання: Про що йде мова У яких станах може перебувати вода на Землі Твердому рідкому газоподібному. Запитання: Яке явище описано у вірші Що є основною причиною утворення кругообігу води в природі Енергія Сонця. Запитання: Про які кольорові моря йде мова Жовте Чорне Червоне Біле . Запитання: Яка основна причина океанічних течій ...
53140. Гигиена питания 98.5 KB
  Действующие лица: комиссар полиции мистер Бортоломью инспектор полиции мистер Дрейк миссис Синтия Бабингтон. Мери пожалуйста пригласите ко мне инспектора Дрейка. Входит инспектор Дрейк. Доброе утро инспектор.