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


 

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

46588. Легочные кровотечения. Этиология. Классификация легочных кровотечений. Лечение 21.08 KB
  Паразитарные заболевания печени. В диагностике эхинококкоза печени большое значение имеет рентгенологическое исследование. При селективной серийной ангиографии наблюдаются характерное дугообразное оттеснение сосудов печени и накопление контрастного вещества между кутнкулярной оболочкой кисты и фиброзной капсулой. Путем радиоизотопного сканирования печени выявляется округлый дефект накопления препарата.
46589. Методы и средства предупреждения пожара, взрыва и обеспечения противопожарной защиты на объекте экономики 21.1 KB
  Для ограничения развития пожара в зданиях сооружениях предусматривают противопожарные преграды: противопожарные стены перегородки перекрытия зоны тамбурышлюзы двери окна люки и клапаны. В этих стенах перекрытиях и перегородках допускают устройство проемов в которых предусмотрены противопожарные двери окна ворота люки и клапана или тамбурышлюзы. Противопожарные двери могут быть НГ или ГВ. НГ двери изготовляют из металлического каркаса обшитого кровельной сталью.
46590. Радиационная, химическая и медико-биологическая защита населения 21.14 KB
  Она реализуется тремя способами защиты: 1 укрытие населения в защитных сооружениях; 2 рассредоточение в загородной зоне работников предприятий и других объектов экономики продолжающих трудиться в городах а также эвакуация из этих городов населения; 3 использование населением СИЗ. Щель не обеспечивает защиту людей от ОВ и БВ поэтому необходимо применение СИЗ. Применение СИЗ и медицинских СЗ. Как известно СИЗ подразделяются на СЗ органов дыхания и кожи.
46591. Реформирование системы государственной власти и законодательства 1985-1991 гг 21.17 KB
  было заменено 70 членов Политбюро 60 секретарей областных партийных организаций 40 членов ЦК КПСС. был смещен первый секретарь Московского горкома КПСС В. состоялся XXVII съезд КПСС который изменил Программу партии. На январском пленуме ЦК КПСС в 1987 г.
46592. Организационные основы обеспечения ОТ на предприятиях 21.25 KB
  Они вытекают из обязанностей и прав по ОТ работодателя и работника которые регламентируются КЗоТом РФ и Основами законодательства РФ об ОТ далее Основами. 3 Основ закрепляет признание и обеспечение приоритета жизни и здоровья работников по отношению к результатам производственной деятельности предприятия. 139 КЗоТ РФ основной обязанностью работодателя по ОТ является обеспечение здоровых и безопасных УТ на каждом РМ. Поэтому он обязан внедрять современные средства ТБ предупреждающие травматизм и обеспечивать санитарногигиенические...
46593. Архитектурная акустика 21.46 KB
  Термическое сопротивление. Сопротивление теплопередаче ограждающей конструкции.Требуемое сопротивление теплопередаче. Сопротивление теплопередаче.
46594. Методика преподавания на профильном уровне. Элективный курс по художественному профилю и специфика его разработки 21.48 KB
  Макаренко в своем учении выделяет несколько стадий этапов:1 стадия становление коллектива стадия первоначального сплочения.актив поддерживает требования педагога и сам предъявляет их к членам колва руководствуясь своими понятиями о том что приносит пользу а что ущерб интересам коллектива. Если активисты правильно понимают потребности коллектива то они становятся надежными помощниками педагога.Происходит стабилизация структуры коллектива.
46595. Мовне законодавство в Україні 21.5 KB
  Мовне законодавство в Україні. В Україні державна мова закріплена першою частиною десятої статті Конституції України відповідно до якої державною мовою в Україні є українська мова. Окрім того вживання мов в Україні регулюється Законом Української РСР Про мови в Українській РСР . Мовна ситуація в Україні є доситьтаки суперечливою і законодавство зовсім її не спрощує.
46596. Пряме й переносне значення слова. Вияви полісемії в різностильових текстах 21.5 KB
  Пряме й переносне значення слова. Пряме значення слова це дефініція слова яка безпосередньо вказує на його співвідношення з тією чи іншою ознакою об'єктивної дійсності як це історично закріпилося у свідомості мовців. Це первинне значення слова. Переносне значення слова це одне із значень слова яке виникло внаслідок перенесення одних ознак предметів чи явищ на інші.