- •Содержание дисциплины "Дискретная математика" введение
- •Входная контрольная работа
- •1Вариант
- •2 Вариант
- •Раздел 1. Основы теории множеств
- •Тема 1.1 Основные понятия теории множеств.
- •Тема 1.2 Операции над множествами.
- •Самостоятельная работа № 1
- •Тема 1.3 Свойства операций.
- •Контрольная работа
- •1 Вариант
- •2 Вариант
- •Раздел 2. Формулы логики.
- •Тема 2.1 Основные логические операции.
- •Тема 2.2 Формулы логики.
- •Самостоятельная работа №2.
- •Тема 2.3 Дизъюнктивная нормальная форма.
- •Различны все члены дизъюнкции;
- •Тема 2.4 Конъюнктивная нормальная форма.
- •Тема 2.5 Равносильные формулы. Свойства.
- •Раздел 3. Булевы функции.
- •Тема 3.1 Понятие булевой функции.
- •Тема 3.2 Совершенная днф. Совершенная кнф. Совершенной дизъюнктивной формой формулы алгебры высказываний (сднф) называется днф, в которой:
- •Различны все члены дизъюнкции;
- •Самостоятельная работа №5.
- •Тема 3.3 Минимальная днф.
- •Тема 3.4 Представление булевой функции в виде минимальной днф.
- •Самостоятельная работа №6. Самостоятельная работа №7
- •Тема 3.5 Полнота множества функций.
- •Тема 3.6 Важнейшие замкнутые классы.
- •Важнейшие замкнутые классы в р2
- •Тема 3.7 Теорема Поста.
- •Примеры использования теоремы Поста.
- •3. Составим критериальную таблицу для другой полной системы функций из р2: {0, 1, x1x2, x1x2}.
- •Контрольная работа
- •Раздел 4. Предикаты и бинарные отношения.
- •Тема 4.1 Понятие предиката. Область определения и область истинности предиката.
- •Тема 4.2 Логические операции над предикатами.
- •Самостоятельная работа №8.
- •Тема 4.3 Кванторные операции над предикатами.
- •2. Квантор существования
- •- «Все люди любят всех людей».
- •- «Существует человек, который кого-то любит» .
- •- «Существует человек, который любит всех людей».
- •Тема 4.4 Понятие предикатной формулы.
- •Тема 4.5 Равносильность предикатов. Исчисление предикатов.
- •Самостоятельная работа №9.
- •Тема 4.6 Бинарные отношения и их свойства.
- •Самостоятельная работа №10. Контрольная работа
- •Раздел 5. Отображения. Подстановки.
- •Тема 5.1 Отображения и их свойства.
- •Самостоятельная работа №11.
- •Тема 5.2 Композиция отображений и обратное отображение.
- •Тема 5.3 Подстановки. Обратные подстановки. Формула количества подстановок.
- •Самостоятельная работа №12. Контрольная работа
- •1 Вариант
- •2 Вариант
- •3 Вариант
- •4 Вариант
- •5 Вариант
- •Раздел 6. Метод математической индукции.
- •Тема 6.1 Принцип метода математической индукции.
- •Раздел 7. Основы теории графов.
- •Тема 7.1 Понятие неориентированный граф. Основные определения.
- •Лабораторная работа № 1.
- •Тема 7.2 Теорема о сумме степеней вершин графа. Полный граф, его свойства.
- •Лабораторная работа № 2.
- •Тема 7.3 Метрические характеристики графа.
- •Лабораторная работа № 3.
- •Тема 7.4 Двудольные и изоморфные графы.
- •Лабораторная работа № 4.
- •Тема 7.5 Эйлеровы и гамильтоновы графы.
- •Лабораторная работа № 5
- •Тема 7.6 Плоские графы.
- •Тема 7.7 Деревья. Код Пруфера.
- •Тема 7.8 Понятие ориентированный граф (орграф).
- •Тема 7.9 Достижимость вершин в орграфе.
- •Раздел 8. Элементы теории алгоритмов.
- •Тема 8.1 Определение класса финитно-поставленных задач.
- •Тема 8.2 Машины Тьюринга.
- •Тема 8.3 Уточнения понятия алгоритм.
- •Итоговая (выходная) контрольная работа.
Тема 7.7 Деревья. Код Пруфера.
Деревом называется всякий несвязный граф без циклов.
Граф, состоящий из изолированной вершины, тоже считается деревом.
Вершина дерева, степень которой равна 1, называется висячей.
Лесом называется граф представленный в виде объединения деревьев.
Теорема: Если у дерева n вершин, то ребер n-1.
Рассмотрим произвольное дерево с 11 вершинами, пронумерованными в произвольном порядке.
В результате возникает вопрос: сколько существует таких деревьев с 11 вершинами?
Английский математик Кэли нашел ответ на этот вопрос: деревьев с n вершинами можно создать столько, сколько существует последовательностей вида: , где и таких последовательностей будет nn-2.
Немецкий математик Пруффер продолжил решать эту проблему и указал алгоритм, согласно которому любому дереву можно поставить во взаимно-однозначное соответствие – код.
Алгоритм:
выбираем висячую вершину с наименьшим номером.
удаляем ее вместе с принадлежащим ей ребром.
записываем номер вершины полученного дерева ближайшей к удаленной.
п овторяем данные действия до тех пор пока не останется две висячие вершины, связанные между собой ребром.
1. вершина № 2
2. записываем вершину № 1
3. выбираем вершину № 3
4. записываем вершину № 1
и т.д., в результате получаем код: (1, 1, 5, 5, 6, 6, 6, 6, 5)
И наоборот, зная код можно изобразить дерево.
Алгоритм составления дерева по коду:
находим наименьшее натуральное число, которое не встречается в последовательности.
это число – номер вершины, которую необходимо соединить с вершиной, которая встречается первой в коде.
находим следующее число
Дан код (1, 5, 5, 3, 6, 4).
Количество вершин = 8,
наименьшее число, не встречающееся в последовательности – 2
строим эту вершину и соединяем ребром с вершиной №1
аналогично перебираем все цифры не встречающиеся в последовательности до 8.
Тема 7.8 Понятие ориентированный граф (орграф).
Ребро <А,В> называется ориентированным, если одну вершину считают его началом, вторую концом
<А,В>
<В,А>
Граф называется ориентированным, если каждое его ребро ориентировано.
Степенью входа вершины А называется количество ребер входящих в А. Степенью выхода вершины А называется количество ребер выходящих из нее.
Рассмотрим
вершина А:
степень входа – 1, степень выхода – 1;
вершина С:
степень входа – 3, степень выхода – 0;
вершина D:
степень входа – 0, степень выхода – 2.
Стоком называется вершина, степень выхода которой равна 0, а степен7ь входа больше 0.
Источником называется вершина, степень выхода которой больше 0, а степень входа равна 0.
Изолированной вершиной называется вершина, у которой степень входа и степень выхода равны 0.
Путем от вершины А1 до вершины Аn называется такая последовательность ребер, ведущих от А1 до Аn <A1,A2><A2,A3>…<An-1,An>, что конец предыдущего ребра является началом следующего и ни одно ребро не встречается дважды.
Р асстоянием от вершины А до вершины В называется длина наименьшего пути. Если пути от вершины А до вершины В не существует, то расстояние считают равным бесконечности.
S(A,B)=1
S(A,C)=2
S(C,A)=∞
Теорема: Если в графе m вершин, р – ребер, то степень входа А1+ степень входа А2+…+ степень входа Am = степень выхода А1+ степень выхода А2+…+ степень выхода Am = р