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

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

На этой странице будут появляться различные материалы и объявления, связанные с курсом «Дискретная математика», читаемого для студентов 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
30.09.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

Семинары

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

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

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

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

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

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

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