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


 

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

12897. Невід’ємне право на життя. Алгоритм поведінки в суспільстві законослухняної особистості 22.85 KB
  Тема : Проведення профілактично виховної бесіди Невідємне право на життя. Алгоритм поведінки в суспільстві законослухняної особистості Місце проведення: Спортивна секція з рукопашного бою ОФРБ приміщення спортивного залу Миколаївського НВК Світанок. ...
12898. ГЕТЬ ПАЛІННЯ! МИ - ЗДОРОВЕ ПОКОЛІННЯ 20.51 KB
  Виховна година. Тема уроку: ГЕТЬ ПАЛІННЯ МИ ЗДОРОВЕ ПОКОЛІННЯ Мета уроку: Інформативновиховна: інформування молоді про негативний вплив тютюну на здоровя не лише того хто палить але й оточуючих; інформування про ризик ро...
12899. Коспект виховного заходу. Моя майбутня професія 35.01 KB
  Коспект виховного заходу на тему: Моя майбутня професія План провеведення: Вступ вибір професії як вибрати професію після школи 3. Типові помилки вибору 4. як вибрати професію по знаку зодіаку 5. тест Холланда У людин
12900. Українські вишиванки - наче райдужні світанки 25.01 KB
  Виховна година Українські вишиванки наче райдужні світанки. Музика пісні Сучасна народна вишивка розвивається на основі традиційної спадщини минулого. Оздоблювали вишивкою житло жіночі та чоловічі сорочки свити кожухи головні убори рушники. У всіх наро...
12901. Виховна година. Ти і твої друзі 26.51 KB
  Виховна година Ти і твої друзі Мета: розкрити значення дружби в житті людини; навчити дітей правильно вибирати друзів знайомитися спілкуватись і товаришувати. Обладнання: Фігурки феї Уваги і чаклунки Доброти аркуші €œусмішки€ мячик пелюстки €œчарівної квітки...
12902. Україна наш спільний дім 27.87 KB
  Виховний урок Україна наш спільний дім Тема: Україна наш спільний дім Мета: поглибити знання учнів про незалежну Україну та її державні символи проаналізувати етапи здобуття українським народом державної самостійності; розвивати логічне мислення вміння порівню
12903. ДЕСЯТЬ МІФІВ ПРО ТОРГІВЛЮ ЛЮДЬМИ 27.19 KB
  Виховна година ДЕСЯТЬ МІФІВ ПРО ТОРГІВЛЮ ЛЮДЬМИ Олександр зі Львова нелегально виїхав до Іспанії разом з дружиною і працював там на будівництві. Одного разу він упав з драбини і сильно забився. Звичайно ніякої страховки у нього не було а працедавець умив руки. Коли чол...
12904. Дружба єднає щирі серця 28.2 KB
  Виховна година у 6 класі Тема. Дружба єднає щирі серця. Навчальна мета: : Поглибити і розширити поняття у дітей про дружбу навчити учнів сприймати ситуації аналізувати їх та знаходити шляхи виходу; допомогти усвідомити значимість слова друг; сприяти виникненню др
12905. Однокласник, товариш, друг. Способи вирішення суперечок та конфліктів. 20.01 KB
  Тема: однокласник товариш друг. Способи вирішення суперечок та конфліктів. Мета: розглянути товариськість як обєктивне явище нашого життя як спосіб співіснування людей; формувати уявлення учнів про різні варіанти людського спілкування; учити уникати конфліктних си