Дискретная математика, весна 2022
Здесь будут появляться материалы по курсу «Дискретная математика» для второго курса матфака, группы ОП «Математика».
Лекции: понедельник 11:00-12:20, ауд. 427 (курс завершён 30.05.22)вторник (нечетные недели) 11:00-12:20, ауд. 427
Плейлист с лекциями на YouTube
Домашнее задание №1 (дедлайн 21:00 22.05.22). Ссылка для загрузки.
Домашнее задание №2 (дедлайн 23:59 14.06.22). Ссылка для загрузки. Работу можно сдать до 23:59 16.06.22 со штрафом в 2 балла.
Контрольная работа состоялась 23.05.22 в 11:30.
Письменный экзамен состоится 27.06.22, начало в 11:00
Преподаватели
Евгений Юрьевич Смирнов, esmirnov@hse.ru, https://www.hse.ru/staff/esmirnov, каб. 307
Василий Геннадьевич Горбунов, vgorbunov@hse.ru, https://www.hse.ru/org/persons/216359816, каб. 402
Михаил Борисович Скопенков, mikhail.skopenkov@gmail.com, https://www.hse.ru/org/persons/133989976, каб. 329
Григорий Ривенович Челноков, grishabenruven@yandex.ru, https://www.hse.ru/org/persons/207925181, каб. 314
Лекции
1. Что значит «посчитать»? Различимые и неразличимые объекты, двенадцатеричный путь.
2. Линейные рекурренты и рациональные производящие функции (лекцию читал Ю.М.Бурман).
3. Разбиения. Эйлеровское бесконечное произведение. Пентагональная теорема Эйлера.
4. Гауссовы биномиальные коэффициенты.
5. Числа Каталана.
6. Формула включений и исключений. Частично упорядоченное множество, функция Мёбиуса.
7. Суммы степеней и числа Бернулли.
8. Перечисление деревьев. Коды Прюфера (лекцию читал В.Г.Горбунов)
Семинары
Листок 1. Перестановки и биномиальные коэффициенты.
Листок 2. Линейные рекурренты и рациональные функции.
Листок 3. Разбиения.
Листок π. Тройное тождество Якоби.
Листок 4. q-бином.
Листок 5. Числа Каталана.
Листок 6. Числа Бернулли.
Листок 7. Перечисление деревьев.
Формула оценки
Внимание: всё указанное относится к студентам ОП «Математика». Студенты совбака и совмага ВШЭ-ЦПМ могут узнать о том, что им предстоит, у Александра Савельевича Штерна и Юрия Михайловича Бурмана соответственно.
Оценка за курс складывается из следующих составляющих:
25% — оценка за письменные домашние задания (скорее всего, их будет два);
25% — контрольная работа (пройдёт после майских праздников);
50% — письменный экзамен.
Итог округляется до ближайшего целого (95% — это 10, а 94% — это 9).
Литература
Книг по дискретной математике огромное количество. Здесь приведены лишь несколько книг, материал из которых можно читать в дополнение к просмотру лекций. Список будет обновляться.
По просьбам слушателей я указываю только книги и статьи на русском языке.
Основная литература
[B] Виленкин Н.Я. Комбинаторика. изд. «Наука», 1969. https://math.ru/lib/363
Классическая книга, на которой выросло не одно поколение матшкольников.
[В3] Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика. МЦНМО, 2006.
Существенно расширенное издание предыдущей книги.
[Л] Ландо С.К. Введение в дискретную математику. МЦНМО, 2012.
http://vyshka.math.ru/pspdf/1112/discr/LandoBook.pdf
Матфаковский учебник по этому курсу. Всё, что нам нужно, там есть.
Дополнительная литература
[ГКП] Р.Грэхем, Д.Кнут, О.Паташик, Конкретная математика. Основание информатики. Мир: Бином, 2009
[М] Г.А.Мерзон, Алгебра, геометрия и анализ сумм степеней последовательных чисел (Матем. просв., сер. 3, вып. 21, с. 104–118)
[См] Е.Ю.Смирнов, Диаграммы Юнга, плоские разбиения и знакочередующиеся матрицы. М.: МЦНМО, 2014. https://www.mccme.ru/free-books/dubna/smirnov-asm.pdf
[C] Стенли, Р. Перечислительная комбинаторика. Мир, 1990.
Более сложный учебник; читать его подряд может быть тяжело, можно использовать его скорее как справочник.