71822

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

Курсовая

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

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

Русский

2014-11-12

206 KB

7 чел.

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

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

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

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

Выполнил: студент гр. АТР-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


 

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

78189. Основные комбинаторные алгоритмы 169 KB
  Контрольные вопросы Введение Комбинаторные алгоритмы с их акцентом на разработку анализ и реализацию практических алгоритмов являются продуктом века вычислительных машин. Предмет теории комбинаторных алгоритмов вычисления на дискретных математических структурах.
78190. Графы. Алгоритмы на графах 224.61 KB
  Геометрическое - графом называется фигура, состоящая из точек (называемых вершинами) и отрезков, соединяющих некоторые из этих вершин. Соединяющие отрезки могут быть направленными (дугами), ненаправленными (ребрами)
78191. Алгоритмы поиска кратчайших расстояний в графе 194.5 KB
  Требуется посетить все вершины графа и вернуться в исходную вершину минимизировав затраты на проезд или минимизировав время. Исходные данные – это граф дугам которого приписаны положительные числа – затраты на проезд или время необходимое для продвижения из одной вершины в другую. В общем случае граф является ориентированным и каждые две вершины соединяют две дуги – туда и обратно. Пусть требуется найти расстояния от 1й вершины до всех остальных.
78192. Алгоритмы поиска с возвращением 87.5 KB
  Рассмотрим общий случай, когда решение задачи имеет вид вектора (а1, а2,), длина которого не определена, но ограничена сверху некоторым (известным или неизвестным) числом r, а каждое аi является элементом некоторого конечного линейно упорядоченного множества
78193. Типы файлов. Организация файловой системы. Текстовые файлы. Нетипизированные файлы 109.5 KB
  В Паскале понятие файла употребляется в двух смыслах: как поименованная информация на внешнем устройстве внешний файл; как переменная файлового типа в Паскальпрограмме внутренний файл. С элементами файла можно выполнять только две операции: читать из файла и записывать в файл. Существует специальная ячейка памяти которая хранит адрес элемента файла предназначенного для текущей обработки записи или чтения. Этот адрес называется указателем или окном файла.
78195. Элементы системного программирования. Прерывания. Резидентные программы 118 KB
  Системным программированием называют разработку программ, которые выполняют действия, возлагаемые на ОС. Это операции с файлами, управление выполнением программ, работа с устройствами и т.д.
78196. Объектно-ориентированное программирование: объект, наследование, инкапсуляция, полиморфизм 117.5 KB
  Объекты представляют собою упрощенное, идеализированное описание реальных сущностей предметной области. Если соответствующие модели адекватны решаемой задаче, то работать с ними оказывается намного удобнее, чем с низкоуровневым описанием всех возможных свойств и реакций объекта.
78197. Инициализация и разрушение объектов. Виртуальная функция 68.5 KB
  В программе концепция полиморфизма реализуется при помощи виртуальных методов. Виртуальный метод объявляется в базовом объектном типе и в порожденных от базового типах. После его объявления должно быть помещено зарезервированное слово virtual.