Семинары по курсу "Дискретная математика", читающиеся на механико-математическом факультете МГУ в 6 семестре.
Список всех тем лекций
Семинар 1. Простейшие комбинаторные задачи. Изучение комбинаторных тождеств с помощью n-мерного куба.
План курса
Типы задач о размещении шаров по ящикам
Задача первого типа
Задача второго типа
Переформулировка задачи о сочетании с повторениями
Вычисление некоторых сумм, составленных из биномиальных коэффициентов
О методе производящих функций в комбинаторике
О разных представлениях биномиального коэффициента
Как удобно рисовать трехмерный куб
Как удобно рисовать четырехмерный куб
Как изображать произвольный n-мерный куб
Тождество Паскаля
О треугольнике Паскаля
О числе рёбер в n-мерном кубе, ещё одно комбинаторное тождество
Задача о числе цепей
Куб как частично упорядоченное множество, антицепи
Задача: какую максимальную мощность может иметь антицепь в кубе
Семинар 2. Задачи на решетке.
Как рисовать n-мерный куб, дополнение
Некоторые задачи по теме "n-мерный куб"
Задачи о числе кратчайших путей
Свертка Вандермонда
Задача Эйлера о перестановках и "честная" карточная игра
Задачи на тождества с биномиальными коэффициентами
Семинар 3. Числа Каталана.
Задачи на перемещение вдоль ломаной
Первый способ, метод зеркального отражения
Второй способ
Задачи, приводящие к числам Каталана
Семинар 4. Блуждание на прямой, задачи на рекуррентные соотношения.
Задача на числа Каталана, блуждание на прямой
Задача о домино
Задача на рекуррентные соотношения № 2
Семинар 5. Метод рекуррентных последовательностей.
Материал предыдущих семинаров
Обход проблемы погрешностей при решении рекуррентной последовательности
x n) домино
Семинар 6. Метод производящих функций. Начала теории графов.
Первая задача на метод производящих функций
Задача про деревья (теорема Кэли)
Семинар 7. Теория графов и её приложения.
Задача о числе ориентированных деревьев
Задача о ходе короля
Задача Сильвестра
Задача о разрезании прямоугольника
Семинар 8. Задачи на гамильтоновы циклы.
Задача о снегоуборочной машине
Гамильтоновы циклы
Задача о гамильтоновом пути на ромбододекаэдре
Задача об обходе конём шахматной доски
Теорема Дирака и подобные
Задача о расстановке фигур на доске
Семинар 9. Теорема о спросе и предложении. История алфавитного кодирования.
Теорема о спросе и предложении, теорема Холла
Алфавитное кодирование, исторический обзор
Семинар 10. Алфавитное кодирование. Однозначная декодируемость.
Алгоритм определения однозначной декодируемости кода
Нахождение слова, декодируемого двумя способами
Геометрическая (графовая) интерпретация префиксных кодов
Задача о построении оптимального кода
Семинар 11. Алгоритм Хаффмана, алгоритм Шеннона.
Алгоритм Хаффмана, двоичный вариант
Алгоритм Хаффмана, вариант с q-ичным алфавитом
Алгоритм Шеннона
Семинар 12. Код Хемминга.
Коды Хемминга
Порождающие матрицы
Геометрическое свойство кода Хемминга