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

Материал из MathINFO
Перейти к навигации Перейти к поиску

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

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

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

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

Консультации

Консультации будут проходить онлайн по понедельникам в 17:00, задавайте ваши вопросы Дмитрию, присоединяйтесь к консультациям!

Join Zoom Meeting https://us05web.zoom.us/j/4685079351?pwd=cVJkeVkzUUR1bXNjMzJ1WDRrN0EyUT09

Meeting ID: 468 507 9351 Passcode: yqTLi1

Лекции

дата лекции тема лекции дополнительные материалы
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 и еще много что)

Семинары

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

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

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

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

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

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

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

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

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

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

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

!! Дедлайн по ДЗ-7 перенесен на 9:30 22го ноября !!

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

дедлайн Домашнее задание Ссылка на загрузку файла Решения и критерии
23.09.2022 Домашнее задание №1 Файл сюда Решения ДЗ-1
30.09.2022 Домашнее задание №2 Файл сюда Решения ДЗ-2
7.10.2022 Домашнее задание №3 Файл сюда Решения ДЗ-3
21.10.2022 Домашнее задание №4 Файл сюда Решения ДЗ-4
4.11.2022 Домашнее задание №5 Файл сюда Решения ДЗ-5
12.11.2022 Домашнее задание №6 Файл сюда
22.11.2022 Домашнее задание №7 Файл сюда