Дискретная Математика: различия между версиями

Материал из MathINFO
Перейти к навигации Перейти к поиску
 
(не показаны 84 промежуточные версии этого же участника)
Строка 14: Строка 14:
 
0,3 * Активность + 0,3 * Домашние задания + 0,4 * Экзамен
 
0,3 * Активность + 0,3 * Домашние задания + 0,4 * Экзамен
  
== Консультации ==
+
== Контрольная ==
  
Консультации будут проходить онлайн по понедельникам в 17:00, задавайте ваши вопросы Дмитрию, присоединяйтесь к консультациям!
+
'''Итоговая контрольная состоится 16го декабря!'''<br>
 
+
Большая просьба не опаздывать!!<br>
Join Zoom Meeting
+
Если все пойдет по плану, последние 30-50 минут занятий мы потратим на разбор задач из контрольной, чтобы у вас сразу было понимание, как вы написали и какие темы стоит повторить к экзамену.
https://us05web.zoom.us/j/4685079351?pwd=cVJkeVkzUUR1bXNjMzJ1WDRrN0EyUT09
+
Оценка за экзамен будет выставляться как максимум из оценок за КР и за Экзамен.
 
 
Meeting ID: 468 507 9351
 
Passcode: yqTLi1
 
  
 
== Лекции ==
 
== Лекции ==
Строка 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
 +
 
  
 
|-
 
|-
Строка 58: Строка 66:
  
 
Принцип Дирихле (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>
 +
Алгоритм нахождения максимального потока в сети: начинаем с нулевого потока, ищем увеличивающий путь (лучше минимальной длины), увеличиваем поток, ищем следующий увеличивающий путь, увеличиваем поток и т.д.
 
|}
 
|}
  
Строка 69: Строка 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) и отправляется на проверку (ссылку на загрузку см. в таблице ниже).
  
Строка 86: Строка 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

Лекции по дискретной математике ФКН ВШЭ стр.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 Файл сюда