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


 

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

56257. ИНФОРМАЦИОННЫЕ И АНАЛИТИЧЕСКИЕ ЖАНРЫ РАДИОЖУРНАЛИСТИКИ 1 MB
  В передачах же, ставящих своей целью эмоциональную подачу материала, стоящих где-то на грани между радиоинформацией и радиоисследованием, необходимо говорить о публицистическом методе. Этот метод, как известно, охватывает основные элементы радиожурналистики...
56258. We Study English 51 KB
  Познайомити з дитячою культурою народу, мову якого вивчаємо. Формувати вміння спілкуватися іноземною мовою підготовлено та непідготовлено. Розвивати інтерес до вивчення англійської мови. Виховувати культурних та ввічливих дітей які знають правила поведінки та вміють застосовувати їх на практиці.
56260. Das Aussehen 48.5 KB
  Мета: практична: активізувати граматичні навички з тем «Відмінювання прикметників» та «Ступені порівняння прикметників», відробити надані раніш ЛО...
56261. Висловлення побажань; вживання Subjonctif présent 28.58 KB
  Bonjour, chers élèves! Aujourd’hui on va systématiser nos connaissances du subjonctif. On va aussi pratiquer les manières d’exprimer nos souhaits. Par quels moyens peut-on exprimer nos souhaits: par e-mail, par lettre, coup de téléphone, pendant l’entretien personnel?
56262. Сучасний урок української мови в школі. Навчально-методичний посібник для студентів педагогічних університетів і вчителів 1.79 MB
  Сучасний урок української мови в школі. Урок як основна форма організації навчальної діяльності учнів з української мови. Мета уроку української мови як системне утворення та шляхи її реалізації. Мотиваційне забезпечення навчальної діяльності на уроках української мови.
56263. Спектакль «Суд над Ядерною Енергією» 71.5 KB
  Вступне слово. Сьогодні завершується тиждень безпеки життєдіяльності. І ми зібралися з вами на останньому заході, що проводиться в рамках цього тижня й присвяченій найбільшій та найстрашнішій загрозі для всього людства – використанню ядерної енергії.
56265. Сума кутів трикутника 50 KB
  Обладнання: набір креслярського приладдя; таблиця Сума кутів трикутникамультимедійний проектор компютеркомпютерна презентація. Учитель ставить проблему: що учні знають про кути трикутника Один з варіантів відповіді...