- •Содержание:
- •Тема 1. Основные понятия теории множеств. Способы задания множеств. Операции над множествами. Диаграммы Венна. Свойства теоретико-множественных операций. Представление множеств в эвм. 5
- •Операции над множествами.
- •Свойства теоретико-множественных операций. Представление множеств в эвм.
- •Многоместные отношения. Композиция отношений. Степень и ядро отношений.
- •Свойства отношений. Представление отношений в эвм.
- •Формулы. Реализация функций формулами. Равносильные формулы. Принцип двойственности.
- •Дизъюнктивная нормальная форма.
- •Конъюнктивная нормальная форма.
- •Теорема Поста
- •Геометрическая интерпретация минимизации функций алгебры логики.
- •Метод неопределённых коэффициентов.
- •Метод карт Карно
- •Тема 4. Алгебраические системы. Дистрибутивные решетки. Определение решетки, дистрибутивной решетки. Булева решетка. Алгебраические системы.
- •Группоиды и полугруппы.
- •Понятие группы.
- •Кольца. Тела и поля.
- •Решетки. Диаграмма Хассе.
- •Дистрибутивная решетка.
- •Булева алгебра.
- •Тема 5. Поля Галуа и их применение. Классическая теория Галуа. Расширения полей и их классификация. Сепарабельные и нормальные расширения. Расширения полей q, f_q, c(t).
- •1.2 Расширения полей и их классификация.
- •1.1.Простое расширение поля.
- •1.2.Минимальный полином алгебраического элемента.
- •1.3.Строение простого алгебраического расширения поля.
- •1.4.Освобождение от алгебраической иррациональности в знаменателе дроби.
- •3. Сепарабельные и несепарабельные расширения.
- •Тема 6. Многозначные логики. Возникновение и формализация модальных логик. Применение многозначных логик. Основные понятия
- •Тема 7. Методы пересчета. Перестановки, сочетания, транспозиции. Методы генерирования перестановок: лексикографический порядок, векторы инверсий, вложенные циклы, транспозиция смежных элементов.
- •Тема 8. Производящие функции. Способы построения производящих функций. Пример построения производящей функции при известном рекуррентном соотношении.
- •Тема 10. Синтез автоматов. Абстрактный уровень проектирования автомата.
- •Тема 11. Минимизация числа состояний автомата. Минимизация числа состояний синхронного автомата методом Хафмена.
- •6. Минимизация числа состояний методом таблиц.
- •Тема 13. Автоматы с памятью. Канонический метод структурного синтеза. Построение логической схемы структурного автомата. Графический метод структурного синтеза.
- •Тема 14. Сети Петри и их свойства. Основные понятия сетей Петри. Конечные разметки сети. Ограниченность сети. Моделирование с помощью сетей Петри. Формальное определение сети Петри.
- •Тема 15. Описание систем с помощью сетей Петри. Применение сетей Петри при разработке графического языка программирования.
- •Тема 17. Решение задач с помощью динамических двоичных функций. Синтез логической схемы, реализующей заданную булеву функцию, с использованием блоков исключения одной переменной.
Тема 7. Методы пересчета. Перестановки, сочетания, транспозиции. Методы генерирования перестановок: лексикографический порядок, векторы инверсий, вложенные циклы, транспозиция смежных элементов.
В этом разделе рассматриваются подстановки и перестановки, которые на самом деле являются равнообъемными понятиями. Для вычисления количества перестановок в подразделе 5.1.4 установлена очень простая формула: i'(n) = п!. Применяя эту формулу при решении практических задач, не следует забывать, что факториал — это очень быстро растущая функция, в частности, факториал растет быстрее экспоненты. Действительно, используя известную из математического анализа формулу Стирлинга
или, более точно
нетрудно показать, что
.
Группа подстановок
Взаимно-однозначная функция называется подстановкой на X.
ЗАМЕЧАНИЕ:
Если множество X конечно (\Х\ = п), то, не ограничивая общности, можно
считать, что X = l..n. В этом случае подстановку : 1..n1.n удобно задавать таблицей из двух строк. В первой строке — значения аргументов, во второй — соответствующие значения функции.
Пример:
f=g=
Произведением подстановок f и g называется их суперпозиция fog.
Пример:
fg=
Тождественная подстановка это подстановка е, такая что е(х) = х.
Таблицу обратной подстановки можно получить, если просто поменять местами строки таблицы исходной подстановки.
Таким образом, множество подстановок образует группу относительно операции суперпозиции. Эта группа называется симметрической степени n.
Циклы
Цикл-это последовательность элементов ,…,, такая что
f()=
Цикл длины 2 называется транспозицией.
Замечание:
Из графического представления подстановки наглядно видно происхождение термина «цикл».
Подстановки и перестановки
В таблице подстановки нижняя строка (значения функции) является перестановкой элементов верхней строки (значения аргумента). Если принять соглашение, что элементы верхней строки (аргументы) всегда располагаются в определенном порядке (например, по возрастанию), то верхнюю строку можно не указывать – подстановка определяется одной нижней строкой. Таким образом, подстановки взаимно однозначно соответствуют перестановкам.
Перестановку (и соответствующую ей подстановку) элементов 1,…,nбудем обозначать (,…,), где все- различные числа из диапазона 1,…,n.
Инверсии
Если в перестановке f=() для элементовиимеет место неравенствоприi<j, то пара () называется инверсией. ОбозначимI(f) – число инверсий в перестановкеf.
Теорема: произвольную подстановкуfможно представить в виде суперпозицииI(f) транспозиций соседних элементов.
Доказательство:
Пусть f=(). Переставим 1 на первое место, меняя её местами с соседними слева элементами. Обозначим последовательность этих транспозиций через. При этом все инверсии (и только они), в которых участвовала 1 пропадут. Затем переставим 2 на второе место и т.д. Таким образом,foo…o=eи по свойству группыf=o…o, причем ||+||+…+||=I(f).
Следствие: всякая сортировка может быть выполнена перестановкой соседних элементов.
Алгоритм. Сортировка методом пузырька
Вход: массив А : array [l..n] of В, где значения элементов массива расположены в про извольном порядке и для значений типа D задано отношение <.
Выход: массив А : array [l..n] of D, в котором значения расположены в порядке возра стания.
for г from 1 to n — 1 do
m: = i { индекс кандидата в минимальные элементы } for j from i + 1 to n do
if A\j\ < A[m] then m:= j { новый кандидат в минимальные }
end if
end for
A\i] <-> A[m\ { ставим минимальный элемент на место } end for
Генерация перестановок
На множестве перестановок естественным образом можно определить упорядоченность на основе упорядоченности элементов. А именно, говорят, что перестановка () лексикографически предшествует перестановки (), если&=. Аналогично, говорят, что перестановка () антилексиграфически предшествует перестановке (), если&=.
Следующий алгоритм генерирует все перестановки элементов 1,…,nв антилексиграфическом порядке. МассивP:array[1..n]of1..nявляется глобальным и предназначен для хранения перестановок.
Алгоритм:Генерация перестановок в антилексиграфическом порядке.
Вход: n— количество элементов
Выход: последовательность перестановок элементов 1,...,n в антилексикографическом порядке.
for г from 1 to n do
P[i]: = i { инициализация } end for
Antilex(n) { вызов рекурсивной процедуры Antilex }
Основная работа по генерации перестановок выполняется рекурсивной процедурой Antilex.
Вход: m — параметр процедуры — количество первых элементов массива Р, для которых
генерируются перестановки. Выход: последовательность перестановок 1,..., m в антилексикографическом порядке.
if т = 1 then yield Р { очередная перестановка }
else
for i from 1 to m do
Antilex(m - 1) { рекурсивный вызов } if i < m then
P[i) о P\m] { следующий элемент }
Reverse(m - 1) { изменение порядка элементов }
end if end for end if
Вспомогательная процедура Reverse переставляет элементы заданного отрезка пассива Р в обратном порядке.
Вход: к — номер элемента, задающий отрезок массива Р, подлежащий перестановке в
обратном порядке.
Выход: первые к элементов массива Р переставлены в обратном порядке j : = 1 { нижняя граница обращаемого диапазона }
while j < к do Ptfl « Р[к] j: = j + l k: = k- 1
end while