- •Раздел 1. Алгебраические структуры Тема 1.1. Бинарные операции и их свойства
- •Тема 1.2. Алгебраические структуры
- •Тема 1.3. Основные свойства групп
- •Тема 1.4. Поля и кольца
- •Раздел 2. Алгебра множеств Тема 2.1. Основные определения теории множеств
- •Тема 2.2. Подмножество, понятие универсального множества
- •Тема 2.3. Операции над множествами
- •Раздел 3. Основные теоремы комбинаторики
- •Тема 3.1. Метод математической индукции
- •Тема 3.2. Основные принципы комбинаторики
- •Раздел 4. Комбинаторные объекты Тема 4.1. Сочетания
- •Тема 4.2. Размещения и перестановки
- •Раздел 5. Полиномиальные тождества Тема 5.1. Бином Ньютона
- •Тема 5.2. Понятие о методе рекуррентных соотношений
- •Тема 5.3. Метод производящих функций
- •Тема 5.4. Метод траекторий
- •Тема 5.5. Примеры комбинаторных задач
- •Раздел 6. Соответствие, отношение, отображение Тема 6.1. Понятие кортежа. Декартово произведение множеств
- •Тема 6.2. Определения и свойства
- •Тема 6.3. Типы отношений
- •Пересечение и объединение отношений
- •Композиция отображений и отношений
- •Тема 6.5. Решётки
- •Тема 6.4. Верхняя и нижняя границы множества.
- •Раздел 7. Операции булевой алгебры Тема 7.1.Понятие высказывания, простые и составные высказывания
- •Тема 7.2.Операции на множестве высказываний
- •Отрицание
- •Конъюнкция
- •Дизъюнкция
- •«Исключающее или»
- •Импликация
- •Эквивалентность
- •Штрих Шеффера
- •Раздел 8. Законы и тождества Булевой алгебры Тема 8.1.Формулы Булевой алгебры
- •Тема 8.2.Законы и тождества Булевой алгебры
- •Тема 8.3.Составление формулы по заданной таблице истинности
- •Тема 8.4. Двойственность
- •Тема 8.5.Булева алгебра и теория множеств
- •Тема 8.6.Днф, интервалы и покрытия
- •Раздел 9. Функциональная полнота. Алгебра Жегалкина
- •Тема 9.1.Функционально полные системы
- •Тема 9.2.Алгебра Жегалкина и линейные функции
- •Тема 9.3.Замкнутые классы. Монотонные функции
- •Тема 9.4.Теоремы о функциональной полноте
- •Раздел 10. Хорновские формулы
- •Тема 10.1.Задача получения продукции
- •Тема 10.2.Решение задачи о продукции
- •Алгоритм замыкание(X,f)
- •Алгоритм ПрямаяВолна(X,y,f)
- •Алгоритм БыстроеЗамыкание(X,f)
- •Раздел 11. Теория релейно-контактных схем Тема 11.1.Основные понятия
- •Тема 11.2.Основные задачи теории релейно-контактных схем
- •Тема 11.3.Построение машины голосования
- •Тема 11.4.Двоичный сумматор
- •Тема 11.5.Методы упрощения логических выражений. Методы решения логических задач
- •Раздел 12. Логика предикатов Тема 12.1.Определение предиката
- •Тема 12.2.Логические операции над предикатами
- •Тема 12.3.Кванторы
- •Тема 12.4. Истинные формулы и эквивалентные соотношения
- •Тема 12.5.Доказательства в логике предикатов
- •Раздел 13. Теория графов
- •Тема 13.1.Основные определения теории графов
- •Тема 13.2. Способы задания графов
- •Тема 13.3. Отношения порядка и эквивалентности на графе
- •Тема 13.4. Числовые характеристики графа
- •Тема 13.5.Изоморфизм графов
- •Раздел 14. Проблемы достижимости на графах Тема 14.1.Граф достижимости
- •Тема 14.2.Взаимная достижимость, компоненты сильной связности и базы графа
- •Раздел 15. Некоторые классы графов Тема 15.1.Деревья
- •Тема 15.2. Обход графа
- •Тема 15.3. Расстояния. Диаметр, радиус и центр графа. Протяжённости.
- •Раздел 16. Машина Тьюринга
- •Тема 16.1. Формальное описание машины Тьюринга
- •Тема 16.2. Примеры построения машины Тьюринга
- •Тема 16.3. Свойства машины Тьюринга как алгоритма
- •Раздел 17. Машина Поста
- •Тема 17.1. Теоретическая часть. Состав машины Поста
- •Тема 17.2. Применимость программ. Определение результата выполнения программ
- •Раздел 18. Основные понятия теории автоматов Тема 18.1. Общие подходы к описанию устройств, предназначенных для обработки дискретной информации
- •Тема 18.2. Способы задания конечного автомата
- •Тема 18.3. Эквивалентные автоматы
- •Тема 18.4. Автоматы Мура и Мили
- •Тема 18.5. Примеры синтеза автоматов
Раздел 15. Некоторые классы графов Тема 15.1.Деревья
Определение:Деревомназывается связный, ориентированный граф без петель и кратных рёбер, не содержащий в себе циклов, удовлетворяющий следующим условиям:
имеется в точности один узел, называемый корнем, в который не входит ни одно ребро;
в каждый узел, кроме корня, входит ровно одно ребро;
из корня к каждому узлу идёт путь (который, как легко показать единственный).
Деревья являются простейшим видом связных графов. Любое дерево с вершинами содержитребро. Число различных деревьев, которые можно построить навершинах равно.
Определение:Дерево с одной выделенной вершиной называетсякорневым деревом.
Определение:Ориентированный граф, состоящий из нескольких деревьев, называетсялесом.
Определение: Пусть– дерево. Если дуга, тоназываетсяотцомузла, а–сыномузла.
Определение: Если есть путь изв, тоназываетсяпредкомузла, а–потомкомузла.
Определение: Узел без потомков называетсялистом.
Определение: Узели его потомки вместе образуют поддерево леса, и узелназывается корнем этого поддерева.
Определение:Глубинаузлав дереве – это длина пути из корня в.
Определение:Высотаузла в дереве – это длина самого длинного пути из этого узла в какой-нибудь лист.
Определение: Высотой дерева называется высота его корня.
Пример 15.1:
Глубина узла , в данном примере, = 1, а его высота = 2. Высота дерева = 3.
Определение:Упорядоченным деревомназывается дерево, в котором множество сыновей каждого узла упорядоченно. При изображении упорядоченного дерева, как правило, считается, что множество сыновей каждого узла упорядоченно слева направо.
Определение:Бинарнымдеревомназывается такое упорядоченное дерево, что:
каждый сын произвольного узла идентифицируется либо как левый сын, либо как правый сын;
каждый узел имеет не более одного левого и не более одного правого сына.
Обратите внимание, что бинарное дерево не является частным случаем дерева, это совершенно иное, хотя и тесно связанное понятие.
Пример 15.2:
Указанные бинарные деревья различны между собой (в первом случае корень имеет пустое правое поддерево, а во втором левое поддерево пусто), хотя как деревья они изоморфны, и мы можем рассматривать их как одно дерево.
Определение: Бинарное дерево называетсяполным, если для некоторого целого числакаждый узел, глубины меньшейимеет как левого, так и правого сына, и каждый узел глубиныявляется листом.
Полное дерево глубины имеетузлов.
Очень часто используются алгоритмы, которые проходят дерево (посещают каждый его узел) в некотором порядке. Известно несколько способов сделать это. Мы рассмотрим три широко известных способа: прохождение дерева в прямом порядке, обратном порядке и внутреннем.
Будем считать, что – дерево с корнеми сыновьямипри. Приэто дерево состоит из единственного узла.
Прохождение дерева в прямом порядке:
посетить корень ;
посетить слева на право поддеревья с корнями .
Пример 15.3:
Прохождение дерева в обратном порядке:
посетить слева направо поддеревья с корнями ;
посетить корень .
Пример 15.4:
Прохождение дерева во внутреннем порядке:
посетить левое поддерево корня (если оно существует);
посетить корень;
посетить правое поддерево корня (если оно существует).
Пример 15.5:
Прежде чем дать описание одного из этих алгоритмов на некотором более формальном языке, поговорим о способах задания и хранения и бинарных деревьев. Бинарные деревья, как правило, хранятся посредством двух массивов ЛЕВЫЙСЫН и ПРАВЫЙСЫН, где номер элемента массива – это номер узла, а значение этого элемента – номер левого или правого узла – сына. Если элемент - сын отсутствует, то значение равно 0.
Теперь опишем алгоритм нумерации узлов двоичного дерева в соответствии с внутренним порядком. Для этого будем пользоваться неким подобием языка программирования, специально предназначенного для прозрачного и понятного описания алгоритмов.
Вход: Двоичное дерево, представленное массивами ЛЕВЫЙСЫН и ПРАВЫЙСЫН.
Выход: Массив, называемый НОМЕР, такой, что НОМЕР[i] – номер i - того узла во внутреннем порядке.
Метод: Будем использовать глобальную переменную СЧЕТ, значение которой – номер очередного узла в соответствии с внутренним порядком. Начальное значение переменной СЧЕТ = 1.
Программа выглядит так:
begin
СЧЕТ 1
ВНУТРПОРЯДОК(КОРЕНЬ)
End
Procedure ВНУТРПОРЯДОК(УЗЕЛ)
Begin
if ЛЕВЫЙСЫН[УЗЕЛ]0 then
ВНУТРПОРЯДОК(ЛЕВЫЙСЫН[УЗЕЛ]);
НОМЕР[УЗЕЛ] СЧЕТ;
СЧЕТ СЧЕТ+1
if ПРАВЫЙСЫН[УЗЕЛ]0 then
ВНУТРПОРЯДОК(ПРАВЫЙСЫН[УЗЕЛ]);
End
Такая процедура, которая явно или неявно вызывает сама себя, называется рекурсивной. Применение рекурсии часто даёт возможность давать более прозрачное и сжатое описание алгоритма, чем это же можно было бы сделать, не используя рекурсию. Если бы приведённый алгоритм не был записан рекурсивно, надо было бы строить явный механизм для прохождения дерева. Двигаться вниз по дереву нетрудно, но чтобы обеспечить возможность вернуться к предку, надо запомнить всех предков в стеке, а операторы работы со стеком усложнили бы алгоритм, лишив его наглядности.