- •Часть 2
- •Часть 2
- •Введение
- •1. Элементы комбинаторики
- •1.1. Простейшие комбинаторные конфигурации
- •Основные правила комбинаторики
- •Выборки элементов без повторений
- •Выборки элементов с повторениями
- •Латинские прямоугольники, конечные проективные плоскости и блок-схемы
- •1.2.1. Латинские прямоугольники
- •1.2.2. Конечные проективные плоскости
- •1.2.3. Блок-схемы
- •Формула включений и исключений
- •Объединение комбинаторных конфигураций
- •1.3.2. Принцип включения и исключения
- •1.3.3. Число булевых функций, существенно зависящих от всех своих переменных
- •1.3.4. Решето Эратосфена
- •Рекуррентные уравнения
- •1.4.1. Определение рекуррентного уравнения
- •1.4.2. Решение линейного однородного рекуррентного уравнения
- •1 (2) .4.3. Решение линейного неоднородного рекуррентного уравнения
- •1.5. Производящие функции
- •1.5.1. Общие сведения о производящих функциях
- •1.5.2. Производящая функция для биноминальных коэффициентов
- •1.5.3. Производящая функция для чисел Фибоначчи
- •1.6.1. Определение z – преобразования
- •1.6.2. Обратное z – преобразование
- •В правой части этого равенства стоит контурный интеграл в z-плоскости по любому замкнутому контуру в области сходимости, охватывающему начало координат.
- •1.6.3. Свойства z-преобразования
- •1.6.4. Использование z-преобразований для решения рекуррентных уравнений
- •1.6.5. Таблица односторонних z-преобразований
- •1.7. Трансверсали и перманенты
- •1.7.1. Множества и мультимножества
- •1.7.2. Трансверсали
- •1.7.3. Пермамент матрицы
- •1.7.4. Число трансверсалей
- •1.8. Матрицы Адамара
- •1.8.1. Определение матрицы Адамара и ее свойства
- •1.8.2. Эквивалентные преобразования матриц Адамара
- •1.8.3. Построение матриц Адамара
- •2. Основы теории конечных автоматов
- •2.1. Понятие конечного автомата
- •2.1.1. Общие сведения о конечных автоматах
- •2.1.2. Абстрактное определение конечного автомата
- •2.2. Эквивалентности в автоматах
- •2.2.1. Основные определения
- •2.2.2. Покрытия и морфизмы
- •2.2.3. Эквивалентные состояния автоматов
- •2.3. Процедура минимизации конечных автоматов
- •2.4. Автоматные функции и эксперименты с автоматами
- •2.4.1. Понятие ограниченно детерминированной функции
- •2.4.2. Моделирование автоматной функции с помощью схемы из функциональных элементов и задержки
- •2.4.3. Пример реализации конечного автомата с помощью сфэз
- •2.4.4. Эксперименты с автоматами
- •2.5. Автоматные языки
- •2.5.1. Представление о формальных языках
- •2.5.2. Алфавит, слово, язык
- •2.5.3. Классификация грамматик и языков
- •2.5.4. Понятие формальной грамматики
- •2.5.5. Автоматные грамматики
- •2.6. Модификации конечных автоматов
- •2.6.1. Частичные автоматы
- •2.6.2. Понятия недетерминированного и вероятностного автоматов
- •2.7. Процедура минимизации частичного автомата
- •2.7.1. Совместимые состояния
- •2.7.2. Техника определения совместимых состояний
- •2.7.3. Построение минимального автомата
- •3. Введение в нечеткую математику
- •3.1. Нечёткие множества
- •3.2. Нечеткие отношения
- •3.3. Нечеткая логика
- •Заключение
- •Библиографический список
- •Оглавление
- •2.7.3. Построение минимального автомата 98
- •Часть 2
- •394026 Воронеж, Московский просп., 14
- •Часть 2
1.2.2. Конечные проективные плоскости
Конечная проективная плоскость – математическая система, составленная из одних элементов, называемых «точками» и из других элементов, называемых «прямыми».
Точки и прямые связаны отношением инцидентности. Предполагается, что существует определенное соотношение «точка P лежит на прямой L» или эквивалентное соотношение «прямая L проходит через точку P».
Это соотношение удовлетворяет постулатам:
Две различные точки лежат на одной прямой .
Две различные прямые проходят через одну и только одну точку .
Существует 4 различных точки плоскости , никакие 3 из которых не лежат на одной прямой.
Постулаты 1 и 2 являются основными. Постулат 3 служит для того, чтобы исключить некоторые вырожденные системы, удовлетворяющие только 1 и 2.
Из постулатов следует: существует 4 различных прямых , никакие 3 из которых, не проходят через одну и ту же точку. Таким образом, предложение, относящееся к проективной плоскости имеет двойственное значение, получаемое заменой слов «точка» и «прямая», а также выражений «точка P лежит на прямой L» и «прямая L проходит через точку P».
Проективная плоскость называется конечной, если она содержит конечное число точек.
Пусть – прямая на конечной проективной плоскости и пусть число всех точек, лежащих на прямой равно . Число называется порядком плоскости .
Теорема. Пусть задана конечная проективная плоскость порядка n. Тогда число точек, лежащих на любой прямой плоскости также, как и число прямых, проходящих через любую точку плоскости равно (n+1). При этом плоскость имеет всего n2+ n+1 точек, и столько же прямых.
Наименьшая проективная плоскость имеет порядок n= 2.
Множество точек 1,2,..,7 образует 7 прямых.
, , , , , ,
1.2.3. Блок-схемы
Блок-схема – система подмножеств конечного множества V, удовлетворяющая следующим условиям:
Она задается упорядоченной парой множеств (V, B), где ,
Элементы множества V называют элементами блок-схемы. Элементы множества B называются блоками.
Элемент ai и блок Bj называются инцидентными, если .
Пусть kj = |Bj|- число элементов, инцидентных блоку Bj, ri – число блоков, инцидентных ai.
- количество блоков, содержащих пару элементов .
Числа называются параметрами блок-схемы.
Если ri = r (i = 1,2,..,v) и kj = k (j= 1,2,..,b), , то блок-схема называется уравновешенной неполной блок-схемой (BIB- схемой) с параметрами .
Если среди чисел , встречаются равно m различных , то блок-схема называется частично уравновешенной неполной блок-схемой с m типами связей (PBIB(m)-схема).
Всякой блок-схеме с v элементами и b-блоками соответствует матрица инцидентности A=(cij), где cij= 1, если и в противном случае (i = 1,2,..,v), (j= 1,2,..,b)
Параметры BIB-схемы связаны соотношениями:
Матрица инцидентности здесь удовлетворяет основному матричному соотношению
(*)
где E – единичная матрица порядка v, I – матрица порядка v, состоящая сплошь из одних единиц.
Существование матрицы, элементы которой 0 и 1, и удовлетворяющей условию (*) является достаточным условием существования BIB-схемы с заданными характеристиками.
BIB-схема, в которой b = v(r = k) называется симметричной блок-схемой или – конфигурацией.
Среди BIB схем выделяются подклассы:
Система Штайнера , «система троек Штайнера» (k = 3).
Адамаровы конфигурации .
Проективные конечные геометрии.
Блок-схемы применяются в планировании экспериментов, теории игр, теории кодировании и других областях.