Учебное пособие. — М.: РУДН, 2012. — 78 с. — ISBN 978-5209-04949В пособии излагаются основы комбинаторики и комбинаторных алгоритмов.
Предназначено для студентов I, II курсов математических специальностей.
Подготовлено на кафедре систем телекоммуникаций.
Комбинаторика является частью науки дискретной математики. Дискретная математика состоит из следующих разделов: комбинаторика, математическая логика, общая теория графов, теория множеств и общая алгебра, теория алгоритмов, теория автоматов и теория кодирования.Содержание лекций (всего 14 лекций):
Введение в комбинаторику. Некоторые области применения задач комбинаторики. Прямое произведение множеств. Правило суммы и правило произведения для конечных множеств. Принцип Дирихле. Размещения без повторений, размещения с повторениями, сочетания без повторений, сочетания с повторениями, перестановки. МультимножествоОсновные тождества, связанные с числом сочетаний. Бином Ньютона. Следствия из теоремы о биноме Ньютона. Свойства биномиальных коэффициентовТреугольник Паскаля. Некоторые свойства треугольника Паскаля. Свойства шестиугольника для треугольника Паскаля. Разбиение множеств. Числа Стирлинга второго родаЧисла Белла. Числа Стирлинга первого рода. Беззнаковое число Стирлинга первого родаФормула включений и исключений. Задача о беспорядкахЧисло элементов, обладающих ровно k свойствами. Задача о встречах. Число элементов, обладающих не менее чем k свойствамиПолиномиальная теорема. Методы в комбинаторном анализе. Метод производящих функций. Задача о взвешиванииПроизводящие функции. Виды производящих функций. Свойства производящих функций. Таблица соответствий производящих функций и последовательностейДифференцирование и интегрирование производящих функций. Некоторые элементарные производящие функции. Бесконечно убывающая геометрическая прогрессия и последовательность из единицПримеры нахождения производящих функций для заданной последовательности. Примеры нахождения для последовательности производящих функцийРешение однородных рекуррентных соотношений. Общий метод решения рекуррентного соотношенияПоследовательность Фибоначчи. Примеры использования производящих функций. Вычисление корня числа через производящие функцииЧисла Каталана. Последовательность Каталана и производящая функция Каталана. Алгоритм расстановки скобокГенерирование комбинаторных объектов. Перестановки. Сочетания. Разбиение чисел. Подмножества множествЛитература.
Учебно-методический комплекс по дисциплине «Комбинаторные алгоритмы».
Место дисциплины в структуре ООП.
Цели и задачи дисциплины.
Требования к результатам освоения дисциплины.
Объем дисциплины и виды учебной работы.
Содержание дисциплины.© Российский университет дружбы народов, Издательство, 2012
© Э.Р. Зарипова, М.Г. Кокотчикова, 2012.
