Дискретная Математика: различия между версиями
(→Лекции) |
|||
(не показано 86 промежуточных версий этого же участника) | |||
Строка 14: | Строка 14: | ||
0,3 * Активность + 0,3 * Домашние задания + 0,4 * Экзамен | 0,3 * Активность + 0,3 * Домашние задания + 0,4 * Экзамен | ||
− | == | + | == Контрольная == |
− | + | '''Итоговая контрольная состоится 16го декабря!'''<br> | |
− | + | Большая просьба не опаздывать!!<br> | |
− | + | Если все пойдет по плану, последние 30-50 минут занятий мы потратим на разбор задач из контрольной, чтобы у вас сразу было понимание, как вы написали и какие темы стоит повторить к экзамену. | |
− | + | Оценка за экзамен будет выставляться как максимум из оценок за КР и за Экзамен. | |
− | |||
− | |||
− | |||
== Лекции == | == Лекции == | ||
Строка 32: | Строка 29: | ||
|- | |- | ||
|16.09.2022 | |16.09.2022 | ||
− | |Понятие множества, конечные множества, задание множества перечислением элементов, задание множества условием, пустое множество, пересечение множеств, объединение множеств, декартово произведение множеств, парадокс брадобрея. Комбинаторика: правило суммы, правило произведения, факториал, число размещений с повторениями и без повторений, число сочетаний. | + | |Понятие множества, конечные множества, задание множества перечислением элементов, задание множества условием, пустое множество, пересечение множеств, объединение множеств, декартово произведение множеств, парадокс брадобрея.<br> |
− | |[https://mathus.ru/math/kombinatorika.pdf Комбинаторика (в частности задачки по темам с ответами)] | + | Комбинаторика: правило суммы, правило произведения, факториал, число размещений с повторениями и без повторений, число сочетаний. |
− | [https://publications.hse.ru/mirror/pubs/share/direct/393719078.pdf Лекции по дискретной математике ФКН ВШЭ] | + | |[https://mathus.ru/math/kombinatorika.pdf Комбинаторика (в частности задачки по темам с ответами)] стр.1-26<br> |
+ | |||
+ | [https://publications.hse.ru/mirror/pubs/share/direct/393719078.pdf Лекции по дискретной математике ФКН ВШЭ] стр.44-63 | ||
|- | |- | ||
|23.09.2022 | |23.09.2022 | ||
− | |Дискретная вероятность = (кол-во положительных исходов)/(общее число исходов). | + | |Дискретная вероятность = (кол-во положительных исходов)/(общее число исходов).<br> |
− | Сочетания с повторениями (метод шариков и перегородок), типы предметов. | + | |
− | Треугольник Паскаля (количество путей от вершины вниз), рекуррентная формула (нижний элемент = сумме двух верхних). | + | Сочетания с повторениями (метод шариков и перегородок), типы предметов.<br> |
− | Бином Ньютона, связь с треугольником Паскаля (коэффициенты в разложении (a+b)<sup>n</sup> это числа в n строке треугольника). | + | |
− | Числа сочетаний в треугольнике Паскаля, формула C<sup>k</sup><sub>n</sub> = C<sup>k</sup><sub>n-1</sub> + C<sup>k-1</sup><sub>n-1</sub> и ее комбинаторный смысл. | + | Треугольник Паскаля (количество путей от вершины вниз), рекуррентная формула (нижний элемент = сумме двух верхних).<br> |
− | Сумма элементов n строки в треугольнике Паскаля равна 2<sup>n</sup> (через удвоение суммы предыдущей строки, через разложение (1+1)<sup>n</sup> и через все подмножества множества из n элементов). | + | |
+ | Бином Ньютона, связь с треугольником Паскаля (коэффициенты в разложении (a+b)<sup>n</sup> это числа в n строке треугольника).<br> | ||
+ | |||
+ | Числа сочетаний в треугольнике Паскаля, формула C<sup>k</sup><sub>n</sub> = C<sup>k</sup><sub>n-1</sub> + C<sup>k-1</sup><sub>n-1</sub> и ее комбинаторный смысл.<br> | ||
+ | |||
+ | Сумма элементов n строки в треугольнике Паскаля равна 2<sup>n</sup> (через удвоение суммы предыдущей строки, через разложение (1+1)<sup>n</sup> и через все подмножества множества из n элементов).<br> | ||
+ | |||
Полиномиальные коэффициенты (определение и формула). | Полиномиальные коэффициенты (определение и формула). | ||
− | | | + | ||[https://mathus.ru/math/kombinatorika.pdf Комбинаторика (в частности задачки по темам с ответами)] стр.26-40<br> |
+ | |||
+ | [https://publications.hse.ru/mirror/pubs/share/direct/393719078.pdf Лекции по дискретной математике ФКН ВШЭ] стр.63-70 | ||
+ | |||
|- | |- | ||
|30.09.2022 | |30.09.2022 | ||
− | |Числа сочетаний в треугольнике Паскаля: возрастание элементов к середине строки и убывание после середины (C<sup>k</sup><sub>n</sub> < C<sup>k+1</sup><sub>n</sub> при k < (n-1)/2 и C<sup>k</sup><sub>n</sub> > C<sup>k+1</sup><sub>n</sub> при k > (n-1)/2), симметрия (C<sup>k</sup><sub>n</sub> = C<sup>n-k</sup><sub>n</sub>), оценка среднего элемента в строке через сумму и количество элементов в этой строке (C<sup>n</sup><sub>2n</sub> > 2<sup>2n</sup>/(2n+1)). | + | |Числа сочетаний в треугольнике Паскаля: возрастание элементов к середине строки и убывание после середины (C<sup>k</sup><sub>n</sub> < C<sup>k+1</sup><sub>n</sub> при k < (n-1)/2 и C<sup>k</sup><sub>n</sub> > C<sup>k+1</sup><sub>n</sub> при k > (n-1)/2), симметрия (C<sup>k</sup><sub>n</sub> = C<sup>n-k</sup><sub>n</sub>), оценка среднего элемента в строке через сумму и количество элементов в этой строке (C<sup>n</sup><sub>2n</sub> > 2<sup>2n</sup>/(2n+1)).<br> |
− | Сумма знакопеременных элементов n строки в треугольнике Паскаля равна нулю (через удвоение элементов предыдущей строки с противоположными знаками, через разложение (1-1)<sup>n</sup>). | + | |
− | Формулы для 11<sup>2</sup>, 11<sup>3</sup>, 11<sup>4</sup> и связь со строками треугольника Паскаля (доказательство через разложение 11<sup>k</sup> = (10+1)<sup>k</sup> по биному Ньютона). | + | Сумма знакопеременных элементов n строки в треугольнике Паскаля равна нулю (через удвоение элементов предыдущей строки с противоположными знаками, через разложение (1-1)<sup>n</sup>).<br> |
− | Формула включений-исключений: через диаграммы Эйлера-Вена для 2 и 3 множеств, формулировка в общем случае. | + | |
+ | Формулы для 11<sup>2</sup>, 11<sup>3</sup>, 11<sup>4</sup> и связь со строками треугольника Паскаля (доказательство через разложение 11<sup>k</sup> = (10+1)<sup>k</sup> по биному Ньютона).<br> | ||
+ | |||
+ | Формула включений-исключений: через диаграммы Эйлера-Вена для 2 и 3 множеств, формулировка в общем случае.<br> | ||
+ | |||
Принцип Дирихле (pigeonhole principle): если кроликов больше, чем клеток, то при рассадке кроликов по клеткам по крайней мере в одну клетку попадут по крайней мере два кролика. | Принцип Дирихле (pigeonhole principle): если кроликов больше, чем клеток, то при рассадке кроликов по клеткам по крайней мере в одну клетку попадут по крайней мере два кролика. | ||
+ | ||[https://mathus.ru/math/kombinatorika.pdf Комбинаторика (в частности задачки по темам с ответами)] стр.41-44<br> | ||
+ | [https://publications.hse.ru/mirror/pubs/share/direct/393719078.pdf Лекции по дискретной математике ФКН ВШЭ] стр.66 | ||
+ | |||
+ | |- | ||
+ | |7.10.2022 | ||
+ | |Числа Фибоначчи: задача про кроликов, определение (F<sub>0</sub> = 0, F<sub>1</sub> = 1, F<sub>n+1</sub> = F<sub>n</sub> + F<sub>n-1</sub>), F<sub>n</sub> равно сумме "диагонали" треугольника Паскаля (F<sub>n</sub> = C<sub>n-1</sub><sup>0</sup> + C<sub>n-2</sub><sup>1</sup> + C<sub>n-3</sub><sup>2</sup> + ... + C<sub>n-[n/2]</sub><sup>[n/2]-1</sup> целая часть должна быть верхней), явная формула (F<sub>n</sub> = 1/٧5((1+٧5)/2)^n - 1/٧5((1-٧5)/2)^n) и ее доказательство по индукции. | ||
+ | |||
+ | Индукция: принцип математической индукции, база и переход их согласованность, индуктивное предположение, доказательство равенств, неравенств, разбор текстовой задачи (машина на краю пустыни). | ||
+ | Примеры неверных доказательств по индукции (резиновый автобус, куча манки, одномастные лошади). | ||
+ | |||
+ | |[https://publications.hse.ru/mirror/pubs/share/direct/393719078.pdf Лекции по дискретной математике ФКН ВШЭ] стр.16-51 | ||
+ | [https://disk.yandex.ru/i/C9uejT5Zu5Fahw Примеры с решениями и без задач на индукцию] | ||
+ | |||
+ | |- | ||
+ | |14.10.2022 | ||
+ | |Числа Фибоначчи (повторение). | ||
+ | Линейные рекуррентные соотношения в разных задачах. | ||
+ | Рекурсия (программирование, литература) и ее связь с рекуррентными соотношениями. | ||
+ | Основная теорема о рекуррентных соотношениях (Master theorem): оценка сложности рекурсивных алгоритмов. | ||
+ | |||
+ | Рекуррентные записи n! и геометрических прогрессий. | ||
+ | |||
+ | Индукция: повторение, связь с рекуррентными соотношениями, пример вложенной индукции (количество разломов прямоугольной шоколадки). | ||
+ | |||
+ | |[https://ru.wikipedia.org/wiki/Основная_теорема_о_рекуррентных_соотношениях Основная теорема о рекуррентных соотношениях] | ||
+ | [https://disk.yandex.ru/i/C9uejT5Zu5Fahw Примеры с решениями и без задач на индукцию] | ||
+ | |||
+ | |- | ||
+ | |21.10.2022 | ||
+ | |Числа Каталана (по заявкам): рекуррентная формула, количество правильных скобочных последовательностей, количество способов разбить n-угольник диагоналями на треугольники. | ||
+ | |||
+ | Системы счисления: позиционные, примеры, n-ичные дроби, переводы между системами счислений целых чисел и дробных частей, погрешность в случае прерывания бесконечных дробей. | ||
+ | |||
+ | Римская система счисления: способы записи чисел, сложность алгоритмов сложения и умножения чисел. | ||
+ | |||
+ | Признаки делимости в n-ичной системе счисления: схожесть признаков делимости на n-1 и n+1 с признаками делимости на 9 и 11 для десятичной системы, схожесть признаков делимости на делители n с признаками делимости на 5 и 10 для десятичной системы. | ||
+ | |||
+ | Троичная система: взвешивание путем уравновешивания весов с двумя чашами. | ||
| | | | ||
+ | [https://disk.yandex.ru/i/UjJYIydJppYhQg Статья про числа Каталана] | ||
+ | [https://disk.yandex.ru/i/MOK8NEeNVq5SYA Книжка по системам счисления] | ||
+ | |||
+ | |- | ||
+ | |01.11.2022 | ||
+ | |Простые числа: определение, основная теорема арифметики (любое число однозначно разлагается в произведение простых), бесконечное количество простых чисел (два доказательства 1. p<sub>1</sub>p<sub>2</sub>...p<sub>n</sub>+1 ; 2. (k+1)<sup>n</sup> << 2<sup>k</sup> при фиксированном n и растущем k), Постулат Бертрана (теорема Чебышева): для любого натурального n ⩾ 2 найдётся простое число p в интервале n < p < 2n. | ||
+ | |||
+ | Остатки от деления и вычеты: сложение, вычитание, умножение, поиск обратного вычета. | ||
+ | Запись вычетов через отрицательные числа для удобства вычислений. | ||
+ | Примеры, когда обратного вычета не существует (элемент и модуль не взаимно просты). | ||
+ | |||
+ | Алгоритм Евклида (с использованием остатка от деления по модулю): сам алгоритм и оценка числа итераций через числа Фибоначчи. | ||
+ | |||
+ | |[http://files.school-collection.edu.ru/dlrstore/e4d919f5-8435-4fe3-a779-275181a69951/M_1.1.4/M_1.1.4.html Вычеты (короткая базовая статья)] | ||
+ | |||
+ | [https://publications.hse.ru/mirror/pubs/share/direct/393719078.pdf Лекции по дискретной математике ФКН ВШЭ] стр.143-156 | ||
+ | |||
+ | |- | ||
+ | |11.11.2022 | ||
+ | |Идея кодирования с открытым ключом. | ||
+ | Диофантовы уравнения: примеры, великая теорема Ферма, линейные Диофантовы уравнения с двумя неизвестными, критерий разрешимости. | ||
+ | Расширенный алгоритм Евклида: решение линейных Диофантовых уравнений с двумя неизвестными. | ||
+ | Сведение поиска обратного по умножению элемента по модулю к решению линейного Диофантова уравнения с двумя неизвестными. | ||
+ | Единственность обратного по умножению элемента по модулю (если существует, то единственный). | ||
+ | |||
+ | Малая теорема Ферма: формулировка, четыре доказательства (мультиномиальное разложение, индукция и бином Ньютона, раскраска бус, перемножение чисел специального вида), поиск обратного по умножению элемента через малую теорему Ферма в случае простого модуля. | ||
+ | |[https://publications.hse.ru/mirror/pubs/share/direct/393719078.pdf Лекции по дискретной математике ФКН ВШЭ] стр.154-163 | ||
+ | |||
+ | |||
+ | |- | ||
+ | |15.11.2022 | ||
+ | |Идея проверки числа на простоту:<br> | ||
+ | 1) проверка делимости на простые до корня из числа;<br> | ||
+ | 2) проверка взаимной простоты с числами от 2 до n-1;<br> | ||
+ | 3) (тест Ферма) проверка справедливости малой теоремы Ферма для чисел от 2 до n-1 (и числа Кармайкла);<br> | ||
+ | 4) (тест Рабина) проверка справедливости малой теоремы Ферма плюс корней из 1. | ||
+ | |||
+ | Китайская теорема об остатках: система сравнений по взаимнопростым модулям имеет единственное решение по произведению модулей. | ||
+ | Доказательство и решения систем сравнений с помощью расширенного алгоритма Евклида. | ||
+ | |[https://publications.hse.ru/mirror/pubs/share/direct/393719078.pdf Лекции по дискретной математике ФКН ВШЭ] стр.161-165 | ||
+ | |||
+ | |- | ||
+ | |18.11.2022 | ||
+ | |Китайская теорема об остатках: доказательство (индукция во числу сравнений), Следствие: независимость распределения остатков по взаимнопростым модулям.<br> | ||
+ | Функция Эйлера: определение и вычисление для простых чисел, степеней простых чисел, составных чисел.<br> | ||
+ | Теорема Эйлера: формулировка, малая теорема Ферма как частный случай, доказательство (аналогично 4 доказательству малой теоремы Ферма, через обратимые остатки и их перемножение).<br> | ||
+ | Алгоритм кодирования с открытым ключом RSA: определение, корректность кодирования и декодирования, устойчивость к атакам. | ||
+ | |[https://publications.hse.ru/mirror/pubs/share/direct/393719078.pdf Лекции по дискретной математике ФКН ВШЭ] стр.162-167<br> | ||
+ | [https://disk.yandex.ru/i/fX6Q_FMRE-I_Zg Лекции по криптографии] (тут довольно хорошо объяснен алгоритм RSA и еще много что) | ||
+ | |||
+ | |- | ||
+ | |22.11.2022 | ||
+ | |Графы: определение (V,E), множество вершин, множество ребер, изолированная вершина, степень вершины, способы задания графов (матрица смежности, матрица инцидентности, список смежности).<br> | ||
+ | Формула 2|E|=Σ deg(v<sub>i</sub>).<br> | ||
+ | Маршрут, путь, простой путь, расстояние между вершинами (длина кратчайшего пути), диаметр графа (самое большое расстояние между вершинами).<br> | ||
+ | Цикл, простой цикл.<br> | ||
+ | Связный граф, компонента связности.<br> | ||
+ | Оценка: количество компонент связности ≥ |V|-|E|.<br> | ||
+ | Следствие: для поиска самого тяжелого камня среди n камней необходимо n-1 взвешивание. | ||
+ | |[https://publications.hse.ru/mirror/pubs/share/direct/393719078.pdf Лекции по дискретной математике ФКН ВШЭ] стр.95-118<br> | ||
+ | |||
+ | |- | ||
+ | |25.11.2022 | ||
+ | |Деревья: (четыре определения и их эквивалентность) связный граф с V-1 ребром; минимальный связный граф; связный ациклический граф; граф, между любыми двумя вершинами которого существует единственный путь.<br> | ||
+ | ''Дополнительно:'' бинарное дерево поиска: поиск элемента, добавление элемента, удаление элемента, поиск следующего и предшествующего элементов.<br> | ||
+ | Существование у произвольного дерева по крайней мере двух листьев (два доказательства: через формулу 2|E|=Σ deg(v<sub>i</sub>) и через максимально удаленные вершины).<br> | ||
+ | Остовное дерево связного графа, возможность удаления из связного графа вершины вместе с ребрами без потери связности.<br> | ||
+ | Правильная раскраска: определение, примеры, критерий 2-раскрашиваемости графа (отсутствие циклов нечетной длины).<br> | ||
+ | ''Дополнительно:'' алгоритмы поиска в ширину (BFS) и глубину (DFS). | ||
+ | |[https://publications.hse.ru/mirror/pubs/share/direct/393719078.pdf Лекции по дискретной математике ФКН ВШЭ] стр.118-123<br> | ||
+ | [https://disk.yandex.ru/i/XDNEDxyuccjLGA Т.Кормен и др. «Алгоритмы Построение и Анализ» стр 316-322, 607-663] | ||
+ | |||
+ | |- | ||
+ | |02.12.2022 | ||
+ | |Жадные алгоритмы: алгоритмы, оптимизирующие некоторый параметр на '''каждом''' шаге, примеры (задача о рюкзаке в дискретном и непрерывном вариантах, задача о поиске минимального остовного дерева, задача о загруженности аудитории).<br> | ||
+ | Эйлеровы циклы и пути: цикл (путь) проходящий по каждому ребру графа ровно один раз, критерии наличия Эйлерова цикла (пути) в неориентированном и ориентированном графах.<br> | ||
+ | Гамильтоновы циклы и пути: цикл (путь) проходящий через каждую вершину графа ровно один раз, отсутствие критерия, NP-полнота задачи о поиске Гамильтонова цикла в графе, теорема Оре.<br> | ||
+ | Чуть-чуть логики: формализация метода доказательства с помощью правила контрапозиции и метода доказательства от противного. | ||
+ | |[https://publications.hse.ru/mirror/pubs/share/direct/393719078.pdf Лекции по дискретной математике ФКН ВШЭ] стр.132-135<br> | ||
+ | [https://disk.yandex.ru/i/XDNEDxyuccjLGA Т.Кормен и др. «Алгоритмы Построение и Анализ» стр 442-482, 642, 1086, 1101-1103] | ||
+ | |||
+ | |- | ||
+ | |09.12.2022 | ||
+ | |Двудольные графы, паросочетания, теорема Холла (о свадьбах): формулировка, примеры.<br> | ||
+ | Сеть: ориентированный граф с истоком и стоком, с заданными пропускными способностями на ребрах.<br> | ||
+ | Поток: неотрицательная функция, заданная на ребрах сети, на каждом ребре не превосходящая пропускной способности ребра и суммарно равная нулю в каждой вершине сети, кроме стока и истока.<br> | ||
+ | Разрез: разбиение вершин сети на два множества S и T, содержащих соответственно исток и сток.<br> | ||
+ | Пропускная способность разреза: сумма пропускных способностей ребер, ведущих из множества вершин S в множество вершин T.<br> | ||
+ | Теорема Форда-Фалкерсона: величина максимального потока равна пропускной способности минимального разреза.<br> | ||
+ | Алгоритм нахождения максимального потока в сети: начинаем с нулевого потока, ищем увеличивающий путь (лучше минимальной длины), увеличиваем поток, ищем следующий увеличивающий путь, увеличиваем поток и т.д. | ||
|} | |} | ||
Строка 65: | Строка 205: | ||
[https://disk.yandex.ru/i/QXW6c4tUxwjV4g Комбинаторика-3] | [https://disk.yandex.ru/i/QXW6c4tUxwjV4g Комбинаторика-3] | ||
+ | |||
+ | [https://disk.yandex.ru/i/lfhWkTgRJPvbGw Числа Фибоначчи, Индукция] | ||
+ | |||
+ | [https://disk.yandex.ru/i/I1VBzSGylBSUtw Числа Фибоначчи-2, Индукция-2] | ||
+ | |||
+ | [https://disk.yandex.ru/i/6ZeDU1zdCnlBog Системы счисления] | ||
+ | |||
+ | [https://disk.yandex.ru/i/pC1rFQaRgrr5KA Делимость и Вычеты] | ||
+ | |||
+ | [https://disk.yandex.ru/i/iGuukuYtT4O1iQ Расширенный алгоритм Евклида, малая теорема Ферма] | ||
+ | |||
+ | [https://disk.yandex.ru/i/yGSOYGTeGLBJVg Малая теорема Ферма, Китайская теорема об остатках] | ||
+ | |||
+ | [https://disk.yandex.ru/i/KjQpX2s2Vj8ITw Теорема Эйлера] | ||
+ | |||
+ | [https://disk.yandex.ru/i/OOaz4DVxqMuUkg Графы-1] | ||
+ | |||
+ | [https://disk.yandex.ru/i/KiTGSNoG6VM_Hg Деревья, правильные раскраски] | ||
+ | |||
+ | [https://disk.yandex.ru/i/KE1u7QBFzIgkcA Эйлеровы и Гамильтоновы циклы и пути] | ||
+ | |||
+ | [https://disk.yandex.ru/i/WhUOhUDduFOzjQ Потоки в сетях] | ||
+ | |||
+ | [https://disk.yandex.ru/d/HDGsExq8H2fkcA Повторение] | ||
== Домашние задания == | == Домашние задания == | ||
+ | '''В ДЗ-8 появилась бонусная задача на бинарные деревья поиска. Ссылку на книгу по теме можно найти в допматериалах к последней лекции.'''<br> | ||
+ | Книга «Алгоритмы. Построение и Анализ.» Т.Кормена и др. на мой взгляд является отличным источником знаний для начинающего (и не только) программиста -- в ней рассмотрено большое количество основных понятий и определений, для каждого алгоритма приведен псевдокод (иногда не один) и оценка сложности. Этой книгой можно пользоваться как справочником: читать 2-3 страницы по интересующей теме и временно откладывать. | ||
+ | |||
'''Правила сдачи ДЗ''': решения задач из домашнего задания оформляются письменно, первый лист работы подписывается, только ответы не проверяются, должно присутствовать ''полное рассуждение'', затем текст сканируется, файл называется в соответствии с ФИО студента (например, SysoevaLN.pdf) и отправляется на проверку (ссылку на загрузку см. в таблице ниже). | '''Правила сдачи ДЗ''': решения задач из домашнего задания оформляются письменно, первый лист работы подписывается, только ответы не проверяются, должно присутствовать ''полное рассуждение'', затем текст сканируется, файл называется в соответствии с ФИО студента (например, SysoevaLN.pdf) и отправляется на проверку (ссылку на загрузку см. в таблице ниже). | ||
Строка 82: | Строка 249: | ||
|[https://disk.yandex.ru/i/87IgAYKMLGbEyA Домашнее задание №2] | |[https://disk.yandex.ru/i/87IgAYKMLGbEyA Домашнее задание №2] | ||
|[https://forms.gle/zZCx8hGiHi1GDy1j6 Файл сюда] | |[https://forms.gle/zZCx8hGiHi1GDy1j6 Файл сюда] | ||
− | |||
|- | |- | ||
|7.10.2022 | |7.10.2022 | ||
|[https://disk.yandex.ru/i/Yy6-_Hda1UEQLg Домашнее задание №3] | |[https://disk.yandex.ru/i/Yy6-_Hda1UEQLg Домашнее задание №3] | ||
− | | | + | |[https://forms.gle/zZCx8hGiHi1GDy1j6 Файл сюда] |
+ | |- | ||
+ | |21.10.2022 | ||
+ | |[https://disk.yandex.ru/i/aofNsKB9AMhONA Домашнее задание №4] | ||
+ | | [https://forms.gle/zZCx8hGiHi1GDy1j6 Файл сюда] | ||
+ | |- | ||
+ | |4.11.2022 | ||
+ | |[https://disk.yandex.ru/i/V62t0PGwzQmJoA Домашнее задание №5] | ||
+ | | [https://forms.gle/zZCx8hGiHi1GDy1j6 Файл сюда] | ||
+ | |- | ||
+ | |12.11.2022 | ||
+ | |[https://disk.yandex.ru/i/ZtHuki9PQHV5Cg Домашнее задание №6] | ||
+ | | [https://forms.gle/zZCx8hGiHi1GDy1j6 Файл сюда] | ||
+ | |- | ||
+ | |22.11.2022 | ||
+ | |[https://disk.yandex.ru/i/X6LCkozybxDH7w Домашнее задание №7] | ||
+ | | [https://forms.gle/zZCx8hGiHi1GDy1j6 Файл сюда] | ||
+ | |- | ||
+ | |27.11.2022 | ||
+ | |[https://disk.yandex.ru/i/FjywLphzBhL0Xw Домашнее задание №8] | ||
+ | | [https://forms.gle/zZCx8hGiHi1GDy1j6 Файл сюда] | ||
+ | |- | ||
+ | |4.12.2022 | ||
+ | |[https://disk.yandex.ru/i/WRZnhkUVF8mXJA Домашнее задание №9] | ||
+ | | [https://forms.gle/zZCx8hGiHi1GDy1j6 Файл сюда] | ||
+ | |- | ||
+ | |18.12.2022 | ||
+ | |[https://disk.yandex.ru/i/gq1oxKo9Y78NEw Домашнее задание №10] | ||
+ | | [https://forms.gle/zZCx8hGiHi1GDy1j6 Файл сюда] | ||
|} | |} |
Текущая версия на 13:10, 20 февраля 2023
Дорогие студенты!
На этой странице будут появляться различные материалы и объявления, связанные с курсом «Дискретная математика», читаемого для студентов 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 |
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) проверка делимости на простые до корня из числа; Китайская теорема об остатках: система сравнений по взаимнопростым модулям имеет единственное решение по произведению модулей. Доказательство и решения систем сравнений с помощью расширенного алгоритма Евклида. |
Лекции по дискретной математике ФКН ВШЭ стр.161-165 |
18.11.2022 | Китайская теорема об остатках: доказательство (индукция во числу сравнений), Следствие: независимость распределения остатков по взаимнопростым модулям. Функция Эйлера: определение и вычисление для простых чисел, степеней простых чисел, составных чисел. |
Лекции по дискретной математике ФКН ВШЭ стр.162-167 Лекции по криптографии (тут довольно хорошо объяснен алгоритм RSA и еще много что) |
22.11.2022 | Графы: определение (V,E), множество вершин, множество ребер, изолированная вершина, степень вершины, способы задания графов (матрица смежности, матрица инцидентности, список смежности). Формула 2|E|=Σ deg(vi). |
Лекции по дискретной математике ФКН ВШЭ стр.95-118 |
25.11.2022 | Деревья: (четыре определения и их эквивалентность) связный граф с V-1 ребром; минимальный связный граф; связный ациклический граф; граф, между любыми двумя вершинами которого существует единственный путь. Дополнительно: бинарное дерево поиска: поиск элемента, добавление элемента, удаление элемента, поиск следующего и предшествующего элементов. |
Лекции по дискретной математике ФКН ВШЭ стр.118-123 Т.Кормен и др. «Алгоритмы Построение и Анализ» стр 316-322, 607-663 |
02.12.2022 | Жадные алгоритмы: алгоритмы, оптимизирующие некоторый параметр на каждом шаге, примеры (задача о рюкзаке в дискретном и непрерывном вариантах, задача о поиске минимального остовного дерева, задача о загруженности аудитории). Эйлеровы циклы и пути: цикл (путь) проходящий по каждому ребру графа ровно один раз, критерии наличия Эйлерова цикла (пути) в неориентированном и ориентированном графах. |
Лекции по дискретной математике ФКН ВШЭ стр.132-135 Т.Кормен и др. «Алгоритмы Построение и Анализ» стр 442-482, 642, 1086, 1101-1103 |
09.12.2022 | Двудольные графы, паросочетания, теорема Холла (о свадьбах): формулировка, примеры. Сеть: ориентированный граф с истоком и стоком, с заданными пропускными способностями на ребрах. |
Семинары
Расширенный алгоритм Евклида, малая теорема Ферма
Малая теорема Ферма, Китайская теорема об остатках
Эйлеровы и Гамильтоновы циклы и пути
Домашние задания
В ДЗ-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 | Файл сюда |