Учебное пособие. Санкт-Петербургский государственный политехнический университет, 2008. - 192 с.
ISBN/ISSN:978-5-7422-1845-6.
В пособии рассматриваются основные понятия дискретной математики, которая имеет широкий спектр приложений, прежде всего в областях, связанных с информационными технологиями и компьютерами. Важнейшими приложениями дискретных структур в программировании являются компьютерная алгебра и вычислительная геометрия. Основу рассмотрений составляет теория алгоритмов. Именно этот круг тем покрывает данное пособие.
Работа выполнена в рамках реализации Инновационной образовательной программы Санкт-Петербургского государственного политехнического университета "Развитие политехнической системы подготовки кадров инновационной среде науки и высокотехнологичных производств Северо-Западного региона России".
Рекомендовано Учебно-методическим объединением по университетскому политехническому образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлениям подготовки и специальностям техники и технологии.Введение.
Множества и отношения.
Множества.
Алгебра подмножеств.
Представление множеств в программах.
Отношения.
Представление отношений в программах.
Функции.
Отношения эквивалентности.
Отношения порядка.
Выводы по главе 1.
Вычислимость и сложность.
Интуитивная вычислимость.
Рекурсия.
Машина с неограниченными регистрами.
Оператор минимизации.
Вычислимость по Тьюрингу.
Перечислимые и разрешимые множества.
Меры сложности.
Выводы по главе 2.
Алгебраические структуры.
Операции и алгебры.
Морфизмы.
Полугруппы и моноиды.
Группы.
Категории и функторы.
Кольца и поля.
Векторные пространства и модули.
Решетки.
Компьютерная алгебра.
Выводы по главе 3.
Комбинаторика.
Комбинаторные задачи.
Перестановки.
Биномиальные коэффициенты.
Разбиения.
Включения и исключения.
Формулы обращения.
Производящие функции.
Выводы по главе 4.
Библиографический список.
