нет. Учебное пособие в оронеж 2011 фгбоу впо Воронежский государственный технический университет

• Название: Учебное пособие в оронеж 2011 фгбоу впо Воронежский государственный технический университет
• Дата: 23.12.2020
• Размер: 0.65 Mb.
• Имя файла: Teoria_avtomatov.docx
• Тип: Учебное пособие; #163524
• страница: 3 из 17

Латинские прямоугольники, конечные проективные плоскости и блок-схемы

1.2.1. Латинские прямоугольники

Пусть дано множество S из n элементов. Латинский прямоугольник, основанный на множестве S, есть прямоугольная таблица.

Каждая строка – упорядоченная выборка элементов множества S длины s, каждый столбец – упорядоченная выборка элементов множества S длины r, причем , .

Обозначим элементы множества S через 1,2,..,n. Предположим, что s = n. Тогда латинский прямоугольник содержит в каждой строке перестановку элементов 1,2,..,n. Эти перестановки выбраны так, что ни один столбец не содержит повторяющихся элементов.

Латинский прямоугольник называется нормализованным, если его первая строка записана в естественном порядке следования элементов 1,2,..,n.

Теорема 1. Для любых чиселсуществует латинский прямоугольник.

Доказательство. Будем «заселять» наш m-этажный «дом» с верхнего этажа. На m-м этаже «расселим» числа 1, 2, 3,..., n в их естественном порядке. На (т—1)-м этаже «расселение» начнем с двойки: 2, 3,..., п,1; на (т—2)-м этаже — с тройки: 3, 4, ..., п, 1, 2, и так далее; наконец, на 1 -м этаже «расселение» начнем с числа т: т,т+1, ...» ", 1. 2,..., т—1. Тогда «дом» будет «заселен» так, как это сделано в таблице. При таком «заселении» не будет двух одинаковых «жильцов», находящихся на одном «этаже» или в одном «подъезде». Следовательно, перед нами — «т-этажный» латинский прямоугольник длиной п. Значит, латинские тхп-прямоугольники существуют.

Таблица 2

1	2	3	…		n
2	3	4	…	n	1
…	…	…	…	…	…
m			…

Перейдем теперь к подсчету числа латинских прямоугольников. Особенно просто решается задача для одноэтажных прямоугольников.

Теорема 2. Число латинских 1хn-прямоугольников равно

Доказательство. Латинский 1хn – прямоугольник - это просто произвольная перестановка из п чисел. Таких перестановок всего п! (на первое место ставили любое из п чисел, на второе - любое из (п-1) оставшихся, на третье - любое из (п-2) оставшихся после этого и т. д.).

Перейдем к 2хn - прямоугольникам. Верхняя строка этого прямоугольника - любая перестановка.

Нижняя строчка - перестановка, в которой на каждом месте стоит число, не равное числу, стоящему на том же месте в первой перестановке. Если мы произвольным образом переставим столбцы нашего прямоугольника, он останется латинским, и при этом верхнюю перестановку можно сделать любой. Из этого видно, что какую бы конкретную перестановку мы ни взяли, число латинских прямоугольников, у которых верхняя строчка совпадает именно с этой перестановкой, будет одним и тем же для всех перестановок. Латинский 2хn-прямоугольник будет нормализованным, если в его верхней строчке числа стоят подряд: 1, 2, 3, ..., (п-1), п. Из этого следует, что число L(2, п) латинских 2хn-прямоугольников равно числу нормализованных латинских 2хn-прямоугольников, умноженному на число перестановок п чисел, т. е.

Для числа нормализованных латинских 2хn-прямоугольников имеется несколько изящных формул.

Теорема 3. (Формула Эйлера).

Это, как говорят, рекуррентная формула: если мы знаем и , а, очевидно, =0 и =1, то мы можем найти с ее помощью последующие :

и т. д.

Доказательство. Всякую перестановку можно записать как систему циклов. Это делается так. Пусть, скажем, на 1-м месте стоит , пишем . Если на -м месте стоит , напишем . Затем и так до тех пор, пока мы снова не дойдем до единицы. Затем берем самое маленькое из чисел, не вошедших в наш цикл, и строим цикл, начиная с него. В конце концов все п чисел окажутся стоящими в циклах. Число циклов может быть любым от 1 до n, и длина цикла может быть любой от 1 до п. Наше условие - что ни одно число не стоит на своем месте - запрещает циклы длиной 1.

Теперь построим по нашей перестановке перестановку длиной п-1 или п-2 и тоже без циклов длиной 1. Найдем на одном из циклов число п. Если длина этого цикла больше двух, мы просто выбросим п и соединим «накоротко» pсq. Если же п входит в цикл длиной 2, например в изображенный на рисунке 5, мы просто выбросим этот цикл и уменьшим все числа от k+1 до п-1 на единицу:

, .

В первом случае получится перестановка (п-1) чисел, во втором случае – перестановка (п-2) чисел. Сколькими способами у нас может получиться перестановка (п-1) чисел? Ясно, что (п-1) способами: чтобы вернуться к перестановке длиной п, мы должны разорвать любую стрелку (а их (п-1) пар) и вставить туда п: . Сколькими способами получается перестановка (п-2) чисел? Снова (п-1) способами: мы добавляем цикла , где k - любое число от 1 до (п-1), и увеличиваем на единицу числа . Значит

что и требовалось.

Обозначая через L(r, n) число латинских прямоугольников, а K(r, n) – число нормализованных латинских прямоугольников.

Задача о перечислении латинских прямоугольников в общем случае не решена в общем случае. Однако, известно, что:

Формула для K(3, n) известна, но имеет сложное выражение.

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

Латинский квадрат может рассматриваться, как таблица умножения в общих алгебраических системах.

I_n – число квадратов порядка n, в которых элементы первой строки и первого столбца расположены в естественном порядке.

Таблица 3

n	1	2	3	4	5	6	7
In	1	1	1	4	56	9408	16947080

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

- элемент, расположенный на пересечении i-й строки и j-го столбца матрицы, полученной наложением латинских квадратов A и B. Для всех есть пары ортогональных квадратов. Для n= 6 таких пар нет.

Несколько латинских квадратов одного порядка называются попарно ортогональными, если любые 2 из них ортогональные.

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

1.2.2. Конечные проективные плоскости

Конечная проективная плоскость – математическая система, составленная из одних элементов, называемых «точками» и из других элементов, называемых «прямыми».

Точки и прямые связаны отношением инцидентности. Предполагается, что существует определенное соотношение «точка P лежит на прямой L» или эквивалентное соотношение «прямая L проходит через точку P».

Это соотношение удовлетворяет постулатам:

1. 
   Две различные точки лежат на одной прямой .
   
2. 
   Две различные прямые проходят через одну и только одну точку .
   
3. 
   Существует 4 различных точки плоскости , никакие 3 из которых не лежат на одной прямой.
   

Постулаты 1 и 2 являются основными. Постулат 3 служит для того, чтобы исключить некоторые вырожденные системы, удовлетворяющие только 1 и 2.

Из постулатов следует: существует 4 различных прямых , никакие 3 из которых, не проходят через одну и ту же точку. Таким образом, предложение, относящееся к проективной плоскости имеет двойственное значение, получаемое заменой слов «точка» и «прямая», а также выражений «точка P лежит на прямой L» и «прямая Lпроходит через точку P».

Проективная плоскость называется конечной, если она содержит конечное число точек.

Пусть – прямая на конечной проективной плоскости и пусть число всех точек, лежащих на прямой равно . Число называется порядком плоскости .

Теорема. Пусть задана конечная проективная плоскость порядка n. Тогда число точек, лежащих на любой прямой плоскости также, как и число прямых, проходящих через любую точку плоскости равно (n+1). При этом плоскость имеет всего n²+ n+1 точек, и столько же прямых.

Наименьшая проективная плоскость имеет порядок n= 2.

Множество точек 1,2,..,7 образует 7 прямых.

, , , , , ,

1.2.3. Блок-схемы

Блок-схема – система подмножеств конечного множества V, удовлетворяющая следующим условиям:

Она задается упорядоченной парой множеств (V, B), где ,

Элементы множества Vназывают элементами блок-схемы. Элементы множества B называются блоками.

Элемент a_iи блок B_jназываются инцидентными, если .

Пусть k_j = |B_j|- число элементов, инцидентных блоку B_j, r_i – число блоков, инцидентных a_i.

- количество блоков, содержащих пару элементов .

Числа называются параметрами блок-схемы.

Если r_i = r(i = 1,2,..,v) и k_j = k (j= 1,2,..,b), , то блок-схема называется уравновешенной неполной блок-схемой (BIB- схемой) с параметрами .

Если среди чисел , встречаются равно m различных , то блок-схема называется частично уравновешенной неполной блок-схемой с m типами связей (PBIB(m)-схема).

Всякой блок-схеме с vэлементами и b-блоками соответствует матрица инцидентности A=(c_ij), где c_ij= 1, если и в противном случае (i = 1,2,..,v), (j= 1,2,..,b)

Параметры BIB-схемы связаны соотношениями:

Матрица инцидентности здесь удовлетворяет основному матричному соотношению

(*)

где E – единичная матрица порядка v, I – матрица порядка v, состоящая сплошь из одних единиц.

Существование матрицы, элементы которой 0 и 1, и удовлетворяющей условию (*) является достаточным условием существования BIB-схемы с заданными характеристиками.

BIB-схема, в которой b= v(r = k) называется симметричной блок-схемой или – конфигурацией.

Среди BIB схем выделяются подклассы:

1. 
   Система Штайнера , «система троек Штайнера» (k = 3).
   
2. 
   Адамаровы конфигурации .
   
3. 
   Проективные конечные геометрии.
   

Блок-схемы применяются в планировании экспериментов, теории игр, теории кодировании и других областях.