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