Методы комбинаторных вычислений

Бакалавриат (Системы автоматизированного проектирования)

Преподаватели:

• Лекции: Волосатова Тамара Михайловна, к.т.н.
• Лабораторные работы: Волосатова Тамара Михайловна, к.т.н. , Родионов Сергей Владимирович, Бочаров Владимир Александрович, Князева Светлана Вадимовна

Описание

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

Общий объем дисциплины составляет 3 зачетные единицы (з.е.), 108 академических часа.

План занятий

Модуль 1. Реализация комбинаторных вычислений на основе сочетаний с использованием бинома Ньютона и треугольника Паскаля.

• Лекция 1. Введение. Терминологический базис сочетаний. Обобщенная формальная постановка задач с использованием сочетаний.
• Лекция 2. Бином Ньютона.
• Лекция 3. Арифметический треугольник Паскаля .
• Лекция 4. Алгоритмы перечисления сочетаний и подмножеств.
• Лекция 5. Перестановки различных элементов .
• Лекция 6. Инверсии перестановок.
• Лекция 7. Циклический сдвиг перестановки и подстановки.
• Лекция 8. Транспозиция смежных элементов .
• Лекция 9. Цикловые классы подстановок и перестановок.
• Лекция 10. Факториальные методы перечисления перестановок .
• Лекция 11. Анализ факториальных методов перечисления перестановок.

Модуль 2. Алгоритмы комбинаторных вычислений на основе перестановок, разбиений и размещений конечных множеств.

• Лекция 1. Разбиения конечного множества.
• Лекция 2. Перестановки элементов мультимножества.
• Лекция 3. Системы различных представителей.
• Лекция 4. Перестановки с запретами.

Модуль 3. Алгоритмы комбинаторных вычислений на основе разбиений, композиций и размещений целых чисел.

• Лекция 1. Латинские прямоугольники и латинские квадраты.
• Лекция 2. Отрезки перестановок.
• Лекция 3. Разбиения целых чисел.
• Лекция 4. Композиции целых чисел.
• Лекция 5. Размещения различных элементов. Размещения с повторением.