Дискретная Математика: различия между версиями
(не показано 14 промежуточных версий этого же участника) | |||
Строка 32: | Строка 32: | ||
|- | |- | ||
|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 | ||
+ | |Числа сочетаний в треугольнике Паскаля: возрастание элементов к середине строки и убывание после середины (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>).<br> | ||
+ | |||
+ | Формулы для 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): если кроликов больше, чем клеток, то при рассадке кроликов по клеткам по крайней мере в одну клетку попадут по крайней мере два кролика. | ||
+ | ||[https://mathus.ru/math/kombinatorika.pdf Комбинаторика (в частности задачки по темам с ответами)] стр.41-44<br> | ||
+ | [https://publications.hse.ru/mirror/pubs/share/direct/393719078.pdf Лекции по дискретной математике ФКН ВШЭ] стр.66 | ||
+ | |||
+ | |||
|} | |} | ||
Строка 62: | Строка 90: | ||
!Домашнее задание | !Домашнее задание | ||
!Ссылка на загрузку файла | !Ссылка на загрузку файла | ||
+ | !Решения и критерии | ||
|- | |- | ||
|23.09.2022 | |23.09.2022 | ||
|[https://disk.yandex.ru/i/WeEzyM70AzqNtw Домашнее задание №1] | |[https://disk.yandex.ru/i/WeEzyM70AzqNtw Домашнее задание №1] | ||
|[https://www.dropbox.com/request/cGNCtS3rrJoiE6NGCrz9 Файл сюда] | |[https://www.dropbox.com/request/cGNCtS3rrJoiE6NGCrz9 Файл сюда] | ||
+ | |[https://disk.yandex.ru/i/lmtlr4mP41Iy-Q Решения ДЗ-1] | ||
|- | |- | ||
Строка 71: | Строка 101: | ||
|[https://disk.yandex.ru/i/87IgAYKMLGbEyA Домашнее задание №2] | |[https://disk.yandex.ru/i/87IgAYKMLGbEyA Домашнее задание №2] | ||
|[https://forms.gle/zZCx8hGiHi1GDy1j6 Файл сюда] | |[https://forms.gle/zZCx8hGiHi1GDy1j6 Файл сюда] | ||
+ | |[https://disk.yandex.ru/i/_yELwtWaJS4RMA Решения ДЗ-2] | ||
|- | |- | ||
|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 Файл сюда] |
+ | | | ||
+ | |||
|} | |} |
Версия 18:13, 3 октября 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 Лекции по дискретной математике ФКН ВШЭ стр.66
|
Семинары
Домашние задания
Правила сдачи ДЗ: решения задач из домашнего задания оформляются письменно, первый лист работы подписывается, только ответы не проверяются, должно присутствовать полное рассуждение, затем текст сканируется, файл называется в соответствии с ФИО студента (например, SysoevaLN.pdf) и отправляется на проверку (ссылку на загрузку см. в таблице ниже).
дедлайн | Домашнее задание | Ссылка на загрузку файла | Решения и критерии |
---|---|---|---|
23.09.2022 | Домашнее задание №1 | Файл сюда | Решения ДЗ-1 |
30.09.2022 | Домашнее задание №2 | Файл сюда | Решения ДЗ-2 |
7.10.2022 | Домашнее задание №3 | Файл сюда |