Предисловие

Данная книга включает в себя многолетний опыт преподавания авторами различных разделов дискретной математики для таких специальностей, как прикладная математика и информатика, прикладная информатика, математические методы в экономике, экономика и управление на предприятии на факультетах «Кибернетика» и «Управление и экономика высоких технологий» НИЯУ МИФИ.

Данный курс знакомит с основами дискретной математики и методами их использования в информатике. Основная задача курса – формирование прочной теоретической основы, необходимой для дальнейшей работы. Разделы, рассмотренные в данной книге, включают в себя теорию множеств и бинарных отношений, математическую логику, основные понятия математических теорий и исчислений, теорию математических доказательств, основы комбинаторики, теорию графов и нечеткие модели. По каждому разделу приводятся задачи и вопросы, часть из них, самые простые, соответствует требованиям Интернет-экзамена, который был проведен в НИЯУ МИФИ весной 2009 г.

Для систематизации материала использованы также рекомендации по преподаванию программной инженерии и информатики в университетах,

приведенные в книге Software Engineering 2004: Curriculum Guidelines for Undergraduate Degree Programs in Software Engineering, Computing Curricula 2001: Computer Science. Именно благодаря этим рекомендациям появилась глава, посвященная построению математических доказательств.

Помимо этого, на содержание учебника большое влияние оказало появление в конце 2007 г. профессиональных стандартов в области информационных технологий (ИТ). Часть задач, используемых в данной книге, сформулированы в соответствии с требуемыми в стандартах компетенциями по ряду ИТ профессий.

Разные главы написаны разными авторами. Главы 1–5 написаны профессором А.И. Гусевой, главы 6–7 – доцентом А.Н. Тихомировой.

7

Глава 1. Теория множеств и бинарные отношения

1.1. Понятие компьютинга и дискретной математики

Компьютинг (computing) – это широкая область знаний, которая не может быть сведена к рамкам какой-либо из составляющих ее дисциплин. Основы компьютинга включают в себя основы информатики и математики, необходимые для проектирования и разработки программных продуктов. Данная область знаний включает в себя также знания о трансформации проекта в реализацию, используемых при этом средствах и о формальных методах создания программного обеспечения. Основываясь на математике и компьютинге, программная инженерия занимается разработкой систематических моделей и надежных методов производства высококачественного программного обеспечения, и данный подход распространяется на все уровни – от теории и принципов до реальной практики создания программного обеспечения, которая лучше всего заметна сторонним наблюдателям.

Программная инженерия посвящена систематическим, управляемым и эффективным методам создания высококачественного программного обеспечения. Поэтому особое внимание уделяется анализу и оценке, спецификации, проектированию и эволюции программного обеспечения. Кроме того, в рамки данной дисциплины попадают вопросы, связанные с управлением и качеством, новизной и творчеством, стандартами, индивидуальными навыками и командной работой, а также профессиональной деятельностью, которые играют жизненно важную роль в программной инженерии. Программная инженерия является такой формой инженерии, которая применяет принципы информатики (computer science) и математики для получения рентабельных решений в области программного обеспечения.

Программная инженерия как наука обладает рядом особенностей:

•основанием программной инженерии является информатика,

ане естественные науки;

8