Семинары по курсу "Дискретная математика", читающиеся на механико-математическом факультете МГУ в 6 семестре.

Список всех тем лекций

Семинар 1. Простейшие комбинаторные задачи. Изучение комбинаторных тождеств с помощью n-мерного куба.
План курса Типы задач о размещении шаров по ящикам Задача первого типа Задача второго типа Переформулировка задачи о сочетании с повторениями Вычисление некоторых сумм, составленных из биномиальных коэффициентов О методе производящих функций в комбинаторике О разных представлениях биномиального коэффициента Как удобно рисовать трехмерный куб Как удобно рисовать четырехмерный куб Как изображать произвольный n-мерный куб Тождество Паскаля О треугольнике Паскаля О числе рёбер в n-мерном кубе, ещё одно комбинаторное тождество Задача о числе цепей Куб как частично упорядоченное множество, антицепи Задача: какую максимальную мощность может иметь антицепь в кубе

Семинар 2. Задачи на решетке.
Как рисовать n-мерный куб, дополнение Некоторые задачи по теме "n-мерный куб" Задачи о числе кратчайших путей Свертка Вандермонда Задача Эйлера о перестановках и "честная" карточная игра Задачи на тождества с биномиальными коэффициентами

Семинар 3. Числа Каталана.
Задачи на перемещение вдоль ломаной Первый способ, метод зеркального отражения Второй способ Задачи, приводящие к числам Каталана

Семинар 4. Блуждание на прямой, задачи на рекуррентные соотношения.
Задача на числа Каталана, блуждание на прямой Задача о домино Задача на рекуррентные соотношения № 2

Семинар 5. Метод рекуррентных последовательностей.
Материал предыдущих семинаров Обход проблемы погрешностей при решении рекуррентной последовательности x n) домино

Семинар 6. Метод производящих функций. Начала теории графов.
Первая задача на метод производящих функций Задача про деревья (теорема Кэли)

Семинар 7. Теория графов и её приложения.
Задача о числе ориентированных деревьев Задача о ходе короля Задача Сильвестра Задача о разрезании прямоугольника

Семинар 8. Задачи на гамильтоновы циклы.
Задача о снегоуборочной машине Гамильтоновы циклы Задача о гамильтоновом пути на ромбододекаэдре Задача об обходе конём шахматной доски Теорема Дирака и подобные Задача о расстановке фигур на доске

Семинар 9. Теорема о спросе и предложении. История алфавитного кодирования.
Теорема о спросе и предложении, теорема Холла Алфавитное кодирование, исторический обзор

Семинар 10. Алфавитное кодирование. Однозначная декодируемость.
Алгоритм определения однозначной декодируемости кода Нахождение слова, декодируемого двумя способами Геометрическая (графовая) интерпретация префиксных кодов Задача о построении оптимального кода

Семинар 11. Алгоритм Хаффмана, алгоритм Шеннона.
Алгоритм Хаффмана, двоичный вариант Алгоритм Хаффмана, вариант с q-ичным алфавитом Алгоритм Шеннона

Семинар 12. Код Хемминга.
Коды Хемминга Порождающие матрицы Геометрическое свойство кода Хемминга