Дискретная Математика: различия между версиями
(→Лекции) |
(→Лекции) |
||
Строка 162: | Строка 162: | ||
|22.11.2022 | |22.11.2022 | ||
|Графы: определение (V,E), множество вершин, множество ребер, изолированная вершина, степень вершины, способы задания графов (матрица смежности, матрица инцидентности, список смежности).<br> | |Графы: определение (V,E), множество вершин, множество ребер, изолированная вершина, степень вершины, способы задания графов (матрица смежности, матрица инцидентности, список смежности).<br> | ||
− | Формула 2|E|=Σ | + | Формула 2|E|=Σ deg(v<sub>i</sub>).<br> |
Маршрут, путь, простой путь, расстояние между вершинами (длина кратчайшего пути), диаметр графа (самое большое расстояние между вершинами).<br> | Маршрут, путь, простой путь, расстояние между вершинами (длина кратчайшего пути), диаметр графа (самое большое расстояние между вершинами).<br> | ||
Цикл, простой цикл.<br> | Цикл, простой цикл.<br> |
Версия 14:21, 23 ноября 2022
Дорогие студенты!
На этой странице будут появляться различные материалы и объявления, связанные с курсом «Дискретная математика», читаемого для студентов 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 |
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 |
Семинары
Расширенный алгоритм Евклида. Малая теорема Ферма.
Малая теорема Ферма. Китайская теорема об остатках.
Домашние задания
Правила сдачи ДЗ: решения задач из домашнего задания оформляются письменно, первый лист работы подписывается, только ответы не проверяются, должно присутствовать полное рассуждение, затем текст сканируется, файл называется в соответствии с ФИО студента (например, 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 | Файл сюда | Решения ДЗ-6 |
22.11.2022 | Домашнее задание №7 | Файл сюда | |
27.11.2022 | Домашнее задание №8 | Файл сюда |