71822

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

Курсовая

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

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

Русский

2014-11-12

206 KB

9 чел.

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

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

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

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

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


 

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

34103. Гражданско-правовая ответственность за правонарушения в области использования и охраны земель 31.5 KB
  И хотя в настоящее время имущественная ответственность еще не нашла своего подобающего места среди других форм юридической ответственности будущее за ней неоспоримо так как ухудшение качества земель и всей окружающей среды влечет как правило имущественные последствия предполагающие возможность возмещения вреда восстановления земель и нарушенных экологических систем. Гражданским законодательством предусматривается ряд правил выработанных за тысячелетия: вред причиненный личности организации или имуществу подлежит возмещению в...
34104. Административная ответственность за правонарушения в области использования и охраны земель 37 KB
  АДМИНИСТРАТИВНАЯ ОТВЕТСТВЕННОСТЬ Согласно Кодексу РФ об административных правонарушениях КоАП от 30 декабря 2001 г. Кроме того в официальных кругах стала преобладать концепция отмирания социалистического государства и уменьшения административных принудительных средств воздействия на правонарушителей необходимости перехода к добровольному исполнению своих обязанностей перед обществом повышения моральных стимулов. Основным органом наложения административных взысканий стала административная комиссия при исполнительных комитетах...
34105. Уголовная ответственность за регистрацию незаконных сделок с землей (ст. 170 УК РФ) 22 KB
  Уголовная ответственность за регистрацию незаконных сделок с землей ст. 254 УК; государственная регистрация незаконных сделок. Государственная регистрация незаконных сделок с земельными участками ст.
34106. Уголовная ответственность за порчу земель (ст. 254 УК РФ) 22.5 KB
  Уголовная ответственность за порчу земель ст. Порча земель ст. За порчу земель предусмотрена как административная так и уголовная ответственность в зависимости от последствий. Порча земель это ухудшение физических и биологических свойств почвы снижение ценности земли.
34107. Порядок установления и взимания земельного налога 32 KB
  Существует две формы платы за землю: земельный налог; арендная плата. Земельный налог. Земельный налог относится к категории местных налогов. Земельный налог устанавливается исключительно нормативноправовыми актами органов местного самоуправления либо законами представительных органов Москвы и СанктПетербурга.
34108. Арендная плата и нормативная цена земли 40.5 KB
  Оценка земли виды стоимости. Существует 4 вида стоимости цены: нормативная цена; кадастровая стоимость; рыночная стоимость; выкупная цена. В любом случае нормативная цена земельного участка не должна быть более 75 от рыночной стоимости аналогичных земельных участков. были внесены изменения в Закон âОб оценке и оценочной стоимости в РФâ и впервые кадастровая стоимость получила закрепление на законодательном уровне.
34109. Пять базовых техник психотерапии:суггестия, абреакция, манипуляция, разъяснение, интерпретация 95 KB
  Абреакция как основа эмоционального состояния и способности пациента справляться с ним. кратко говоря различных ментальных процессов терапевтом индивидуум в авторитетном положении у пациента индивидуума в зависимом положении независимо от или с исключением рационального или критического реалистического мышления последнего. Техническое использование суггестии может быть главным образом формальным к примеру чтобы в общем индуцировать пациента к фантазии или сну какой бы не была эта фантазия или сон или главным образом...
34110. Понятие регрессии. Роль регрессии в развитии психоаналитической терапии 48 KB
  Понятие регрессии. Роль регрессии в развитии психоаналитической терапии. Процесс регрессии как временный постоянный защитный топический ситуационный. Патологическая и нормальная регрессии их формирование в процессе развития и их значение в функционировании психического аппарата и формировании различных уровней психопатологии.
34111. Принцип психоаналитической нейтральности. Реакции аналитика на пациента: рациональные аффективные, комплиментарные, эмпатические, контрпереносные 48 KB
  Принцип психоаналитической нейтральности. В данной теме особое внимание следует уделить пониманию центрального базового значения психоаналитического понимания нейтральности. Слово НЕЙТРАЛЬНОСТЬ neutrlity и концепция ПСИХОАНАЛИТИЧЕСКОЙ НЕЙТРАЛЬНОСТИ были амбивалентными с самого момента рождения психоанализа. Приветствуемая одно время как настолько фундаментальная что принимается как данность к нейтральности тут же стали тихо относиться как мифу.