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