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

Дорогие студенты!

На этой странице будут появляться различные материалы и объявления, связанные с курсом «Дискретная математика», читаемого для студентов 1-го курса ОП Вычислительные социальные науки в 2022/2023 учебном году.

• Лекции и семинары: Сысоева Любовь Николаевна lsysoeva@hse.ru, telegram @lsysoeva
• Ассистент: Ластовецкий Дмитрий dalastovetsky@hse.ru, telegram @dalastovetskiy

Ведомость активности

Ведомость ДЗ

Формула итоговой оценки: 0,3 * Активность + 0,3 * Домашние задания + 0,4 * Экзамен

Контрольная

Итоговая контрольная состоится 16го декабря!
Большая просьба не опаздывать!!
Если все пойдет по плану, последние 30-50 минут занятий мы потратим на разбор задач из контрольной, чтобы у вас сразу было понимание, как вы написали и какие темы стоит повторить к экзамену. Оценка за экзамен будет выставляться как максимум из оценок за КР и за Экзамен.

Лекции

дата лекции	тема лекции	дополнительные материалы
16.09.2022	Понятие множества, конечные множества, задание множества перечислением элементов, задание множества условием, пустое множество, пересечение множеств, объединение множеств, декартово произведение множеств, парадокс брадобрея. Комбинаторика: правило суммы, правило произведения, факториал, число размещений с повторениями и без повторений, число сочетаний.	Комбинаторика (в частности задачки по темам с ответами) стр.1-26 Лекции по дискретной математике ФКН ВШЭ стр.44-63
23.09.2022	Дискретная вероятность = (кол-во положительных исходов)/(общее число исходов). Сочетания с повторениями (метод шариков и перегородок), типы предметов. Треугольник Паскаля (количество путей от вершины вниз), рекуррентная формула (нижний элемент = сумме двух верхних). Бином Ньютона, связь с треугольником Паскаля (коэффициенты в разложении (a+b)n это числа в n строке треугольника). Числа сочетаний в треугольнике Паскаля, формула Ckn = Ckn-1 + Ck-1n-1 и ее комбинаторный смысл. Сумма элементов n строки в треугольнике Паскаля равна 2n (через удвоение суммы предыдущей строки, через разложение (1+1)n и через все подмножества множества из n элементов). Полиномиальные коэффициенты (определение и формула).	Комбинаторика (в частности задачки по темам с ответами) стр.26-40 Лекции по дискретной математике ФКН ВШЭ стр.63-70
30.09.2022	Числа сочетаний в треугольнике Паскаля: возрастание элементов к середине строки и убывание после середины (Ckn < Ck+1n при k < (n-1)/2 и Ckn > Ck+1n при k > (n-1)/2), симметрия (Ckn = Cn-kn), оценка среднего элемента в строке через сумму и количество элементов в этой строке (Cn2n > 22n/(2n+1)). Сумма знакопеременных элементов n строки в треугольнике Паскаля равна нулю (через удвоение элементов предыдущей строки с противоположными знаками, через разложение (1-1)n). Формулы для 112, 113, 114 и связь со строками треугольника Паскаля (доказательство через разложение 11k = (10+1)k по биному Ньютона). Формула включений-исключений: через диаграммы Эйлера-Вена для 2 и 3 множеств, формулировка в общем случае. Принцип Дирихле (pigeonhole principle): если кроликов больше, чем клеток, то при рассадке кроликов по клеткам по крайней мере в одну клетку попадут по крайней мере два кролика.	Комбинаторика (в частности задачки по темам с ответами) стр.41-44 Лекции по дискретной математике ФКН ВШЭ стр.66
7.10.2022	Числа Фибоначчи: задача про кроликов, определение (F0 = 0, F1 = 1, Fn+1 = Fn + Fn-1), Fn равно сумме "диагонали" треугольника Паскаля (Fn = Cn-10 + Cn-21 + Cn-32 + ... + Cn-[n/2][n/2]-1 целая часть должна быть верхней), явная формула (Fn = 1/٧5((1+٧5)/2)^n - 1/٧5((1-٧5)/2)^n) и ее доказательство по индукции. Индукция: принцип математической индукции, база и переход их согласованность, индуктивное предположение, доказательство равенств, неравенств, разбор текстовой задачи (машина на краю пустыни). Примеры неверных доказательств по индукции (резиновый автобус, куча манки, одномастные лошади).	Лекции по дискретной математике ФКН ВШЭ стр.16-51 Примеры с решениями и без задач на индукцию
14.10.2022	Числа Фибоначчи (повторение). Линейные рекуррентные соотношения в разных задачах. Рекурсия (программирование, литература) и ее связь с рекуррентными соотношениями. Основная теорема о рекуррентных соотношениях (Master theorem): оценка сложности рекурсивных алгоритмов. Рекуррентные записи n! и геометрических прогрессий. Индукция: повторение, связь с рекуррентными соотношениями, пример вложенной индукции (количество разломов прямоугольной шоколадки).	Основная теорема о рекуррентных соотношениях Примеры с решениями и без задач на индукцию
21.10.2022	Числа Каталана (по заявкам): рекуррентная формула, количество правильных скобочных последовательностей, количество способов разбить n-угольник диагоналями на треугольники. Системы счисления: позиционные, примеры, n-ичные дроби, переводы между системами счислений целых чисел и дробных частей, погрешность в случае прерывания бесконечных дробей. Римская система счисления: способы записи чисел, сложность алгоритмов сложения и умножения чисел. Признаки делимости в n-ичной системе счисления: схожесть признаков делимости на n-1 и n+1 с признаками делимости на 9 и 11 для десятичной системы, схожесть признаков делимости на делители n с признаками делимости на 5 и 10 для десятичной системы. Троичная система: взвешивание путем уравновешивания весов с двумя чашами.	Статья про числа Каталана Книжка по системам счисления
01.11.2022	Простые числа: определение, основная теорема арифметики (любое число однозначно разлагается в произведение простых), бесконечное количество простых чисел (два доказательства 1. p1p2...pn+1 ; 2. (k+1)n << 2k при фиксированном n и растущем k), Постулат Бертрана (теорема Чебышева): для любого натурального n ⩾ 2 найдётся простое число p в интервале n < p < 2n. Остатки от деления и вычеты: сложение, вычитание, умножение, поиск обратного вычета. Запись вычетов через отрицательные числа для удобства вычислений. Примеры, когда обратного вычета не существует (элемент и модуль не взаимно просты). Алгоритм Евклида (с использованием остатка от деления по модулю): сам алгоритм и оценка числа итераций через числа Фибоначчи.	Вычеты (короткая базовая статья) Лекции по дискретной математике ФКН ВШЭ стр.143-156
11.11.2022	Идея кодирования с открытым ключом. Диофантовы уравнения: примеры, великая теорема Ферма, линейные Диофантовы уравнения с двумя неизвестными, критерий разрешимости. Расширенный алгоритм Евклида: решение линейных Диофантовых уравнений с двумя неизвестными. Сведение поиска обратного по умножению элемента по модулю к решению линейного Диофантова уравнения с двумя неизвестными. Единственность обратного по умножению элемента по модулю (если существует, то единственный). Малая теорема Ферма: формулировка, четыре доказательства (мультиномиальное разложение, индукция и бином Ньютона, раскраска бус, перемножение чисел специального вида), поиск обратного по умножению элемента через малую теорему Ферма в случае простого модуля.	Лекции по дискретной математике ФКН ВШЭ стр.154-163
15.11.2022	Идея проверки числа на простоту: 1) проверка делимости на простые до корня из числа; 2) проверка взаимной простоты с числами от 2 до n-1; 3) (тест Ферма) проверка справедливости малой теоремы Ферма для чисел от 2 до n-1 (и числа Кармайкла); 4) (тест Рабина) проверка справедливости малой теоремы Ферма плюс корней из 1. Китайская теорема об остатках: система сравнений по взаимнопростым модулям имеет единственное решение по произведению модулей. Доказательство и решения систем сравнений с помощью расширенного алгоритма Евклида.	Лекции по дискретной математике ФКН ВШЭ стр.161-165
18.11.2022	Китайская теорема об остатках: доказательство (индукция во числу сравнений), Следствие: независимость распределения остатков по взаимнопростым модулям. Функция Эйлера: определение и вычисление для простых чисел, степеней простых чисел, составных чисел. Теорема Эйлера: формулировка, малая теорема Ферма как частный случай, доказательство (аналогично 4 доказательству малой теоремы Ферма, через обратимые остатки и их перемножение). Алгоритм кодирования с открытым ключом RSA: определение, корректность кодирования и декодирования, устойчивость к атакам.	Лекции по дискретной математике ФКН ВШЭ стр.162-167 Лекции по криптографии (тут довольно хорошо объяснен алгоритм RSA и еще много что)
22.11.2022	Графы: определение (V,E), множество вершин, множество ребер, изолированная вершина, степень вершины, способы задания графов (матрица смежности, матрица инцидентности, список смежности). Формула 2|E|=Σ deg(vi). Маршрут, путь, простой путь, расстояние между вершинами (длина кратчайшего пути), диаметр графа (самое большое расстояние между вершинами). Цикл, простой цикл. Связный граф, компонента связности. Оценка: количество компонент связности ≥ |V|-|E|. Следствие: для поиска самого тяжелого камня среди n камней необходимо n-1 взвешивание.	Лекции по дискретной математике ФКН ВШЭ стр.95-118
25.11.2022	Деревья: (четыре определения и их эквивалентность) связный граф с V-1 ребром; минимальный связный граф; связный ациклический граф; граф, между любыми двумя вершинами которого существует единственный путь. Дополнительно: бинарное дерево поиска: поиск элемента, добавление элемента, удаление элемента, поиск следующего и предшествующего элементов. Существование у произвольного дерева по крайней мере двух листьев (два доказательства: через формулу 2|E|=Σ deg(vi) и через максимально удаленные вершины). Остовное дерево связного графа, возможность удаления из связного графа вершины вместе с ребрами без потери связности. Правильная раскраска: определение, примеры, критерий 2-раскрашиваемости графа (отсутствие циклов нечетной длины). Дополнительно: алгоритмы поиска в ширину (BFS) и глубину (DFS).	Лекции по дискретной математике ФКН ВШЭ стр.118-123 Т.Кормен и др. «Алгоритмы Построение и Анализ» стр 316-322, 607-663
02.12.2022	Жадные алгоритмы: алгоритмы, оптимизирующие некоторый параметр на каждом шаге, примеры (задача о рюкзаке в дискретном и непрерывном вариантах, задача о поиске минимального остовного дерева, задача о загруженности аудитории). Эйлеровы циклы и пути: цикл (путь) проходящий по каждому ребру графа ровно один раз, критерии наличия Эйлерова цикла (пути) в неориентированном и ориентированном графах. Гамильтоновы циклы и пути: цикл (путь) проходящий через каждую вершину графа ровно один раз, отсутствие критерия, NP-полнота задачи о поиске Гамильтонова цикла в графе, теорема Оре. Чуть-чуть логики: формализация метода доказательства с помощью правила контрапозиции и метода доказательства от противного.	Лекции по дискретной математике ФКН ВШЭ стр.132-135 Т.Кормен и др. «Алгоритмы Построение и Анализ» стр 442-482, 642, 1086, 1101-1103
09.12.2022	Двудольные графы, паросочетания, теорема Холла (о свадьбах): формулировка, примеры. Сеть: ориентированный граф с истоком и стоком, с заданными пропускными способностями на ребрах. Поток: неотрицательная функция, заданная на ребрах сети, на каждом ребре не превосходящая пропускной способности ребра и суммарно равная нулю в каждой вершине сети, кроме стока и истока. Разрез: разбиение вершин сети на два множества S и T, содержащих соответственно исток и сток. Пропускная способность разреза: сумма пропускных способностей ребер, ведущих из множества вершин S в множество вершин T. Теорема Форда-Фалкерсона: величина максимального потока равна пропускной способности минимального разреза. Алгоритм нахождения максимального потока в сети: начинаем с нулевого потока, ищем увеличивающий путь (лучше минимальной длины), увеличиваем поток, ищем следующий увеличивающий путь, увеличиваем поток и т.д.

Семинары

Комбинаторика-1

Комбинаторика-2

Комбинаторика-3

Числа Фибоначчи, Индукция

Числа Фибоначчи-2, Индукция-2

Системы счисления

Делимость и Вычеты

Расширенный алгоритм Евклида, малая теорема Ферма

Малая теорема Ферма, Китайская теорема об остатках

Теорема Эйлера

Графы-1

Деревья, правильные раскраски

Эйлеровы и Гамильтоновы циклы и пути

Потоки в сетях

Повторение

Домашние задания

В ДЗ-8 появилась бонусная задача на бинарные деревья поиска. Ссылку на книгу по теме можно найти в допматериалах к последней лекции.
Книга «Алгоритмы. Построение и Анализ.» Т.Кормена и др. на мой взгляд является отличным источником знаний для начинающего (и не только) программиста -- в ней рассмотрено большое количество основных понятий и определений, для каждого алгоритма приведен псевдокод (иногда не один) и оценка сложности. Этой книгой можно пользоваться как справочником: читать 2-3 страницы по интересующей теме и временно откладывать.

Правила сдачи ДЗ: решения задач из домашнего задания оформляются письменно, первый лист работы подписывается, только ответы не проверяются, должно присутствовать полное рассуждение, затем текст сканируется, файл называется в соответствии с ФИО студента (например, SysoevaLN.pdf) и отправляется на проверку (ссылку на загрузку см. в таблице ниже).

дедлайн	Домашнее задание	Ссылка на загрузку файла
23.09.2022	Домашнее задание №1	Файл сюда
30.09.2022	Домашнее задание №2	Файл сюда
7.10.2022	Домашнее задание №3	Файл сюда
21.10.2022	Домашнее задание №4	Файл сюда
4.11.2022	Домашнее задание №5	Файл сюда
12.11.2022	Домашнее задание №6	Файл сюда
22.11.2022	Домашнее задание №7	Файл сюда
27.11.2022	Домашнее задание №8	Файл сюда
4.12.2022	Домашнее задание №9	Файл сюда
18.12.2022	Домашнее задание №10	Файл сюда