• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Дискретная математика

2019/2020
Учебный год
RUS
Обучение ведется на русском языке
5
Кредиты
Статус:
Курс обязательный
Когда читается:
2-й курс, 3, 4 модуль

Преподаватель

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

Аннотация

В данном курсе студенты познакомятся с понятиями дискретной математики как основой важной части математического аппарата теории вероятностей и математической статистики, исследования операций, дискретной оптимизации, компьютерных наук и других дисциплин, получат опыт анализа дискретных структур, развитие строгого логического мышления.
Цель освоения дисциплины

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

  • Ознакомление студентов с основными методами и задачами комбинаторики и теории автоматов
Планируемые результаты обучения

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

  • Знание основных понятий и методов комбинаторики, теории автоматов
  • Умение исследовать комбинаторные свойства дискретных моделей
  • Умение применять методы дискретной математики в различных приложениях математики и компьютерных наук
Содержание учебной дисциплины

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

  • Элементарные комбинаторные подсчеты
    1. Основные комбинаторные числа: число перестановок, число сочетаний, число слов заданной длины в конечном алфавите. Бином Ньютона. Рекуррентное соотношение между биномиальными коэффиценттами:, треугольник Паскаля. Число функкций между двумя конечными множествами, число подмножеств конечного множества. Принцип включения-исключения. 2. Число сочетаний с повторениями и число целых решений уравнения x1+x2+...+xk=n. Рекуррентное соотношение для чисел Стирлинга 2-го рода (чисел размещения различимых объектов в неразличимых ящиках, ни один из которых не пуст).
  • Метод производящих функций в комбинаторике
    Производящие функции. Производящие функции основных последовательностей: постоянной, биномиальных коэффициентов, чисел сочетаний с повторениями. Производящие функции для задач о числе решений линейного уравнения в целых числах. Число размещений n неразличимых объектов в k различимых ящиках. Производящая функция для числа разбиения n на различные целые слагаемые.
  • Разбиения и диаграммы Юнга
    Разбиения и диаграммы Юнга. Число разбиений числа n на k слагаемыхи число разбиений n на слагаемые, непревосходящие k. Производящая функция этих чисел. Производящая функция чисел разбиений n на ненулевые слагаемые. Соотношение между количеством разбиений числа n на четное и нечетное число слагаемых. Рекуррентное соотношение для чисел разбиений n на ненулевые слагаемые.
  • Рекуррентные соотношения
    1. Рекуррентные соотношения. Общее и частное решение. Линейные однородные рекуррентные соотношения с постоянными коэффициентами. 2. Решения рекуррентных соотношений с помощью производящих функций. 3. Числа Каталана.
  • Экспоненциальные производящие функции в комбинаторике
    Экспоненциальные производящие функции. Число размещений n различимых объектов по k различимым непустым ящикам и число сюръективных функций. Числа Стирлинга 2-го рода.
  • Конечные автоматы
    Конечные автоматы. Определение. Диаграмма состояний. Детерминированные и недетерминированные КА. Операции над КА. Лемма о накачивании. Регулярные выражения и языки. Теорема Клини. Вопросы разрешимости автоматных языков.
Элементы контроля

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

  • неблокирующий Контрольные работы
  • неблокирующий Итоговая аттестация
Промежуточная аттестация

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

  • Промежуточная аттестация (4 модуль)
    0.5 * Итоговая аттестация + 0.5 * Контрольные работы
Список литературы

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

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

  • Дискретная математика и комбинаторика, Андерсон, Дж. А., 2003

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

  • Лекции о производящих функциях, Ландо, С. К., 2007