Феофанова В.А., Воротников В.И. Дискретная математика. Часть 2

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