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


 

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

10364. Особенности профессионально-педагогической деятельности современного учителя. Требования к учителю в теории и истории отечественной и зарубежной педагогики 75 KB
  Особенности профессионально-педагогической деятельности современного учителя. Требования к учителю в теории и истории отечественной и зарубежной педагогики Я.А. Коменский И.Г. Песталоцци А. Дистервег К.Д. Ушинский Л.Н. Толстой А.С. Макаренко. Требования к учителю совре...
10365. Учитель в современной школе, его должностные обязанности. Квалификационные категории и разряды профессионального статуса учителя 59.5 KB
  Учитель в современной школе его должностные обязанности. Квалификационные категории и разряды профессионального статуса учителя. Процесс профессионального самосовершенствования учителя. Повышение квалификации и аттестации учителя. Индивидуальные стили педагогическ...
10366. Классный руководитель в современной школе. Основные направления его деятельности с коллективом учащихся. Психология малых групп 45 KB
  Классный руководитель в современной школе. Основные направления его деятельности с коллективом учащихся. Психология малых групп. Планирование и организация работы классного руководителя. Особенности организации взаимодействия учителя с семьей школьника. Формы виды ра...
10367. Инновационные процессы в образовании. Типы инновационных учебных заведений и особен-ности организации в них учебно-воспитательного процесса 43 KB
  Инновационные процессы в образовании. Типы инновационных учебных заведений и особенности организации в них учебновоспитательного процесса. Негосударственные учебные заведения. Процедура создания и регламентация деятельности образовательных учреждений. Лицензионная...
10368. Регионализация образования. Состояние и развитие Тульской областной системы образования. Региональная программа развития образования 38 KB
  Регионализация образования. Состояние и развитие Тульской областной системы образования. Региональная программа развития образования. Основные направления экспериментальной инновационной работы в учреждениях образования Тульской области. Регионализация системы ...
10369. Шпаргалка по педагогике (для педагогов) 1.87 MB
  Шпаргалка по педагогике для педагогов 1. Понятие педагогики и этапы ее развития Слово педагогика греческого происхождения. В дословном переводе означает детовождение. В современном понимании педагогика представляет собой совокупность знаний и умений по...
10370. АВГУСТИН Блаженный (Augustinus Sanctus) Аврелий 45.72 KB
  АВГУСТИН Блаженный Augustinus Sanctus Аврелий 13.11.354 Тагаст Сев. Африка Нумидия 28.8.430 Гишюн Сев. Африка христ. теолог представитель зап. патристики. Прошёл через увлечение манихейством и скептицизмом в 387 принял крещение. С 395 епископ Гиппона. Онтология А. и его уч...
10371. АДЛЕР (Adler) Альфред 33.73 KB
  АДЛЕР Adler Альфред 7.2.1870 Вела 28.5.1937 Абердин Шотландия австр. врач и психолог создатель индивидуальной психологии. Примыкал сначала к сторонникам 3. Фрейда затем основал собств. школу получившую наибольшее влияние в 20х гг. с созданием Междунар. ассоциации инд
10372. ФОМА АКВЙНСКИЙ, (Thomas Aquinas) 47.64 KB
  ФОМА АКВЙНСКИЙ Thomas Aquinas 1225 или 122i замок Роккасекка близ Акуино Юж. Италия 7. 3. 1274 монастырь Фоссануова Юж. Италия ср.век философ и теолог систематизатор ортодоксальной схоластики основатель томизма; монахдоминиканец с 1244. В 1567 признан пятым учителем ...