- •Содержание дисциплины "Дискретная математика" введение
- •Входная контрольная работа
- •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 – количество вершин, p – количество ребер
n=4, p=6.
n =3, p=0.
n=5, p=2.
A
Теоремой называется необходимое и достаточное условие, что два рисунка изображают один и тот же граф.
Теорема: Для того, чтобы два рисунка изобразили один и тот же граф необходимо и достаточно, чтобы между вершинами на этих рисунках существовало такое взаимно-однозначное соответствие, при котором выполнялись бы два условия:
Две вершины графа на первом рисунке соединены ребром, когда соответствующие им вершина на втором рисунке соединены ребром.
Две вершины графа на втором рисунке соединены ребром, когда соответствующие им вершина на первом рисунке соединены ребром.
Графом Г называется не пустое множество М и множество отношений на нем.
Г=(M,Q)
Лабораторная работа № 1.
Основные характеристики графа
Цель работы:
Изучить понятия вершины, ребра и дуги графа, цикл графа.
Рассмотреть понятие дерево.
Литература:
"Графы и их применение", Березина Л.Ю., М: Просвещение, 1979г.
"Теория графов. Алгоритмический подход", Кристофидес Н.
"Применение теории графов в программировании", Евстигнеев В.А. - М.: Наука, 1985г.
Порядок выполнения работы:
I Разработать схему алгоритмов основной программы и подпрограмм.
II Написать и отладить программу на языке Turbo Pascal.
Задание:
Задача Прима-Краскала.
Дана плоская страна и в ней n-городов. Нужно соединить все города телефонной связью так, чтобы общая длина телефонных линий была минимальной.
Другими словами, дан граф с n-вершинами; длины рёбер заданы матрицей { }, i,j=1,2,3, ,n. Найти дерево минимальной длины.
Краткие теоретические сведения:
Граф представляет собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек.
Ребро, ведущее из вершины в неё же, называется петлей.
Граф без кратных ребер и петель называется простым.
Цепью между вершинами u и v называется последовательность ребер, соединяющих u и v.
Связный граф - это граф, где существует цепь между любой парой вершин u и v; иногда такой граф называют односвязанным.
Циклом называется цепь из V в V.
Деревом называется граф без циклов.
Дерево с n -вершинами имеет n-1 ребер. Поэтому краткое описание поставленной задачи выглядит следующим образом: в цикле n-1 раз делай: Выбрать самое короткое ещё не выбранное ребро при условии, что оно не образует цикла с уже выбранными. Выбранные таким образом ребра образуют искомое дерево.
Кроме того, при проверки того, что новое ребро не образовывает цикла со старыми, используйте следующее: до построения дерена окрасим каждую вершину i в отличный от других цвет i. При выборе очередного ребра, скажем (i, j), где i и j имеют разные цвета, вершина j и все окрашенные в её цвет (т.е. ранее соединенные с ней) перекрашиваются в цвет i. Таким образом, выбор вершин разного цвета обеспечивает отсутствие циклов. После выбора n-1 ребер все вершины получают один цвет.
В заключении анализа алгоритма надо оценить требуемую память и требуемое число операций. С памятью здесь все ясно: в решении удобно хранить n-1 ребер ответа. Всего требуется память 0(n2), т.е. порядка ≈ , что учитывая реальные величины n, необременительно. Для нахождения текущего минимального ребра надо просмотреть 0( ) чисел и сделать это n-1 раз, так что временная сложность алгоритма 0( ). Это тоже реально.
Содержание отчета;
Составление алгоритмов.
Написание программы на языке Turbo Pascal.
Отладка программы.
Контрольные вопросы:
Что такое граф?
Какой граф называется простым?
Что называется цепью?
Что такое цикл?
Понятие дерева.