Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Комсомольский-на-Амуре государственный технический университет»
Институт новых информационных технологий
Федерального государственного бюджетного образовательного учреждения
высшего профессионального образования
«Комсомольский-на-Амуре государственный технический университет»
А.А. Хусаинов н.Н. Михайлова дискретная математика
Утверждено в качестве учебного пособия
ученым советом Федерального государственного бюджетного образовательного
учреждения высшего профессионального образования
«Комсомольский-на-Амуре государственный технический университет»
Комсомольск-на-Амуре 2012
УДК 519.1
ББК
Х
Хусаинов А.А.
Х Дискретная математика: Учебное пособие / А.А. Хусаинов, Н.Н. Михайлова. – Комсомольск-на-Амуре: Изд-во ФГБОУ ВПО «КнАГТУ», 2012. – 90 с.
В пособии изложены основы дискретной математики: конечные множества и отношения, комбинаторный анализ, производящие функции и рекуррентные соотношения, теория графов, деревья, хроматические функции графов, функции Мебиуса на конечных частично упорядоченных множествах.
Предназначено для студентов направлений 230100 «Информатика и вычислительная техника» и 231000 «Программная инженерия» заочной формы обучения, обучающихся с использованием дистанционных технологий.
ББК
© Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Комсомольский-на-Амуре государственный технический университет», 2012
© Институт новых информационных технологий Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Комсомольский-на-Амуре государственный технический университет», 2012
Введение
Математика изучает множества с заданными на них математическими структурамив смысле Николы Бурбаки. В частности, объектами изучения являются группы, частично упорядоченные множества, топологические пространства. Поскольку числа, функции и отношения определяются как множества, то к математическим структурам относятся системы уравнений и неравенств, связывающих элементы множеств. В современной терминологии эти структуры чаще называютматематическими моделями.
Дискретная математикаизучает математические структуры с теми или иными условиями конечности. Как правило, эти условия конечности позволяют формализовать и наглядно формулировать проблемы дискретной математики. В то же время дискретная математика имеет много общего со всеми областями математики. Это превращает ее в достаточно общую область математики, многие методы решения которой понятны для широкого круга читателей.
Как правило, курс дискретной математики включает комбинаторный анализ и теорию графов, изложение которых невозможно без введения в теорию множеств. Кроме этих традиционных разделов добавляют алгебру логики и логику предикатов [12], [14], [17], конечные автоматы [10], [12], экстремальные задачи [6], элементы теории алгоритмов [4]. Мы предпочитаем этим разделам производящие функции и частично упорядоченные множества.
Наш курс состоит из разделов:
Множества и отношения.
Комбинаторный анализ.
Производящие функции.
Теория графов.
Частично упорядоченные множества.
К каждой главе прилагается список несложных упражнений. Более сложные задачи читатель может найти в [5], [7], [13].
В рамках дисциплины «Дискретная математика» выполняется одно расчетно-графическое задание и одна контрольная работа. Номер варианта определяется двумя последними цифрами номера зачётной книжки следующим образом:
если две последние цифры номера зачётной книжки находятся в диапазоне 00 – 29, то им соответствуют номера вариантов с 01 по 30, например, числу 23 соответствует вариант 24;
в других случаях к остатку от деления числа, состоящего из двух последних цифр номера зачётной книжки, на 30 прибавляется 1. Если последние цифры зачётной книжки, например, 56, то номер варианта – 27.
Отчёты по расчётно-графическому заданию и контрольной работе сдаются в письменном виде. После изучения курса сдаётся письменный экзамен. Экзаменационный билет составляется из экзаменационных вопросов и задач, приведённых в пособии.