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


 

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

81818. Понятие науки. Основные аспекты бытия науки 34.37 KB
  Наука как социальный институт или форма общественного сознания связанная с производством научнотеоретического знания представляет собой определенную систему взаимосвязей между научными организациями членами научного сообщества систему норм и ценностей. Они участвуют в разнообразных формах научного общения дискуссии конференции издания монографии учебники читают лекции и т. Выделим самые характерные черты научного знания. Еще Кант в качестве неотъемлемой черты науки отмечал систематичность научного знания: именно этим как он...
81819. Виховне середовище школи як інтегрований чинник впливу на соціальне становлення та розвиток учнівської молоді 74 KB
  У статті розглядається вплив виховного середовища в школі на соціальне становлення та розвиток учнівської молоді. Розкрито залежність типу виховного середовища школи від особистісної центрації педагога та педагогічного колективу загалом.
81820. Логико-эпистемологический подход к исследованию науки 32.07 KB
  Они полагали что причина большинства эпистемологических затруднений в неправильном использовании языка. Правильное же использование языка которому мы пока не научились даст возможность либо вообще избежать ошибок либо по крайней мере свести к минимуму ущерб от них. исследования языка в основу своих эпистемологических поисков неопозитивисты принялись за работу над многими проблемами методологии науки: тут и соотношение уровней познания принципы выбора теории определение факта место логики и математики в познании и т. Карнапа...
81821. Позитивистская традиция в философии науки 33.28 KB
  Максимум метафизики который признавался позитивизмом законным заключался в призыве к философии стать метанаукой т. Конта 17981857 пустившего в оборот термин позитивизм который фигурирует в названиях основных его сочинений: Курс позитивной философии Дух позитивной философии и Система позитивной политики. Наука к тому времени уже была предметом анализа в немецкой классической философии у Канта Фихте и Гегеля и следы немецкого влияния просматриваются у Конта.
81822. Расширение поля философской прблематики в позитивистской философии науки. Концепции К.Поппера, И. Лакатоса, Т. Куна, П. Фейерабенда, М.Полани 42.44 KB
  Проблему роста развития изменения знания разрабатывали начиная с 60х гг. Они считали что существует тесная аналогия между ростом знания и биологическим ростом т. В постпозитивизме происходит существенное изменение проблематики философских исследований: если логический позитивизм основное внимание обращал на анализ структуры научного познания то постпозитивизм главной своей проблемой делает понимание роста развития знания. Первой такой концепцией стала концепция роста знания К.
81823. Социологический и культурологический подходы к исследованию развития науки 27.7 KB
  проблема истории науки не была предметом специального рассмотрения ни философов ни ученых работавших в той или иной области научного знания и только в трудах первых позитивистов появляются попытки анализа генезиса науки и ее истории создается историография науки. Специфика подхода к возникновению науки в позитивизме выражена Г. Спенсером 18201903 в работе Происхождение науки .
81824. Проблема интернализма и экстернализма в понимании механизмов научной деятельности 33.09 KB
  Экстерналистская концепция генезиса науки вызвала резкое неприятие со стороны некоторых историков науки, которые представили альтернативную концепцию, получившую название интерналистской, или имманентной. Согласно этой концепции
81825. Базисные ценности современной цивилизации. Ценность научной рациональности 33.22 KB
  Ценности не сводятся только к моральноэтическим императивам. Ценности способствуют усилению мотивации поступков и действий человека они связаны с глубинными переживаниями значимости своей деятельности и поэтому ценностные установки накладывают свой отпечаток на процесс научного творчества. Важно подчеркнуть что ценности могут играть как позитивную так и негативную роль.
81826. Многообразие форм знания. Научное и вненаучное знание 36.77 KB
  Появление научного знания не отменило и не упразднило не сделало бесполезными другие формы знания. Шестова о том что повидимому существуют и всегда существовали ненаучные приемы отыскания истины которые и приводили если не к самому познанию то к его преддверию но мы так опорочили их современными методологиями что не смеем и думать о них серьезно Каждой форме общественного сознания: науке философии мифологии политике религии и т. соответствуют специфические формы знания.