ВВЕДЕНИЕ. Утверждено в качестве учебного пособия

А.А. Хусаинов

Н.Н. Михайлова

ДИСКРЕТНАЯ МАТЕМАТИКА

Утверждено в качестве учебного пособия

ученым советом Федерального государственного бюджетного образовательного

учреждения высшего профессионального образования

«Комсомольский-на-Амуре государственный технический университет»

Комсомольск-на-Амуре 2012

УДК 519.1

ББК

Х

Хусаинов А.А.

Х Дискретная математика: Учебное пособие / А.А. Хусаинов, Н.Н. Михайлова. – Комсомольск-на-Амуре: Изд-во ФГБОУ ВПО «КнАГТУ», 2012. – 90 с.

В пособии изложены основы дискретной математики: конечные множества и отношения, комбинаторный анализ, производящие функции и рекуррентные соотношения, теория графов, деревья, хроматические функции графов, функции Мебиуса на конечных частично упорядоченных множествах.

Предназначено для студентов направлений 230100 «Информатика и вычислительная техника» и 231000 «Программная инженерия» заочной формы обучения, обучающихся с использованием дистанционных технологий.

ББК

© Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Комсомольский-на-Амуре государственный технический университет», 2012

© Институт новых информационных технологий Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Комсомольский-на-Амуре государственный технический университет», 2012

ВВЕДЕНИЕ

Математика изучает множества с заданными на них математическими структурами в смысле Николы Бурбаки. В частности, объектами изучения являются группы, частично упорядоченные множества, топологические пространства. Поскольку числа, функции и отношения определяются как множества, то к математическим структурам относятся системы уравнений и неравенств, связывающих элементы множеств. В современной терминологии эти структуры чаще называют математическими моделями.

Дискретная математика изучает математические структуры с теми или иными условиями конечности. Как правило, эти условия конечности позволяют формализовать и наглядно формулировать проблемы дискретной математики. В то же время дискретная математика имеет много общего со всеми областями математики. Это превращает ее в достаточно общую область математики, многие методы решения которой понятны для широкого круга читателей.

Как правило, курс дискретной математики включает комбинаторный анализ и теорию графов, изложение которых невозможно без введения в теорию множеств. Кроме этих традиционных разделов добавляют алгебру логики и логику предикатов [12], [14], [17], конечные автоматы [10], [12], экстремальные задачи [6], элементы теории алгоритмов [4]. Мы предпочитаем этим разделам производящие функции и частично упорядоченные множества.

Наш курс состоит из разделов:

1. Множества и отношения.

2. Комбинаторный анализ.

3. Производящие функции.

4. Теория графов.

5. Частично упорядоченные множества.

К каждой главе прилагается список несложных упражнений. Более сложные задачи читатель может найти в [5], [7], [13].

В рамках дисциплины «Дискретная математика» выполняется одно расчетно-графическое задание и одна контрольная работа. Номер варианта определяется двумя последними цифрами номера зачётной книжки следующим образом:

если две последние цифры номера зачётной книжки находятся в диапазоне 00 – 29, то им соответствуют номера вариантов с 01 по 30, например, числу 23 соответствует вариант 24;

в других случаях к остатку от деления числа, состоящего из двух последних цифр номера зачётной книжки, на 30 прибавляется 1. Если последние цифры зачётной книжки, например, 56, то номер варианта – 27.

Отчёты по расчётно-графическому заданию и контрольной работе сдаются в письменном виде. После изучения курса сдаётся письменный экзамен. Экзаменационный билет составляется из экзаменационных вопросов и задач, приведённых в пособии.

Поиск по сайту: