- •Русаков Алексей Михайлович
- •Лекции по дисциплине «Дискретная математика»
- •Введение.
- •Теория множеств.
- •Понятие множества. Операции над множествами.
- •Определение.
- •Определение.
- •Определение.
- •Пример.
- •Свойства операций сложения и пересечения множеств.
- •Определение.
- •Замечание.
- •Примеры.
- •Счётные множества. Теорема Кантора.
- •Определение.
- •Примеры счётных множеств.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Задачи для самостоятельного решения.
- •Решите задачи № 1.30 1.39 с использованием диаграммы Эйлера-Венна.
- •Бинарные отношения в теории графов.
- •Например:
- •Матрицы смежности и инцидентности.
- •Пример.
- •Маршруты, цепи и простые цепи.
- •Определение
- •Расстояние и протяжённость в графе.
- •Деревья.
- •Примеры:
- •Например:
- •Помеченные графы. Перечисление помеченных деревьев.
- •Пример:
- •Теорема Келли.
- •Задача о кратчайшем соединении.
- •Задача о кратчайших путях.
- •Эйлеровы цепи, критерий Эйлеровости. Задача о Кёнигсбергских мостах.
- •Доказательство:
- •Достаточность.
- •Индуктивный переход.
- •Гамильтовы циклы.
- •Пример:
- •Примеры задач и упражнений.
- •Решение.
- •Задачи для самостоятельного решения.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение группы.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение и способы описания формальных грамматик.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теория автоматов.
- •Основные понятия теории автоматов.
- •Определение.
- •Способы задания автоматов. Таблица переходов.
- •Определение.
- •Определение.
- •Способы задания автоматов. Граф автомата.
- •Определение.
- •Способы задания автоматов. Матрица переходов и выходов. Определение.
- •Машины Тьюринга и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Машины Тьюринга с двумя выходами.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматы с магазинной памятью и бесконтекстные языки.
- •Определение.
- •Определение.
- •Модель дискретного преобразователя Глушкова в. М. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Понятие об абстрактном автомате и индуцируемом им отображении. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматные отображения и события. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теорема.
- •Регулярные языки и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Правила подчинения мест в регулярных выражениях.
- •Определение.
- •Определение.
- •Правила построения основного алгоритма синтеза конечных автоматов.
- •Пример.
- •Автомат Мили.
- •Определение.
- •Определение.
- •Автомат Мура.
- •Определение.
- •Определение.
- •Теория булевых функций.
- •Связь булевых функций и схем из функциональных элементов и контактных схем. Определение.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Замечание.
- •Теорема. (Формулы разложения Клода Шеннона.)
- •Доказательство:
- •Замечания.
- •Основные свойства булевых функций. Замечание.
- •Определение.
- •Примеры задач и упражнений. Пример 1
- •Доказательство
- •Задачи для самостоятельного решения.
- •Элементы комбинаторики.
- •Основные понятия комбинаторики. Определение.
- •Определение.
- •Доказательство.
- •Теорема – правило включения-исключения.
- •Доказательство.
- •Доказательство.
- •8.2. Формулировка задания.
- •Определение.
- •Пример.
- •Переходы можно представить также с помощью таблицы и схематически:
- •Определение.
- •Последовательность выполнения.
- •Методический пример.
- •Контрольная распечатка.
- •Замечания.
- •Отчет по практической работе.
- •Контрольные вопросы
- •Варианты заданий.
- •Домашняя работа №1. По всей теории
- •Домашняя работа №2. Способы задания графов
- •8.03.2. Правила регулярного выражения.
- •Установка необходимого программного обеспечения.
- •Замечания.
- •Методический пример.
- •Контрольная распечатка.
- •Отчет по практической работе.
- •Контрольные вопросы.
- •Варианты заданий.
- •Дополнительные материалы.
- •Биография Георга Кантора (основатель теории множеств).
- •Город Калининград (Кёнигсберг).
- •Список литературы.
-
Помеченные графы. Перечисление помеченных деревьев.
Определение.
Граф с вершинами называется помеченным, если его множество вершин .
Определение.
Помеченные графы и с вершинами называются изоморфными, если существует биективное отображение такое, что (композиция) .
Замечание.
Это определение похоже на определение изоморфизмов теории графов, отличие состоит в том, что изоморфизм графов реализуется парой биективных отображений , , а — тождественное отображение.
Пример:
изоморфен как помеченный граф, графу и не изоморфен как помеченный графу .
Ясно, что в обычном смысле ,, изоморфны.
Задача.
Сколько существует не изоморфных между собой неориентированных помеченных деревьев с вершинами.
Обозначим число неизоморфных помеченных деревьев через . Ясно, что
Теорема Келли.
Свои результат по перечислению деревьев А. Келли успешно применил в жизни для определения количества химических изомеров углеродов CnH2n+2.
Структурные формулы таких молекул таких соединений (вершины — атомы, дуги — валентные связи) представляют собой деревья.
Важным для приложений классом ориентированных деревьев являются корневые, или растущие деревья, то есть такие, у которых существует вершина называемая корнем, из которой существуют простые пути во все остальные вершины (в силу общих свойств деревьев путь из корня в каждую вершину — единственный).
Вершины корневого дерева отличные от корня и висячих называют промежуточными. Такие структуры принято использовать для организации систем хранения информации, в частности, такими являются компьютерные файловые системы. Корневое дерево файловой системы обычно называют деревом директорий, в котором корень – корневая директория, промежуточные вершины – поддиректории, а висячие вершины – отдельные файлы или пустые поддиректории.
-
Задача о кратчайшем соединении.
Известны точки, в которых будут расположены населённые пункты (A,B,C,D,E) и известны трасы дорог (I,II,III,IV,V,VI,VII,VIII,IX,X), которые можно построить, а также стоимости из строительства (1,2,3,4,5,6).
Ясно, что сформулированная задача может быть формализована с помощью теории графов.
Определение.
Взвешенным графом будем называть четверку , где — граф, .
Отображение называется весовым отображением.
Если , то называют весом дуги .
Если — путь или цепь на графе , то её весом называют величину: .
Весом графа называют величину .
Аналогично определяется вес подграфа и частичного графа.
Сформулируем задачу о соединении городов на языке теории графов: Дан конечный связный взвешенный граф . Требуется найти связный частичный граф минимального веса.
Определение.
Покрывающим деревом связного графа называется его частичный граф, который является деревом.
Если не является связным графом, то говорят о покрывающем лесе, то есть о деревьях, покрывающих его компоненты связности.
Теорема.
Решение задачи о соединении городов — покрывающее дерево.
Последовательность дуг покрывающего дерева минимального веса может быть найдена с помощью алгоритма Краскала. (В некоторых изданиях Крускала.)