Дискретная математика

Лекции по Дискретной математике Вводная лекция Дискретная математика Предупреждение!!! Всё, что говорит преподаватель при показе презентации, должно быть законспектировано, поскольку обязательно встретится в контрольных материалах Структура предмета Дискретная математика Математические основы Теория множеств Комбинаторика Логические основы Теория отношений и функций Переключательные функции и схемы Нормальные формы представления функций Конструктивные основы Теория графов и сетей Теория конечных автоматов Структура дисциплины n Лекции: 18 часов (9 пар) n Практические занятия: 24 часа (12 пар) n Домашние расчётные работы: 3 n Аудиторные контрольные работы: 3 nТест:10 nДифференцированный зачёт: 1 Темы для самостоятельного изучения n Раздел 1. Теория множеств и отношений Доказательство свойств операций над множествами; виды (инъекция, сюръекция, биекция), суперпозиции и композиции соответствий; функциональное соответствие; комбинаторные операции (перестановки, сочетания, размещения) на конечных множествах; морфизмы. n Раздел 2. Теория графов Изоморфизм графов; алгоритмы на графах: поиска (в глубину, в ширину), отыскания эйлеровой цепи (цикла), построение остова (жадный алгоритм), поиск кратчайшего пути, определения максимального паросочетания; сети. n Раздел 3. Переключательные функции Замыкания логической алгебры; минимизация формулы логической функции в классах ДНФ, КНФ; построение полинома Жегалкина для логической функции. Рекомендуемая литература: n https://do.rusoil.net/course/view.php?id=803. n Шевелев Ю.П. Дискретная математика. n Кузнецов О.П. Дискретная математика для инженера. n Иванов Б.Н. Дискретная математика. Алгоритмы и программы. n Новиков Ф.А. Дискретная математика для программистов. Используемые обозначения - квантор всеобщности («для каждого»)  - квантор существования («существует»)  - квантор единственности («единственная»)  -знак принадлежности  - знак непринадлежности  - конкретный выбор («и»)  - альтернативный выбор («или»)  - следственность («если … то …» или «следует»)  - равносильность(«…тогда и только тогда, когда…») Лекции по Дискретной математике Лекция 1 Теория множеств Обозначения множеств и элементов A t1 t3 t2 t4 t5 Множество треугольников Т={t1, t2, t3, t4, t5} Абстрактное множество А |T|=5 (конечное множество) … -2 -1 R 0,8 1 2 Множество действительных чисел R=(-; +) (бесконечное множество) U … U-универсальное множество (универсум) Множество, не содержащее элементов, называется пустым и обозначается . Способы задания множеств n Диаграмма Эйлера-Венна U B A n Характеристический предикат А={х| P(x)} D={nZ| -4