2015-03-22
278
Выборки. Правила суммы и произведения. Перестановки, размещения, сочетания с повторениями и без повторений. Решение простых перечислительных задач. Декартовы произведения множеств. Бинарные отношения. Доказательство свойств декартова произведения, бинарных отношений функций. Отношения порядка. Элементарные функции и их свойства рефлексивности (иррефлексивности), симметричности, антисимметричности, транзитивности и эквивалентности.
Практические занятия № 6-7.
Производящие функции, экспоненциальные производящие функции, действия над ними. Производящие функции некоторых комбинаторных последовательностей. Метод рекуррентных соотношений. Решение линейных рекуррентных уравнений с постоянными коэффициентами. Формула включений и исключений. Применение принципа включений и исключений к решению некоторых комбинаторных задач. Формула включений и исключений. Разбор и решение задач практического содержания с использованием весов в формуле включений и исключений. Функция Эйлера и порождаемый ею класс комбинаторных задач.
Управление самостоятельной работой студента - 10 часов.
Правила суммы и произведения. Перестановки, размещения, сочетания с повторениями и без повторений. Бином Ньютона. Алгебраический подход изучения комбинаторных объектов и чисел. Метод рекуррентных соотношений и его применение при решении перечислительных задач. Решение линейных рекуррентных уравнений с постоянными коэффициентами. Числа Фибоначчи. Формула включений и исключений. Производящие функции, экспоненциальные производящие функции, действия над ними. Производящие функции некоторых комбинаторных последовательностей. Решение линейных рекуррентных уравнений с постоянными коэффициентами.
Разделы 3. Основы теории графов.
Теоретические занятия (лекции) – 8 часов.
Лекция 8. Информационная лекция.
Граф (орграф), его элементы. Виды графов (орграфов). Отношения между элементами графа (орграфа). Способы задания. Степень вершины. Изоморфизм. Связность. Маршруты в графах. Теоремы о маршрутах и циклах. Определение маршрутов, состоящих из фиксированного количества ребер. Упорядочение дуг и вершин орграфа, алгоритм Фалкерсона.
