71828

Исследования задач о двух ортогональных латинских квадратах

Курсовая

Экономическая теория и математическое моделирование

Вывести формулу по которой из значений элементов двух ортогональных латинских квадрата порядка n можно получить значения элементов нового латинского квадрата порядка n. Пример латинского квадрата 3го порядка: Теоремы Теорема 1 Для n 1 существует не более n−1 попарно...

Русский

2014-11-12

190 KB

2 чел.

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

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

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

«Исследования задач о двух ортогональных латинских квадратов»

Выполнил: студент гр. АТР-131                                                                                          Косцов Игорь

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

Воронеж 2013 г.

Содержание

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

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

Решение……………………………………………………………………………………7

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

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


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

Вывести формулу, по которой из значений элементов двух ортогональных латинских квадрата порядка n можно получить значения элементов нового латинского квадрата порядка n.

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

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

                                                            

Теоремы

Теорема 1 Для n > 1 существует не более n−1 попарно ортогональных латинских квадратов размера n × n.

Теорема 2 Если существует система из n − 1 попарно ортогональных латинских квадратов размера n × n, то существует конечная проективная плоскость порядка n.

Теорема 3 (Эйлер — Тарри) Не существует двух ортогональных латинских квадратов 6 × 6.

Теорема 4 Для любого r > 0 и любого простого числа p существует система из pr−1 попарно ортогональных латинских квадратов размера pr × pr.

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

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

                                 

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

                                                          

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

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

Латинский квадрат можно рассматривать как ортогональный массив. Меняя порядок элементов в каждой упорядоченной тройке этого массива, можно получить 6 латинских квадратов, которые называются парастрофами. В частности, парастрофом является латинский квадрат, полученный в результате транспонирования.

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

Два латинских квадрата L=(lij) и K=(kij) n-го порядка называются ортогональными, если все упорядоченные пары (lij,kij) различны. Пример двух ортогональных латинских квадратов и соответствующие им упорядоченные пары:

                  

Эйлер называл такие квадраты "полными". В его честь в научной литературе их раньше называли "эйлеровыми" или "греко-латинскими" (так как Эйлер использовал буквы греческого алфавита для квадрата, ортогонального латинскому).

Свойством ортогональных латинских квадратов является то, что при наложении двух квадратов порядка n, все пары получившихся чисел оказываются различными.

Ортогональные латинские квадраты существуют для любого n, не равного 2 и 6.

Применение

Латинские квадраты находят широкое применение в алгебре, комбинаторике, статистике, криптографии, теории кодов и многих других областях.
Решение

Идеальный квадрат порядка n=4k, k=2, 3, 4… строится из двух латинских ортогональных квадратов по следующей формуле:

cij = n*aij + bij + 1

где aij – элементы первого латинского квадрата, bij  – соответствующие элементы второго латинского квадрата, cij – соответствующие элементы идеального квадрата.

Замечу, что 1 в этой формуле прибавляется для того, чтобы превратить квадрат, заполненный числами от 0 до n2-1, в традиционный квадрат, заполненный числами от 1 до n2. Можно и не прибавлять 1, тогда получится совершенный квадрат, заполненный числами от 0 до n2-1.

                                           Способ построения

1 этап. Строим обобщённый латинский квадрат порядка n следующим образом: каждая строка нижней половины квадрата заполняется путём последовательного чередования чисел i  и n-i-1, где i – порядковый номер строки (строки нумеруются снизу вверх целыми числами от 0 до n-1); верхняя половина квадрата получается из нижней отражением относительно вертикальной оси симметрии.

2 этап. Строим второй обобщённый латинский квадрат из первого. Для этого надо повернуть построенный на первом этапе квадрат на 90 градусов по часовой стрелке. Замечу, что полученные таким образом два латинских квадрата будут ортогональными.

3 этап. Строим совершенный квадрат следующим образом. Обозначим элементы первого латинского квадрата aij, элементы второго латинского квадрата – bij, тогда каждый соответствующий элемент совершенного квадрата cij получается по формуле:

cij = n*aij + bij + 1

Существует простой способ построения латинских квадратов порядка n. Пусть а1, а2,…аn – любая перестановка чисел 1, 2,……n. Сдвинем ее на один шаг аn, а1, …аn-1. Данная операция (перестановка ) повторяется n-1 раз. Например, пусть n=8, перестановка чисел в каждой последующей строке квадрата буде осуществляться 7 раз.

                          

Построение ортогональных квадратов – сложная комбинаторная задача. Для её решения применяются как алгебраические конструкции, так и комбинаторные (трансверсали, ортогональные массивы, дизайны, блок-схемы, тройки Штейнера и др.) Существует несколько подходов к решению этой задачи, их можно разделить на две группы:

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

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

Заключение

Таким образом, я исследовал задачу о двух ортогональных латинских квадратах и вывел формулу, по которой из значений элементов двух ортогональных латинских квадрата порядка n можно получить значения элементов нового латинского квадрата порядка n.

 


Используемая литература:

Холл М. Комбинаторика, пер. с англ. М. 1970.

Сачков В. Н. Комбинаторные методы дискретной математики. М. 1977.

Малых А. Е., Данилова В. И. Об историческом процессе развития теории латинских квадратов и некоторых их приложениях // Вестник Пермского Университета. 2010.

Тужилин М. Э. Об истории исследований латинских квадратов // Обозрение прикладной и промышленной математики. 2012. Том 19, выпуск 2.  

Энциклопедический словарь юного математика/ сост. А.П. Савин-3-е изд. М., Педагогика-Пресс, 1999.

Латинские квадраты: Метод. указ. и задачи по факультативному курсу / Гонина Е.Е. Пермь, 1991.

Математика. школьная энциклопедия /гл. ред. С.М. Никольский-М.: Большая российская энциклопедия; Дофа, 1997.

PAGE   \* MERGEFORMAT10


 

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

81087. ПРИОРИЕТЫ БЮДЖЕТНО-НАЛОГОВОЙ ПОЛИТИКИ РФ 45.51 KB
  Полнота бюджета, как правило, прямо пропорциональна благосостоянию граждан. Бюджет, его формирование и статьи расходов являются важным разделом в экономической науки, требующим большого внимания со стороны не только занимающих высокие посты экономистов и политиков, но и рядовых граждан.
81088. Электронные выпрямители, преобразователи, защита электронных устройств и основные характеристики 468.06 KB
  Инвертор который формирует частоту напряжения электродвигателя. Преобразователи частоты различаются по режиму коммутации используемому для регулирования напряжения питания электродвигателя.
81089. СОЗДАНИЕ ГОСУДАРСТВЕННОГО СТАНДАРТА ISO 21500:2012 30.93 KB
  Задачей рабочей группы по созданию стандарта было взять за основу опыт существующих организаций по управлению проектами (Института управления проектами PMI (США), Британского института стандартизации BSI и Международной ассоциации управления проектами IPMA) и свести его в лучшую практику – универсальный стандарт.
81090. Изменения в системе государственного управления при правлении Ивана III 50 KB
  Иван III заложил основы российского самодержавства не только значительно расширив территорию своего государства но и укрепив его политический строй государственный аппарат резко возвысив международный престиж Москвы. Иван III явился фактическим создателем Московского государства.
81091. Разработки и построение моделей социальных процессов для определения сущности, областей применения и наиболее эффективных методов моделирования 23.61 KB
  Актуальность темы состоит в том что в настоящее время нельзя назвать область человеческой деятельности в которой в той или иной степени не использовались бы методы моделирования. Остановимся на философских аспектах моделирования а точнее общей теории моделирования. Методологическая основа моделирования.
81092. Манипуляции в деловом общении и способы их нейтрализации 30.02 KB
  Очень важны психологические аспекты делового общения. Вопрос, с которым постоянно сталкиваются деловые люди, как построить беседу, переговоры. Важно понимать общие закономерности делового общения, что позволит анализировать ситуацию, учитывать интересы партнера, говорить на общем языке.
81093. Трансакционные издержки и их виды 30.14 KB
  Трансакционные издержки центральная объясняющая категория всего неоинституционального анализа. Ортодоксальная неоклассическая теория рассматривала рынок как совершенный механизм где нет необходимости учитывать издержки по обслуживанию сделок.
81094. England. Education and Architecture 129.3 KB
  England is a country that is part of the United Kingdom. It shares land borders with Scotland to the north and Wales to the west. The Irish Sea lies north west of England, whilst the Celtic Sea lies to the southwest. The North Sea to the east and the English Channel to the south separate England from continental Europe.
81095. Системный анализ безопасности 31.01 KB
  Безопасность жизнедеятельности как сравнительно новая область науки, которая образовалась на стыке естественных, гуманитарных и технических наук, использует методы этих наук, вместе с тем разрабатывает свои собственные методы. Комплексный характер БЖД требует использования комплекса методов других наук.