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


 

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

18436. Электрические исполнительные механизмы 46.5 KB
  Лекция 20. Электрические исполнительные механизмы. Назначение. Механизмы исполнительные электрические однооборотные постоянной скорости МЭО и МЭОФ предназначены для перемещения регулирующих органов в системах автоматического регулирования технологическими пр
18437. Регулирующие органы 91 KB
  Лекция 21. Регулирующие органы. Регулирующие органы служат для изменения количества вещества или энергии подводимых к объекту регулирования или отводимых от него по определенной программе или поддержание на определенном уровне. Чаще всего с помощью регулирующих
18438. История языка PHP. Установка ПО для работы с PHP 780 KB
  Серверные технологии разработки webсайтов История языка PHP. Установка ПО для работы с PHP. История PHP Язык PHP был разработан как инструмент для решения чисто практических задач. Его создатель Расмус Лердорф хотел знать сколько человек читают его onlineрезюме и написал ...
18439. Конструкции и типы данных PHP 223.5 KB
  Серверные технологии разработки webсайтов Конструкции и типы данных PHP Основной синтаксис Первое что нужно знать относительно синтаксиса PHP – это то как он встраивается в HTMLкод как интерпретатор узнает что это код на языке PHP. В предыдущей лекции мы уже говорили об
18440. Операторы условий и циклов 192 KB
  Серверные технологии разработки webсайтов Операторы условий и циклов Условные операторы Оператор if Это один из самых важных операторов многих языков включая PHP. Он позволяет выполнять фрагменты кода в зависимости от условия. Структуру оператора if можно представит
18441. Функции в PHP 206 KB
  Серверные технологии разработки webсайтов Функции в PHP Функции определяемые пользователем Для чего нужны функции Чтобы ответить на этот вопрос нужно понять что вообще представляют собой функции. В программировании как и в математике функция есть отображение множ...
18442. Работа с массивами в PHP 192.5 KB
  Серверные технологии разработки webсайтов Работа с массивами в PHP Массивы В одной из первых лекций мы рассказывали о том как можно создать массив данных. Напомним что массив можно создать двумя способами: С помощью конструкции array array_name = arraykey1=>value1
18443. Работа со строками в PHP 207 KB
  Серверные технологии разработки webсайтов Работа со строками в PHP Строки Вероятно читатели примерно представляют что такое тип данных строка и как создать переменную такого типа. В одной из первых лекций мы приводили три способа задания строк: с помощью одинарных
18444. Регулярные выражения в PHP 190.5 KB
  Серверные технологии разработки webсайтов Регулярные выражения в PHP Понятие регулярного выражения Регулярное выражение regular expression – это технология которая позволяет задать шаблон и осуществить поиск данных соответствующих этому шаблону в заданном тексте предст