71822

Разработка алгоритма преобразования латинского прямоугольника в латинский квадрат

Курсовая

Информатика, кибернетика и программирование

Латинские квадраты существуют для любого n достаточно взять таблицу Кэли аддитивной группы кольца : lij= ij1 mod n Число латинских квадратов Точная формула для числа Ln латинских квадратов nго порядка неизвестна. Пример нормализованного латинского квадрата: Число Rn...

Русский

2014-11-12

206 KB

6 чел.

ГОУВПО «Воронежский государственный технический университет»        Факультет энергетики и систем управления                                                         Кафедра высшей математики и физико-математического моделирования

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

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

«Разработка алгоритма преобразования латинского прямоугольника в латинский квадрат»

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

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

Воронеж 2013 г.

Содержание

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

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

Решение……………………………………………………………………………………8

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

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


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

Цифры 1, 2, 3, …, 9 размещены в латинском прямоугольнике с 8 строками и 9 столбцами. Можно ли и сколькими способами, если можно, добавить одну строку, чтобы получить латинский квадрат?


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

ЛАТИНСКИЙ КВАДРАТ

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

В настоящее время в качестве множества M обычно берется множество натуральных чисел {1,2,…,n} или множество {0,1,…,n-1}, однако Леонард Эйлер использовал буквы латинского алфавита, откуда латинские квадраты и получили своё название.[1]

Латинские квадраты существуют для любого n, достаточно взять таблицу Кэли аддитивной группы кольца : lij= (i+j-1) mod n

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

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

[8]

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

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

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

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

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 и Wanless (2005)

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

Два латинских квадрата 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 над полем .[11] Пример построения полного множества попарно ортогональных латинских квадратов 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.[12]

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

Игры и головоломки с латинскими квадратами

Существует ряд игр, в которых используются латинские квадраты. Наиболее известна из них судоку. В ней требуется частичный квадрат дополнить до латинского квадрата 9-го порядка, обладающего дополнительным свойством: все девять его подквадратов содержат по одному разу все натуральные числа от 1 до 9.

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

ЛАТИНСКИЙ ПРЯМОУГОЛЬНИК

прямоугольная матрица размера  каждая строка к-рой является перестановкой (без повторений) элементов множества S, состоящего из га элементов, причем в столбцах каждый элемент встречается не более одного раза. При m = n Л. п. является латинским квадратом порядка п. Обычно S= {1, 2,. . ., п}, и о Л. п. говорят, что он построен на множестве S.

Л. п. существует при любых натуральных т, п,  Примером Л. п. может служить матрица, первая строка к-рой есть (1, 2, . . ., га), а все последующие получаются из предыдущей циклич. сдвигом на один шаг. Л. п. размера  всегда может быть дополнен до латинского квадрата порядка птак, что первые m строк латинского квадрата будут совпадать со строками Л. п.

Для числа L (m, n) Л. п. размера  верна следующая оценка снизу:

Л. п. наз. нормализованным, если его первая строка есть (1, 2,. . ., п). Число К( т, п).нормализованных Л. п. связано с L(m, п).соотношением:

Подсчет L(m, п).при m = 2,3 связан с классич. комбинаторными задачами:с задачей о числе беспорядков (см. Инверсия).и с задачей о супружеских парах. Так, числобеспорядков Dn=K(2, п), а число размещений Un в задаче о супружеских парах есть число Л. п. размера  первые две строки к-рых суть:

Для Un верны формулы:

Число К(3, п).выражается через Dk и Ui:

где  Верна также следующая асимптотика:

где  - Эрмита многочлен. Известно также, что 

Задача о перечислении Л. п., имеющих более трех строк, не решена (1982). При  так, что  получена асимптотика:

На Л. п. распространяются нек-рые понятия и теоремы, связанные с латинскими квадратами. Так, два Л. п.  размера  наз. ортогональными, если все пары вида  различны. Множество Л. п., в к-ром любые два Л. п. ортогональны, имеет не более т-1 Л. п.

Часто под Л. п. понимают следующее обобщение Л. п.: латинским прямоугольником размера  построенным на множестве 5, состоящем из пэлементов, наз. матрица размера  с элементами из S, встречающимися в каждой строке и каждом столбце не более одного раза. Л. п. размера  построенный на псимволах, может быть расширен до латинского квадрата порядка птогда и только тогда, когда каждый символ встречается в Л. п. не менее r+s-п раз.


Решение

Добавить одну строку и получить латинский квадрат можно всегда точно одним способом, так как каждый столбец девятой строки дополняется элементами, не вошедшими в предыдущие строки. 

Пример:

1

2

3

4

5

6

7

8

9

2

3

4

5

6

7

8

9

1

3

4

5

6

7

8

9

1

2

4

5

6

7

8

9

1

2

3

5

6

7

8

9

1

2

3

4

6

7

8

9

1

2

3

4

5

7

8

9

1

2

3

4

5

6

8

9

1

2

3

4

5

6

7

К данному латинскому прямоугольнику добавляем одну строку, чтобы образовать квадрат и заполним элементами, не вошедшими ранее.

1

2

3

4

5

6

7

8

9

2

3

4

5

6

7

8

9

1

3

4

5

6

7

8

9

1

2

4

5

6

7

8

9

1

2

3

5

6

7

8

9

1

2

3

4

6

7

8

9

1

2

3

4

5

7

8

9

1

2

3

4

5

6

8

9

1

2

3

4

5

6

7

9

1

2

3

4

5

6

7

8

 


Литература

  •  Холл М. Комбинаторика, пер. с англ. М. 1970.
  •  Dénes J. H., Keedwell A. D. Latin Squares and their Applications. Budapest. 1974.
  •  Сачков В. Н. Комбинаторные методы дискретной математики. М. 1977.
  •  Dénes J. H., Keedwell A. D. Latin squares: New developments in the theory and applications. Annals of Discrete Mathematics vol. 46. Academic Press. Amsterdam. 1991.
  •  Laywine C.F., Mullen G.L. Discrete mathematics using Latin squares. New York. 1998.
  •  Малых А. Е., Данилова В. И. Об историческом процессе развития теории латинских квадратов и некоторых их приложениях // Вестник Пермского Университета. 2010. Вып. 4(4). С. 95-104.
  •  Тужилин М. Э. Об истории исследований латинских квадратов // Обозрение прикладной и промышленной математики. 2012. Том 19, выпуск 2. С. 226—227.
  •  Риордан Д ж., Введение в комбинаторный анализ, пер. с англ., М., 1963. См. также лит. при ст. Латинский квадрат. В. М. Михеев









PAGE   \* MERGEFORMAT17