Основная профессиональная образовательная программа высшего образования

Тема 10. Эксперименты с автоматами
Основные понятия теории экспериментов с автоматами. Диагностические эксперименты. Установочные эксперименты. Эксперименты по распознаванию автоматов. Тестирование автоматов. Тестирование комбинационных схем. Методы построения тестов. Вероятностное тестирование. Оценки вероятности обнаружения неисправности. Псевдослучайное тестирование.
Тема 11. Вероятностные автоматы
Определение и частные виды. Декомпозиция. Эквивалентность состояний. Применения.
Тема 12. Основные комбинаторные методы
Принцип сложения и умножения. Подмножества. Примеры использования принципа сложения и умножения. Принцип включения и исключения. Выборки. Размещениями с повторениями. Размещения без повторений. Сочетания без повторений. Бином Ньютона и полиномиальная формула (комбинаторный смысл). Сочетания с повторениями. Перестановки без повторений. Свойства перестановок. Перестановки без повторений. Таблица инверсий. Задача о разупорядочении. Субфакториалы. Перестановки с повторениями. Задача о размещениях.
Тема 13. Рекуррентные соотношения
Простые примеры рекуррентных последовательностей. Числа Фибоначчи. Свойства чисел Фибоначчи. Нерекуррентная формула для чисел Фибоначчи. Вывод нерекуррентной формулы для чисел Фибоначчи с помощью производящей функции. Фибоначчиева система счисления. Числа Каталана. Нелинейная рекуррентная формула. Нерекуррентная формула. Задача о триангуляции многоугольника. Пути Дика.
Тема 14. Числа Стирлинга и их свойства
Разбиения. Числа Стирлинга второго рода. Числа Белла. Разбиения на циклы. Числа Стирлинга первого рода. Разбиение числа на слагаемые.
Тема 15. Производящие функции
Рекуррентные соотношения и производящие функции. Производящие функции. Задача о расстановке чёрных и белых шаров. Операции над рядами. Производящие функции. Примеры.
Тема 16. Ладейные полиномы
Ладейные полиномы. Связь ладейных полиномов с перестановками. Примеры.
Тема 17. Комбинаторные методы в решении экстремальных задач
Латинские прямоугольники и квадраты. Ортогональные латинские квадраты. Матрицы Адамара. Перечисление графов отображений. Экстремальные задачи и перебор. Оптимизационные задачи. Универсальные задачи. Метод ветвей и границ. Комбинаторные конфигурации, блок-схемы. Трансверсали. Конечные проективные плоскости. Перечисление графов и отображений.