Учебник Дискретная математика для начинающих

Программа курса

1. 1 Множества и операции

   1. Множества: язык, на котором говорит вся математика

      Что такое множество, элементы, пустое множество, способы задания и подмножества — с живой проверкой на Python через set.

   2. Операции над множествами и диаграммы Венна

      Объединение, пересечение, разность, симметрическая разность и дополнение множеств; диаграммы Венна и проверка операций на Python.

   3. Законы алгебры множеств, мощность и декартово произведение

      Законы де Моргана, дистрибутивность, булеан и его размер 2^n, декартово произведение и его мощность — с компьютерной проверкой.

2. 2 Отношения и функции

   1. Бинарные отношения и их свойства

      Что такое бинарное отношение, как его задают; рефлексивность, симметричность, антисимметричность и транзитивность — с проверкой на Python.

   2. Отношения эквивалентности и порядка

      Отношение эквивалентности и классы эквивалентности, разбиение множества; частичный и линейный порядок, диаграммы Хассе — с примерами на Python.

   3. Функции: инъекция, сюръекция, биекция

      Функция как особое отношение; область определения и значений, образ; инъекция, сюръекция и биекция; обратная функция — с проверкой перебором на Python.

3. 3 Математическая логика

   1. Высказывания, логические операции и таблицы истинности

      Высказывания и логические связки: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность; таблицы истинности — с построением на Python.

   2. Тавтологии, противоречия и логические эквивалентности

      Тавтология и противоречие, логические законы (де Морган, дистрибутивность, контрапозиция), проверка равносильности формул перебором на Python.

   3. Предикаты, кванторы и методы доказательства

      Предикаты и кванторы «для всех» и «существует», отрицание кванторов; методы доказательства: прямое, от противного, контрапозиция — с примерами.

4. 4 Математическая индукция и рекурсия

   1. Принцип математической индукции

      Метод математической индукции: база, предположение и шаг; почему он работает; доказательство формул суммы — с компьютерной проверкой на Python.

   2. Рекуррентные соотношения и их решение

      Рекуррентные соотношения, числа Фибоначчи, метод характеристического уравнения для линейных рекуррент — с проверкой замкнутой формулы на Python.

   3. Рекурсия: от математики к коду

      Рекурсивные определения и рекурсия в программировании, связь с индукцией, классические примеры: факториал, Ханойские башни — запускаемо на Python.

5. 5 Комбинаторика

   1. Правила суммы и произведения

      Два базовых правила комбинаторики — сумма (или) и произведение (и); как считать число вариантов в составных выборах — с перебором на Python.

   2. Перестановки, размещения и сочетания

      Перестановки, размещения и сочетания: формулы, когда порядок важен, а когда нет; разница между ними — с перебором и проверкой на Python.

   3. Бином Ньютона и треугольник Паскаля

      Биномиальные коэффициенты, формула бинома Ньютона, треугольник Паскаля и его свойства, связь с сочетаниями — с построением на Python.

   4. Принцип включения-исключения и принцип Дирихле

      Формула включения-исключения для подсчёта объединений и принцип Дирихле (голубей и ящиков) — два мощных приёма комбинаторики с проверкой на Python.

6. 6 Теория графов

   1. Графы: основные понятия, степени и матрицы

      Что такое граф, вершины и рёбра, виды графов; степень вершины и лемма о рукопожатиях; матрица смежности и список смежности — с кодом на Python.

   2. Обходы графа, связность и деревья

      Обход в ширину (BFS) и в глубину (DFS), компоненты связности, деревья и их свойства (n−1 рёбер) — с работающими алгоритмами на Python.

   3. Эйлеровы и гамильтоновы циклы, раскраска графов

      Эйлеров путь и критерий чётности степеней (мосты Кёнигсберга), гамильтонов цикл, раскраска графа и хроматическое число — с проверками на Python.

7. 7 Булева алгебра

   1. Булевы функции, СДНФ и СКНФ

      Булевы функции и таблицы истинности, число булевых функций; построение совершенной ДНФ и КНФ по таблице — с генерацией формулы на Python.

   2. Минимизация булевых функций и логические схемы

      Зачем упрощать булевы функции, законы поглощения и склеивания, идея карт Карно, превращение формулы в логическую схему из вентилей — с проверкой на Python.

   3. Полные системы булевых функций

      Функциональная полнота, базис {И, ИЛИ, НЕ}, штрих Шеффера (НЕ-И) как единственная операция, теорема Поста — с проверкой выразимости на Python.

8. 8 Элементы теории чисел

   1. Делимость, простые числа, НОД и алгоритм Евклида

      Делимость и её свойства, простые числа и решето Эратосфена, НОД и НОК, алгоритм Евклида и расширенный Евклид — с реализациями на Python.

   2. Сравнения по модулю и модулярная арифметика

      Сравнения по модулю, классы вычетов, свойства сложения и умножения по модулю, арифметика «часов» — с проверкой свойств на Python.

   3. Малая теорема Ферма и её применения

      Малая теорема Ферма, быстрое возведение в степень по модулю, нахождение обратного элемента и идея теста на простоту — с живыми вычислениями на Python.