Магистратура
2020/2021
Асимптотические методы в дискретных задачах
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс адаптационный (Математические методы моделирования и компьютерные технологии)
Направление:
01.04.02. Прикладная математика и информатика
Кто читает:
Департамент прикладной математики
Когда читается:
1-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Преподаватели:
Выборный Евгений Викторович
Прогр. обучения:
Математические методы моделирования и компьютерные технологии
Язык:
русский
Кредиты:
4
Контактные часы:
60
Программа дисциплины
Аннотация
Цели освоения дисциплины «Асимптотические методы в дискретных задачах»: освоение основных методов построения асимптотик в задачах дискретной математики; получение навыков по применению методов дисциплины в различных задачах комбинаторики; - знакомство с новейшими результатами и актуальными задачами данной дисциплины.
Цель освоения дисциплины
- освоение основных методов построения асимптотик в задачах дискретной математики
- получение навыков по применению методов дисциплины в различных задачах комбинаторики
- знакомство с новейшими результатами и актуальными задачами данной дисциплины
Планируемые результаты обучения
- Знание теории и умение решать задачи по теме введение в асимптотические методы.
- Знание теории и умение решать задачи по теме элементарные асимптотики в комбинаторных задачах.
- Знание теории и умение решать задачи по теме методы построения асимптотических оценок для сумм.
- Знание теории и умение решать задачи по теме методы оценок рекуррентных последовательностей.
- Знание теории и умение решать задачи по теме производящие функции.
Содержание учебной дисциплины
- Введение в асимптотические методыАсимптотические оценки. Асимптотическое разложение по Пуанкаре. Различные асимптотические шкалы. Элементарные действия над асимптотиками. Простейшие примеры построения асимптотических формул, для явно заданных функций. Итерационный метод получения асимптотических оценок. Асимптотика корней трансцендентных уравнений.
- Элементарные асимптотики в комбинаторных задачахПостроение оценок для факториала и биномиальных коэффициентов, формула Стирлинга. Асимптотики решений комбинаторных задач о сочетаниях и размещениях. Асимптотические методы в задачах на графах.
- Методы построения асимптотических оценок для суммОценки знакопостоянных сумм, случаи равномерного и доминирующего вклада. Сведение суммирования к интегрированию, формулы суммирования Эйлера-Маклорена, Абеля, Пуассона. Аналоги методов Лапласа, стационарной фазы и метода перевала для оценки сумм. Оценки знакопеременных сумм. Формула включения исключения. Теорема обращения Мебиуса. Асимптотика числа циклических слов. Оценки чисел Белла различных разбиений множества.
- Методы оценок рекуррентных последовательностейСуммирование разностных уравнений с постоянными коэффициентами. Различные методы сведение разностных уравнений к дифференциальным уравнениям. Квазилинейные и нелинейные рекуррентности. Аналоги методов пограничного слоя и ВКБ для разностных уравнений. Асимптотика спектра трехдиагональных матриц, уравнение Матье.
- Производящие функцииРазличные виды производящих функций. Аналитическое исследование производящих функций. Тауберовы и Абелевы теоремы. Полюсы, существенные особые точки и точки ветвления производящих функций. Метод перевала для производящих функций.
Элементы контроля
- Текущий контроль знаний и навыков студентов
- Экзамен
- Текущий контроль знаний и навыков студентов
- Экзамен