• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Магистратура 2020/2021

Асимптотические методы в дискретных задачах

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Направление: 01.04.02. Прикладная математика и информатика
Когда читается: 1-й курс, 1, 2 модуль
Формат изучения: без онлайн-курса
Прогр. обучения: Математические методы моделирования и компьютерные технологии
Язык: русский
Кредиты: 4

Программа дисциплины

Аннотация

Цели освоения дисциплины «Асимптотические методы в дискретных задачах»: освоение основных методов построения асимптотик в задачах дискретной математики; получение навыков по применению методов дисциплины в различных задачах комбинаторики; - знакомство с новейшими результатами и актуальными задачами данной дисциплины.
Цель освоения дисциплины

Цель освоения дисциплины

  • освоение основных методов построения асимптотик в задачах дискретной математики
  • получение навыков по применению методов дисциплины в различных задачах комбинаторики
  • знакомство с новейшими результатами и актуальными задачами данной дисциплины
Планируемые результаты обучения

Планируемые результаты обучения

  • Знание теории и умение решать задачи по теме введение в асимптотические методы.
  • Знание теории и умение решать задачи по теме элементарные асимптотики в комбинаторных задачах.
  • Знание теории и умение решать задачи по теме методы построения асимптотических оценок для сумм.
  • Знание теории и умение решать задачи по теме методы оценок рекуррентных последовательностей.
  • Знание теории и умение решать задачи по теме производящие функции.
Содержание учебной дисциплины

Содержание учебной дисциплины

  • Введение в асимптотические методы
    Асимптотические оценки. Асимптотическое разложение по Пуанкаре. Различные асимптотические шкалы. Элементарные действия над асимптотиками. Простейшие примеры построения асимптотических формул, для явно заданных функций. Итерационный метод получения асимптотических оценок. Асимптотика корней трансцендентных уравнений.
  • Элементарные асимптотики в комбинаторных задачах
    Построение оценок для факториала и биномиальных коэффициентов, формула Стирлинга. Асимптотики решений комбинаторных задач о сочетаниях и размещениях. Асимптотические методы в задачах на графах.
  • Методы построения асимптотических оценок для сумм
    Оценки знакопостоянных сумм, случаи равномерного и доминирующего вклада. Сведение суммирования к интегрированию, формулы суммирования Эйлера-Маклорена, Абеля, Пуассона. Аналоги методов Лапласа, стационарной фазы и метода перевала для оценки сумм. Оценки знакопеременных сумм. Формула включения исключения. Теорема обращения Мебиуса. Асимптотика числа циклических слов. Оценки чисел Белла различных разбиений множества.
  • Методы оценок рекуррентных последовательностей
    Суммирование разностных уравнений с постоянными коэффициентами. Различные методы сведение разностных уравнений к дифференциальным уравнениям. Квазилинейные и нелинейные рекуррентности. Аналоги методов пограничного слоя и ВКБ для разностных уравнений. Асимптотика спектра трехдиагональных матриц, уравнение Матье.
  • Производящие функции
    Различные виды производящих функций. Аналитическое исследование производящих функций. Тауберовы и Абелевы теоремы. Полюсы, существенные особые точки и точки ветвления производящих функций. Метод перевала для производящих функций.
Элементы контроля

Элементы контроля

  • неблокирующий Текущий контроль знаний и навыков студентов
  • неблокирующий Экзамен
  • неблокирующий Текущий контроль знаний и навыков студентов
  • неблокирующий Экзамен
Промежуточная аттестация

Промежуточная аттестация

  • Промежуточная аттестация (2 модуль)
    0.5 * Текущий контроль знаний и навыков студентов + 0.5 * Экзамен
Список литературы

Список литературы

Рекомендуемая основная литература

  • Конкретная математика : основание информатики, Грэхем, Р. Л., Кнут, Д., 2009

Рекомендуемая дополнительная литература

  • Flajolet, Philippe. Analytic combinatorics / Philippe Flajolet, Robert Sedgewick. – Cambridge University Press, 2009