В этом материале представлены ссылки на лекции и варианты практических занятий для изучения дисциплины "Дискретная математика".
Вторая часть материалов по дисциплине "Дискретная математика" расположена по ссылке:
1. Теория множеств. Бинарные отношения. Функции.
1.1. Тема «Основные понятия теории множеств. Операции над множествами. Законы теории множеств».
Обучающийся должен
· знать: основные понятия теории множеств (множество, способы задания множеств, конечное множество, бесконечное множество, пустое множество, универсальное множество, принадлежность множеству, непринадлежность множеству, подмножество, булеан, множество натуральных чисел, множество целых чисел, множество рациональных чисел, множество действительных чисел, множество комплексных чисел, счетное множество, континуальное множество), формулу количества подмножеств конечного множества, перечисление элементов (список элементов), характеристическое свойство (предикат), порождающую процедуру, понятия пересечения, объединения, разности, симметрической разности, дополнения, приоритет выполнения операций, законы теории множеств (закон идемпотентности, закон коммутативности, закон ассоциативности, закон дистрибутивности, закон двойного дополнения, закон де Моргана и др.), диаграмму Эйлера — Венна;
· уметь: определять соотношения между элементом и множеством, задавать множества списком, характеристическим предикатом и порождающей процедурой, выполнять операции над множествами, упрощать формулы, описывающие множества, изображать диаграмму Эйлера — Венна, применять теоретико-множественные диаграммы.
Лекционный материал по теме:
1.2. Тема «Метод математической индукции».
Обучающийся должен
· знать: формулировку метода математической индукции, некоторые разновидности (модификации) метода математической индукции, последовательность доказательства с помощью метода математической индукции, в чём смысл базиса индукции; важность проведения индуктивного перехода;
· уметь: доказывать утверждения с помощью метода математической индукции, доказывать неравенства с помощью метода математической индукции.
Лекционный материал по теме:
1.3. Тема «Декартово произведение множеств. Бинарные отношения».
Обучающийся должен
· знать: понятия k-арной упорядоченной последовательности, декартового (прямого) произведения произвольного числа множеств, декартова квадрата, о невыполнении свойства коммутативности декартова произведения, понятия k-арного (k-местного) отношения, бинарного отношения, способы задания бинарных отношений, понятие специального бинарного отношения, тождественного бинарного отношения, полного бинарного отношения, свойства бинарных отношений (рефлексивность, симметричность, транзитивность), понятие замыкания бинарного отношения, отношения эквивалентности, примеры отношений эквивалентности, понятие разбиения множества, понятие класса эквивалентности, теорему о разбиении множества на классы, понятия отношения частичного порядка и линейного порядка, способы построения диаграммы Хассе, понятие обратного бинарного отношения и композиции двух бинарных отношений;
· уметь: определить декартово произведение для произвольного числа множеств, изобразить график декартового произведения двух множеств, показать, что для декартова произведения не выполняется свойство коммутативности, привести примеры бинарных отношений, записать различными способами бинарное отношение, определить для бинарного отношения область определений и область значений, исследовать бинарное отношение на заданные свойства (рефлексивность, симметричность, транзитивность), получить замыкание относительно заданного свойства для бинарного отношения, привести примеры отношения эквивалентности, выделить классы эквивалентности, привести примеры отношения частичного порядка, изобразить диаграмму Хассе, привести примеры отношения линейного порядка, записать обратного бинарное отношение к заданному, определить композицию для двух заданных бинарных отношений.
Лекционный материал по теме:
1.4. Тема «Теория функций».
Обучающийся должен
· знать: определение функции, примеры функций, способы записи функций, способы задания функций, понятие области определения функции, области значений функции, понятие множества значений функции, как изобразить диаграмму Эйлера-Венна для функции, свойства функций (инъекция, сюръекция и биекция), понятие обратной функции, понятие композиции двух функций;
· уметь: задавать функции различными способами (перечисление элементов, формулой, графиком), определять основные характеристики функций (область определения, область значений, множество значений), изобразить диаграмму Эйлера-Венна для функций, определять свойства функций (инъекция, сюръекция и биекция), получать и записывать обратную функцию, определять композицию двух функций.
Лекционный материал по теме:
В материале приведены типовые примеры тех тестовых заданий, которые имеются в базе данных теста по разделу "Теория множеств. Бинарные отношения. Функции":
2. Основы теории графов.
2.1. Тема «Неориентированный граф».
Обучающийся должен
· знать: определение неориентированного графа, понятия множества вершин и множества неориентированных рёбер, способы записи неориентированных графов, что такое (n, m)-граф, способы изображения вершин и неориентированных ребер, какие элементы называются соединенными или связанными, понятие размеченного графа; понятие инцидентности для вершин (неориентированных рёбер), определение степени вершины, какие вершины называются изолированными или концевыми, понятие смежности для вершин (неориентированных рёбер), формулировку теоремы о сумме степеней вершин (n, m)-графа, следствие о чётности числа вершин нечётной степени, понятия подграфа, надграфа, какой подграф называется остовным; способы задания неориентированных графов (матрица смежности, список смежности, списочная структура, матрица инцидентности, список инцидентности, матрица Кирхгофа, матрица расстояний); понятия пути (маршрута) длины k, простого пути, цепи, простой цепи, цикла, простого цикла, понятия связного графа, формулировку теоремы о существовании простого пути, следствие о существовании простого пути между любыми двумя вершинами, понятия компоненты связности, разрезающего множества рёбер, разреза, моста; понятия тривиального, пустого неориентированного графа, графа с петлёю, мультиграфа, псевдографа, полного графа, способ обозначения полного графа, двудольного графа, способ обозначения двудольного графа; понятия расстояния между вершинами неориентированного графа, перечень аксиом метрики, понятие эксцентриситета вершины, свойства матрицы расстояний, понятия радиуса, диаметра графа, какая вершина называется центральной, периферийной; понятие эйлерова цикла, формулировку теоремы о существовании эйлерова цикла, понятия эйлерова пути, собственного эйлерова пути, формулировку теоремы о существовании собственного эйлерова пути.
· уметь: представлять неориентированный граф различными способами, определять инцидентности, смежности вершин и рёбер неориентированного графа, определять степени вершин графа, находить все остовные подграфы граф; задавать неориентированный граф различными способами (матрица смежности, список смежности, списочная структура, матрица инцидентности, список инцидентности, матрица Кирхгофа, матрица расстояний); записывать путь, цепь, цикл для неориентированного графа, определять, являются ли путь, цепь, цикл для неориентированного графа простыми, определять число компонент связности графа, находить разрезающее множество графа, определять, имеется ли разрез или мост, вид графа; определять расстояния в графе, эксцентриситет, радиус и диаметр графа, определять, является ли вершина графа центральной, периферийной; определять наличие или отсутствие у неориентированного графа эйлерова цикла или собственного эйлерова пути.
Лекции по ссылкам:
Теоретико-множественное представление графа - https://zen.yandex.ru/media/id/603a418d1684900aa2499416/62735a02d5f97c19587d7738
Основные характеристики графа - https://zen.yandex.ru/media/id/603a418d1684900aa2499416/627364ffbfba4345e08f3a2a
Подграфы неориентированного графа - https://zen.yandex.ru/media/id/603a418d1684900aa2499416/627370b9a4797a5ee6ad270f
Связность в неориентированном графе - https://zen.yandex.ru/media/id/603a418d1684900aa2499416/6273d341fb19593ccbfd7165
Матричное представление неориентированных графов - https://zen.yandex.ru/media/id/603a418d1684900aa2499416/627cafcf12a7ec034e94e3a4
Полный и двудольный граф в WolframAlpha -
https://zen.yandex.ru/media/id/603a418d1684900aa2499416/63aedf59f1a4fe4f467df779
Расстояние в неориентированном графе - https://zen.yandex.ru/media/id/603a418d1684900aa2499416/627cb928b24f8b72b9196886
Циклы и пути Эйлера в неориентированном графе - https://zen.yandex.ru/media/id/603a418d1684900aa2499416/63b969729bd13619e2d43fb2
Графы и деревья в WolframAlpha - https://dzen.ru/a/Y997BVmQpD4_kjWd?share_to=link
2.2. Тема «Ориентированный граф»
Обучающийся должен:
· знать: определение ориентированного графа; как обозначается ориентированный граф; что представляет собой множество вершин и множество ориентированных рёбер; как определяется порядок ориентированного графа; какие вершины называются соединенными (связанными); каким образом наглядно изобразить ориентированный граф; какие имеются требования к элементам изображения орграфа; определение размеченного ориентированного графа; сколько имеется различных орграфов, если число вершин n; какая вершина орграфа называется начальной; какая вершина орграфа называется конечной; определение вершин, инцидентных ориентированному ребру; определение степени входа (выхода) произвольной вершины ориентированного графа; определение степени вершины орграфа; какая вершина называется источником (истоком); какая вершина называется стоком; какая вершина называется изолированной вершиной; как определить степень вершины по полустепеням исхода и захода в орграфе; какие вершины ориентированного графа называются смежными; какие ориентированные рёбра называются смежными; как обозначается множество вершин орграфа, смежных с некоторой вершиной; определение ориентированного пути (маршрута) длины k ориентированного графа; какой путь (маршрут) в орграфе называется простым; определение цепи (простой цепи) ориентированного графа; определение цикла (простого цикла) в орграфе; какой граф называется соотнесённым; определение связного орграфа; определение сильно связного орграфа; определение матрицы смежности; какими свойствами обладает матрица смежности ориентированного графа; какое графовое представление называется списком вершин (списком смежности); определение матрицы инцидентности; какими свойствами обладает матрица инцидентности ориентированного графа; какое графовое представление называется списком рёбер (списком инцидентности); определение тривиального орграфа; определение пустого орграфа; определение ориентированного мультиграфа; определение взвешенного орграфа; определение ориентированного двудольного графа; определение полного ориентированного двудольного графа; определение ориентированного эйлерова цикла; формулировку теоремы об орграфах, имеющих эйлеров цикл;
· уметь: записать множество вершин и множество ориентированных рёбер орграфа; определять порядок ориентированного графа; наглядно изображать ориентированный граф; наглядно изображать размеченный орграф; определять, сколько имеется различных орграфов, если число вершин n; для произвольного орграфа находить начальную вершину; для произвольного орграфа находить конечную вершину; для произвольного орграфа находить вершины, инцидентные ориентированному ребру; определять степени входа (выхода) произвольной вершины ориентированного графа; определять степени каждой вершины орграфа; находить источники (истоки) орграфа; находить стоки орграфа; определять, имеются ли у орграфа изолированные вершины; рассчитывать степень вершины по полустепеням исхода и захода в орграфе; находить смежные вершины в орграфе; находить смежные ориентированные рёбра в орграфе; записать множество вершин орграфа, смежных с некоторой вершиной; определять и записывать ориентированные пути (маршруты) длины k ориентированного графа; определять и записывать простые пути (маршруты) в орграфе; определять и записывать цепи (простые цепи) ориентированного графа; определять и записывать циклы (простые циклы) в орграфе; изображать соотнесённый граф для произвольного орграфа; определять, является ли орграф связным; определять, является ли орграф сильно связным; записывать матрицы смежности произвольного ориентированного графа; записывать списки вершин (списки смежности) произвольного ориентированного графа; записывать матрицы инцидентности произвольного ориентированного графа; записывать списки рёбер (списки инцидентности) произвольного ориентированного графа; определять тип орграфа; определять, имеет ли указанный ориентированный граф ориентированный эйлеров цикл.
Лекции по ссылкам:
Теоретико-множественное представление ориентированного графа - https://zen.yandex.ru/media/id/603a418d1684900aa2499416/628e37b10a455003f94a13db
Основные характеристики ориентированного графа - https://zen.yandex.ru/media/id/603a418d1684900aa2499416/628e3c028a25537430ec3711
Связность в ориентированном графе - https://zen.yandex.ru/media/id/603a418d1684900aa2499416/628f2e855f085456c7f72cd8
Матричное представление ориентированных графов - https://zen.yandex.ru/media/id/603a418d1684900aa2499416/628f3aa8b6c7c75984e0e8f6
Циклы Эйлера в ориентированном графе - https://dzen.ru/a/Y7oJlzubSXxdM119?share_to=link
Графы и деревья в WolframAlpha - https://dzen.ru/a/Y997BVmQpD4_kjWd?share_to=link
В комментариях под материалом можете предложить свои темы, относящиеся к дискретной математике, теоретические или практические вопросы которых вам хотелось бы изучить.
