Сафуанов И.С. Дискретная математика

Учебное пособие. — М.: Московский городской педагогический университет (МГПУ), 2022. — 172 с.Пособие включает соответствующие программе педагогических вузов разделы дискретной математики. Предназначено для студентов педагогических вузов, обучающихся по направлению подготовки 44.03.01 «Педагогическое образование» (уровень бакалавриата), профили «Математика» и «Информатика».Конечные суммы и рекуррентные соотношения.
Индукция и индуктивные определения.
Способы записи конечных сумм.
Некоторые методы суммирования.
Рекуррентные соотношения.
Числа Каталана.
Некоторые способы решения рекуррентных соотношений.
Решение линейных однородных рекуррентных соотношений с постоянными коэффициентами второго порядка в случае различных корней характеристического уравнения.
Решение линейных однородных рекуррентных соотношений с постоянными коэффициентами второго порядка в случае равных корней характеристического уравнения.
Формула для последовательности Фибоначчи.
Деление многочленов и степенные ряды.
Производящие функции.
Решение рекуррентных соотношений с помощью производящих функций.
Элементы комбинаторики.
Комбинаторные числа. Бином Ньютона.
Полиномиальная формула.
Треугольник Паскаля.
Формула включений – исключений.
Специальные числа. Числа Стирлинга.
Целочисленные функции.
Асимптотические методы.
Асимптотические методы (продолжение). О большое.
Элементы теории кодирования.
Коды и кодирование.
Двоичное кодирование. Блочные коды.
Матричное кодирование.
Групповые коды.
Декодирование. Таблицы декодирования.
Коды Хэмминга. Совершенные коды.
Элементы теории графов.
Основные понятия теории графов.
Виды и модификации графов.
Степени вершин.
Бинарные отношения и орграфы.
Матрицы смежности и матрицы инцидентности.
Маршруты и цепи.
Компоненты связности.
Графы и головоломки.
Эйлеровы графы.
Гамильтоновы графы.
Планарные графы.
Формула Эйлера для многоугольных графов.
Деревья и леса.
Описание деревьев.
Остовное дерево. Алгоритм Краскалла.
Двудольные графы.
Паросочетания. Теорема Холла о свадьбах.
Проблема четырех красок.
Теорема о пяти красках.
Конечные цепи Маркова.
Стохастические векторы и стохастические матрицы.
Неподвижные векторы стохастических матриц. Регулярные стохастические матрицы и регулярные цепи Маркова.
Литература.
Предметный указатель.