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


 

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

85308. Календарные праздники и обряды: структура, функции, художественные элементы 35.95 KB
  Основные зимние праздники приходились на январь. Дети девушки и парни под Рождество ходили по домам колядовать Колядовали и в Новый год. Молодежь наряжалась стариками и старухами цыганами гусарами; мазали лица сажей надевали вывороченные наизнанку шубы и ходили по деревне подшучивая над всеми разыгрывая сценки веселясь. Ходили друг к другу в гости обильно угощались блинами оладьями пирогами была и выпивка.
85309. Календарные праздники и обряды на Руси; их связь с зимним и летним солнцеворотами; весенним и осенним равноденствием; с циклами сельскохозяйственных работ; с языческими и христианскими основами веры 35 KB
  Важнейшие на Руси языческие обряды и праздники были слиты с земледельческим трудом с жизнью природы а значит с мифологическими олицетворениями природных сил. Первыми еще в глубокой древности возникли праздники связанные с земледельческим календарем предков восточных славян. Начинаясь в декабре когда солнце поворачивается на лето предвещая скорое пробуждение кормилицы материземли от зимнего сна и заканчиваясь осенью с завершением уборки урожая праздники составляли целостный календарный цикл.
85310. Система церковных праздников 35.79 KB
  Среди двунадесятых праздников три подвижных: Вход Господень в Иерусалим за неделю до Пасхи Вербное воскресенье Вознесение Господне Вознесение в 40й день по Пасхе и день Святой Троицы Пятидесятница Троица в 50й день по Пасхе. Неподвижные великие праздники: Крещение Господне Богоявление Водокрещи Иордань 619 января; Сретение Господне Сретение 215 февраля; Благовещение Пресвятой Богородицы Благовещенье 25 марта 7 апреля; Преображение Господне второй Спас Спас на горе средний Спас Спас яблочный 619...
85311. Классификация традиционных календарных праздников и обрядов русского народа 37.14 KB
  Расписное яйцо было столь важным атрибутом обрядов что длительное время примерно с Х века держался обычай пользоваться специально изготовленными керамическими разукрашенными яйцами писанками. Для землепашца это время критическое все что мог он на полях сделал брошенное зерно дало всходы теперь все зависело от природы а значит от прихоти управляющих природными стихиями существ. И ожидали в это время от русалок не только шалостей и козней но и орошения полей живительной влагой способствующей колошению хлебов. Во время праздника...
85312. Функции фольклора 29.24 KB
  Функции фольклора в целом и отдельных его жанров не могли не изменяться в зависимости от общих изменений структуры всей духовной культуры от типа соотношения фольклорных и условно говоря ldquo;нефольклорныхrdquo; форм и видов духовной культуры. Важнейшие общественные функции фольклора функции народной истории народной философии народной социологии.
85313. Методология и методы изучения народной художественной культуры 33.46 KB
  Виды научных исследований в области НХТ. Теоретические исследования НХК выявление сущности принципов функций закономерностей развития НХТ и т. Фольклористические исследования фиксирующие образцы НХТ выявляющие особенности жанров сказки песни театральные тексты и т. Понятие модели в педагогике возможности педагогического моделирования в разработке направлений развития объединений и организаций занимающихся НХТ.
85314. Традиционное народное жилище: структура, функции 44.65 KB
  Кочевой образ жизни издавна определил тип герметически замкнутого компактного жилищасборноразборной сооружения из решетчатого каркаса и войлочного покрытия круглого в основания и полусферическим верхом. Остов стен составляется из связанных между собой складных деревянных решёток которые определяют размеры и вместимость жилища. Если северная часть считалась почётной то южное пространство примыкающая к двери самая низшая часть жилища. Таким образом круглая юрта оригинальный исторически сложившийся образец жилища идеально...
85315. Научные предпосылки формирования курса «Теория и история народной художественной культуры» 35.12 KB
  Этнология сравнительная дисциплина целью которой является описание культуры а изначально и физических обличий между народами и объяснение таких различий по средствам реконструкции истории развития народов миграции и взаимодействия этносов. Эта концепция рассматривает происхождение культуры и культурных элементов в первобытном состоянии человечества. История культуры представляется как непрерывный процесс прямолинейный процесс перехода от простого к более сложному.
85316. Влияние христианства на содержание и формы бытования народной художественной культуры в России 49.9 KB
  Примерно к VI веку в Византии на смену античной языческой картине мира приходит христианская в центре которой страдающий униженный раздираемый противоречиями маленький греховный человек.Бог безусловно центральный образ в новой византийской картине мира: причина бытия источник совершенства и упорядочения мироздания недостижимая цель познания. Меняются представления о космосе о времени и пространстве о ходе истории: на смену представлениям о замкнутых исторических циклах античной картины мира приходит образ телеологического...