Войти
Математика 12 лекций
Дискретная математика
1
Лектор
Гашков Сергей Борисович
#лекции
Механико-математический факультет
VI семестр
Осень 2018

Курс "Дискретная математика" состоит из трех разделов:

1) Комбинаторика - рассматриваются основные принципы комбинаторики, схемы размещений шаров по ящикам, биномиальное преобразование, числа Стирлинга, производящие функции, рекуррентные соотношения и т.д.

2) Графы - рассматриваются основные понятия теории графов, формула Эйлера, некоторые алгоритмы на графах, теорема Форда-Фалкерсона и т.д.

3) Кодирование - рассматривается алфавитное кодирование, некоторые классические задачи и алгоритмы.

 

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

Лекция 1. Введение в комбинаторику.
Два принципа комбинаторики: сложение и умножение Еще два принципа: взаимно-однозначное соответствие и двойной подсчет Пример задачи с решением с помощью принципа двойного подсчета Возвращаемся к принципу сложения: конечное число множеств Формула включения-исключения, примеры, разные варианты написания, пример - теорема Лапласа Три основные задачи

Лекция 2. Биномиальное преобразование. Числа Стирлинга.
Обратное преобразование рода  Задача о размещении шаров по ящикам

Лекция 3. Числа Стирлинга 1 и 2 рода. Взаимно обратные линейные преобразования.
Взаимно обратные линейные преобразования Биномиальное преобразование рода Треугольник Пирса Треугольник Паскаля Формула Добинского

Лекция 4. Рекуррентное уравнение.
Рекуррентное уравнение Диаграмма Феррерса Производящие функции Задача о размене монет Проблема Фробениуса Теорема Эйлера, теорема Харди - Рамануджана Рассказ о Рамануджане

Лекция 5. Производящие функции.
Вычисление рекуррентного соотношения Решение задачи с использованием метода производящих функций (1) Решение задачи с использованием метода производящих функций (2)

Лекция 6. Линейное рекуррентное соотношение.
Линейное рекуррентное соотношение с постоянными коэффициентами конечного порядка Метод производящих функций Использование матриц при решении линейного рекуррентного соотношения

Лекция 7. Производящие функции множеств.
Использование матриц при решении линейного рекуррентного соотношения Производящие функции множеств Обращение степенных рядов Функция Мёбиуса

Лекция 8. Функция Мёбиуса.
Функция Мёбиуса Формула включения-исключения Примеры применения функции Мёбиуса

Лекция 9. Теория графов.
Теория графов (общая информация) Основные определения  Применение формулы Эйлера Двойственные плоские графы Доказательство теоремы с помощью формулы Эйлера

Лекция 10. Алгоритм нахождения максимального потока в сети.
Алгоритм нахождения максимального потока в сети Алгоритм поиска в ширину Теорема Форда-Фалкерсона о максимальном потоке и минимальном разрезе Алгоритм Эдмондса-Карпа в двудольных графах Теорема Холла о двудольных графах

Лекция 11. Теория кодирования.
Теорема о спросе и предложении Алфавитное кодирование

Лекция 12. Теория кодирования (продолжение).
Задача о построении кода с минимальной средней длиной Алгоритм Хаффмана Лемма 2 Лемма о редукции Кодирование с исправлением ошибок