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


 

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

38687. ПРАКТИЧЕСКИЙ КУРС АНГЛИЙСКОГО ЯЗЫКА 5.17 MB
  Образец 1: Techer: How mny books hve you red this yer Student: Mny. White nd hve tlk with Mrs. to hve tlk поговорить; также: to hve smoke покурить: to hve swim поплавать значение однократного действия to be gld радоваться e. djectives which hve two forms of comprison Positive Comprtive Superltive fr old frther более дальний further 1.
38688. МОРФОМЕТРИЧЕСКАЯ СТРУКТУРА ПОПУЛЯЦИЙ ЖУЖЕЛИЦ (COLEOPTERA, CARABIDAE) В АНТРОПОГЕННЫХ ЛАНДШАФТАХ 701.5 KB
  Среди животных быстро и адекватно реагирующих на изменения в окружающей среде особую группу составляют жужелицы Coleopter Crbide. Жужелицы одни из немногих видов почвенных обитателей педобионтов которые встречаются в импактных зонах промышленных источников и могут быть использованы для оценки антропогенных влияний на биоту. С помощью анализа динамики морфометрической структуры популяций жужелиц создается возможность проследить процесс адаптации к меняющимся условиям среды.
38689. ВЛИЯНИЕ КРИМИНАЛИЗАЦИИ ОБЩЕСТВА НА ПРАВОВОЕ СОЗНАНИЕ УЧАЩЕЙСЯ МОЛОДЕЖИ 109 KB
  Современная российская молодежь в полной мере испытывает на себе негативные последствия глубокой социальной трансформации общества которая сопровождается процессом интенсивной криминализации. рост количества преступлений и правонарушений совершенных молодежью говорит о необходимости выработки эффективных мер противодействия негативному влиянию криминального общества на подрастающее поколение в первую очередь на правовое сознание молодежи. Одним из условий успешного решения этой проблемы является научное исследование процесса криминализации...
38690. ОБЩИЙ АЛГОРИТМ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ АДАПТИВНО-ЛАНДШАФТНЫХ СИСТЕМ ЗЕМЛЕДЕЛИЯ И АЛГОРИТМ АВТОМАТИЗИРОВАННОГО ФОРМИРОВАНИЯ СИСТЕМЫ МАШИН ДЛЯ АДАПТИВНО-ЛАНДШАФТНЫХ СИСТЕМ ЗЕМЛЕДЕЛИЯ 164.5 KB
  Целью работы является разработка алгоритмов автоматизированного проектирования адаптивноландшафтных систем земледелия АЛСЗ и систем машин для адаптивно ландшафтных систем земледелия СМ АЛСЗ. Основные задачи: Для достижения цели необходимо в ходе выполнения теоретических и экспериментальных исследований решить следующие задачи: Исследовать существующие методы экспертного проектирования АЛСЗ и СМ АЛСЗ. Провести анализ существующих алгоритмов автоматизированного проектирования АЛСЗ и СМ АЛСЗ. Разработать общий алгоритм...
38691. Тактика хирургического лечения повреждений передней крестообразной связки коленного сустава с учетом объективных и субъективных особенностей пациента 105.5 KB
  Как показал анализ отдаленных результатов операций пластики передней крестообразной связки выполненных в различных лечебных учреждениях и различными способами наряду с хорошими результатами и полным восстановлением функции оперированного сустава отмечаются и такие осложнения как ограничение движений в оперированном суставе разрывы растяжение трансплантата со всеми вытекающими последствиями Сименач Б. Большое количество способов восстановления передней крестообразной связки коленного сустава свидетельствует об отсутствии оптимального...
38692. Выбор и установка прицела и точки прицеливания при стрельбе по движущимся целям. Виды движения цели 208 KB
  Для определения упреждения при стрельбе по целям имеющим фланговое движение под прямым углом к направлению стрельбы руководствоваться этой таблицей: Пример: Дальность стрельбы 600 метров скорость цели 3 м сек движение фланговое. Решение: По таблице смотрим на дистанции 600 метров упреждение для скорости передвижения 3 м сек = 300 см.Стрельба из стрелкового оружия по воздушным целям самолетам вертолетам и парашютистам без зенитных прицелов ведется на расстоянии 500 метров не больше с прицелом...