В этом материале представлены ссылки лекций и практических занятий для изучения дисциплины "Дискретная математика".
Первая часть материалов по дисциплине "Дискретная математика" расположена по ссылке:
1. Алгоритмическое перечисление некоторых видов комбинаторных объектов.
1.1. Тема «Комбинаторные объекты».
Обучающийся должен
· знать: формулировку понятия комбинаторного объекта, определение комбинаторного числа, формулировку комбинаторного правила умножения, формулировку комбинаторного правила сложения, методику использования комбинаторных принципов (правил);
· уметь: использовать комбинаторные правила умножения и сложения для решения практических задач по расчёту комбинаторного числа произвольного комбинаторного объекта.
Лекция по ссылке: https://zen.yandex.ru/media/id/603a418d1684900aa2499416/6394864914723754a36a5d5c.
1.2. Тема «Генерирование комбинаторных объектов».
Обучающийся должен
· знать: сущность порядка выбора, сущность повторений, понятие выборки r элементов, понятия комбинаторного числа размещений без повторений, комбинаторного числа сочетаний без повторений, комбинаторного числа размещений с повторениями, комбинаторного числа сочетаний с повторениями, определения перестановки, перестановки с повторениями, свойства сочетаний без повторений, бином Ньютона, полиномиальную формулу, способы задания треугольника Паскаля;
· уметь: использовать основные схемы для получения комбинаторных чисел при решении различных практических задач, определять, важен ли порядок выбора элементов, определять, разрешено ли использовать элементы повторно, свойства сочетаний без повторений для решения практических задач.
Лекции по ссылкам:
Генерирование комбинаторных объектов (часть 1) - https://zen.yandex.ru/media/id/603a418d1684900aa2499416/63b56f3b7a5b092ebfa9e9d2.
Генерирование комбинаторных объектов (часть 2) - https://zen.yandex.ru/media/id/603a418d1684900aa2499416/63b573797a5b092ebfade5f7.
Генерирование комбинаторных объектов (часть 3) - https://zen.yandex.ru/media/id/603a418d1684900aa2499416/63b7847723064044f3329a5d.
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
3. Элементы теории алгебры подстановок.
3.1. Тема «Элементы теории алгебры подстановок».
Обучающийся должен
· знать: определение перестановки из n элементов, число всех перестановок из n элементов, определение подстановки, матричный способ записи подстановки, канонический вид записи подстановки, формулировку теоремы о числе подстановок, понятие циклического разложения подстановки, формулировку теоремы о разложении подстановки в произведение непересекающихся циклов, понятие транспозиции, формулировку теоремы о представлении подстановки произведением транспозиций, как задаётся операция умножения подстановок, свойства операции умножения подстановок, символ обозначения симметрической группой подстановок n-ой степени, понятие порядка подстановки, формулировку теоремы о порядке подстановки циклической подгруппы, понятие инверсии, понятия чётной и нечётной подстановок, формулировку о числе чётных подстановка, аксиомы знакопеременной группы;
· уметь: задавать подстановки через биективное отображение, матрицей, произведение циклов и произведение транспозиций, осуществлять умножение подстановок, определять обратную подстановку для заданной, рассчитывать число k-циклов в симметрической группе подстановок n-ой степени, определять порядок подстановки циклической подгруппы, определять число инверсий, выяснять, является ли заданная подстановка чётной (нечётной).
Лекции по ссылкам:
Элементы теории алгебры подстановок (часть 1) - https://zen.yandex.ru/media/id/603a418d1684900aa2499416/6393d7b71b4dc972389fdd19
Элементы теории алгебры подстановок (часть 2) - https://zen.yandex.ru/media/id/603a418d1684900aa2499416/6393fde192a8ca050a7e585d
Элементы теории алгебры подстановок (часть 3) - https://zen.yandex.ru/media/id/603a418d1684900aa2499416/639412cb5a4721646f639b2e
4. Основы алгебры вычетов.
4.1. Тема «Основы алгебры вычетов».
Обучающийся должен
· знать: понятие сравнимых целых чисел по модулю, способы записи сравнимых целых чисел по модулю, свойства сравнимости по модулю, арифметические действия над сравнимыми целыми числами по модулю, примеры признаков делимости, понятие класса вычетов по модулю, способы обозначения класса вычетов по модулю, понятие полной системы вычетов, способы обозначения полной системы вычетов, способы задания операций над вычетами;
· уметь: определять, являются ли два целых числа сравнимыми по определенному модулю, применять свойства сравнимости, использовать признаки делимости, разбивать множество целых чисел на непересекающиеся классы, определять операции над вычетами.
Лекции по ссылкам:
Основы алгебры вычетов (часть 1) –
https://zen.yandex.ru/media/id/603a418d1684900aa2499416/638b1ee3563b8a07cb770bf9
Основы алгебры вычетов (часть 2) - https://zen.yandex.ru/media/id/603a418d1684900aa2499416/638bef42f93de3331397fd2f
Видеолекция:
Решение задач по алгебре вычетов (часть 1) – https://zen.yandex.ru/media/id/603a418d1684900aa2499416/638bfca99158172953ea3b45
Решение задач по алгебре вычетов (часть 2) - https://zen.yandex.ru/media/id/603a418d1684900aa2499416/63a1a08fc60419562cda25c2
В комментариях под материалом можете предложить свои темы, относящиеся к дискретной математике, теоретические или практические вопросы которых вам хотелось бы изучить.
Просто красивая картинка)
