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


 

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

31350. РАЗВИТИЕ ИССЛЕДОВАТЕЛЬСКОЙ ИНИЦИАТИВНОСТИ В ДЕТСКОМ ВОЗРАСТЕ 9.73 MB
  Структура и функции исследовательской инициативности в деятельности человека . Психологические исследования деятельности человека по изучению сложных многосвязных объектов . В настоящее время развитие общества характеризуется все возрастающей динамичностью проникновением на новые уровни познания природы изменением социального устройства и возникновением качественно новых видов деятельности в ранее неизвестных областях. Особое значение здесь приобретает стремление и способность личности активно исследовать новизну и сложность меняющегося...
31351. КОММУНИКАТИВНЫЕ СТРАТЕГИИ И ТАКТИКИ АГИТАЦИОННОГО ТЕКСТА И ИХ СТИЛИСТИЧЕСКАЯ РЕПРЕЗЕНТАЦИЯ 850 KB
  Формирование в стране новой коммуникационной среды, новых форм коммуникационного обмена, становление системы активных публичных коммуникаций обусловило актуальность социопрагматического аспекта анализа феноменов вербальной коммуникации. По выражению О.С. Иссерс, «в сегодняшнем обществе сформировался социальный заказ на знание закономерностей общения»
31352. Параметрические модели популяционной динамики и их приложение к задачам демографии 6.7 MB
  Приближение стабильного населения и решение уравнения Лотки. Макроэкономическая модель устойчивого развития населения. В настоящей диссертационной работе проведена систематизация и предпринята попытка развития параметрических методов моделирования динамики численности популяций и в частности населения вводится понятие информационного параметра как отличительной черты цивилизованного общества от биологической популяции и рассматривается его участие в демографических процессах. В работе уделено особое внимание параметрическому...
31355. Организационно-экономические формы дилерской деятельности на российском рынке 391.46 KB
  Переход России к рыночным отношениям невозможен без создания сети малых предприятий способных обеспечить структурную перестройку экономики оперативно реагировать на изменение потребительского спроса. Развитие малых предприятий имеет огромное значение для насыщения рынка товарами и услугами создания конкурентной среды внедрения достижений научнотехнического прогресса В странах с развитой рыночной экономикой малые предприятия составляют самую многочисленную долю их субъектов. Развитие малого предпринимательства в...
31356. ФЕНОМЕНОЛОГИЧЕСКИЙ ПОДХОД В ПСИХОЛОГИИ: ИСТОРИЯ И ПЕРСПЕКТИВЫ 871 KB
  Шпигельбергом мы имеем все основания утверждать что центральной фигурой в развитии феноменологического движения был и до сих пор является Эдмунд Гуссерль [65 с. Исходные эпистемологические идеи Гуссерля Как известно Гуссерль получил отнюдь не философское образование. Исследуя основные понятия и принципы математики и логики Гуссерль пришел к убеждению о принципиальной незавершенности естественнонаучного и математического знания [Мотрошилова 43 с. Чем глубже я анализировал тем сильнее сознавал что логика нашего времени не доросла до...
31357. МЕТОДОЛОГИЯ УПРАВЛЕНИЯ КОРПОРАТИВНЫМИ ИНВЕСТИЦИЯМИ В РЕГИОНЕ (на примере республики Татарстан) 739.5 KB
  Активизация инвестиционного процесса – наиболее актуальная и весьма болезненно решаемая макроэкономическая проблема. Рост объемов инвестиций и подъем экономики в целом ожидался и прогнозировался, начиная с 1993 г., однако выхода из состояния циклического спада не произошло до сих пор
31358. Факторы роста оборотного капитала промышленных предприятий и цена источников его финансирования 3.95 MB
  Оценка финансового состояния предприятия нефтеперерабатывающей отрасли. Финансовый анализ и диагностика предприятия химической отрасли. В начале XXI века в российской экономике действуют наряду с неплатежеспособными предприятиями и вполне благополучные финансово состоятельные хозяйствующие субъекты которые смогли прогрессивно воспринять перемены направленные на многоукладность экономики широкий спектр форм собственности неизбежность опережающего наращивания качества и номенклатуры товаров для широкого потребительского спроса....