Лекториум. Курсы повышения квалификации

Приглашаем на бесплатный онлайн-курс Санкт-Петербургского государственного электротехнического университета «ЛЭТИ» «Дискретная математика». В этом курсе вы изучите несколько сюжетов дискретной математики и узнаете основные определения и свойства объектов теории чисел, комбинаторики, булевых функций, бинарных отношений на множествах. Кроме этого, вы научитесь осуществлять вычисления и преобразования, связанные с этими объектами, решать конструктивно-исследовательские задачи и пользоваться основными методами применения алгоритмов. Программа курса: Раздел 1. Теория чисел • Эпоха античности • Деление с остатком • Делимость • Наибольший общий делитель и наименьшее общее кратное • Алгоритм Евклида • Обобщенный алгоритм Евклида • Второй способ нахождения линейного представления НОД • Свойства НОД • Линейные диофантовы уравнения с двумя неизвестными • Простые числа • Решето Эратосфена • Основная теорема арифметики • Степень вхождения данного простого числа в разложение факториала • Теорема Евклида о бесконечности множества простых чисел • Системы счисления • Сравнение по модулю • Модульная арифметика • Решение уравнений в кольце остатков по данному модулю • Китайская теорема об остатках • Непрерывные дроби и перевод рационального числа в конечную дробь Раздел 2. Комбинаторика • Задачи комбинаторики • Правило произведения • Правило сложения • Перестановки • Размещения с повторениями • Размещения без повторений • Сочетания • Переход к дополнению • Использование взаимно однозначного соответствия множеств • Принцип включений-исключений • Бином Ньютона • Свойства биномиальных коэффициентов • Шары и перегородки • Треугольник Паскаля Раздел 3. Булевы функции • Определение булевой функции и примеры булевых функций • Приоритет булевых функций • Некоторые равенства о булевых функциях двух переменных • Пример построения таблицы истинности для булевой функции трех переменных • Совершенные дизъюнктивная (СДНФ) и конъюнктивная (СКНФ) нормальные формы • Композиция функции от трех переменных, дизъюнкции и конъюнкции • Многочлен Жегалкина • Двойственная функция • Нахождение таблицы значений функции, двойственной к данной булевой функции • Исследование булевой функции на принадлежность к основным классам замкнутости • Применение теоремы Поста Раздел 4. Множества и отношения • Представление отношения на множестве в виде матрицы и графа • Свойства отношений и проявление этих свойств на свойствах матрицы и графа • Примеры конструктивно-исследовательских задач про множества и отношения Подробнее: https://www.lektorium.tv/Z45.