Введение. Предмет дискретной математики

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

ДМ - самостоятельное направление современной математики. ДМ изучает математические модели объектов, процессов, зависимостей, существующих в реальном мире, с которыми имеют дело в технике, информатике и других областях знаний.

Дискретная и непрерывная математика взаимно дополняют друг друга. Понятия и методы одной часто используются в другой. Один и тот

|же объект может рассматриваться с двух точек зрения и в зависимости от этого выбирается непрерывная или дискретная модель. Сегодня ДМ является важным звеном математического образования. Умение проводить анализ, композицию и декомпозицию информационных комплексов и информационных процессов -обязательное квалификационное требование к специалистам в области информатики.

Знание дискретной математики необходимо для создания и эксплуатации интегрированных систем обработки информации и их компонент (математического обеспечения, пакетов прикладных программ, распределенных банков данных, сетей передачи данных, систем с разделением ресурсов и распределенной обработкой информации).

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

Еще в доньютоновский период появились простейшие понятия комбинаторики (П.Ферма, Б.Паскаль, Франция, XVIII в.). Комбинаторика возникла как основа дискретной теории вероятностей в связи сисследованиями в области азартных игр. Л.Эйлер в середине XVIII в. закладывает основы теории графов; в середине XIX в. Дж. Буль, опираясь на некоторые идеи Г.Лейбница, придумывает свою "универсальную алгебру" в продолжение наметившегося еще в средние века стремления к формализации аристотелевой логики. Конец XIX в., характеризующийся, с одной стороны, обобщающе-синтетическим подходом к различным разделам математики, а с другой - стремлением к строгости математических обоснований, дает толчок к созданию и быстрому расцвету математической логики.

Основным поставщиком задач и идей для ДМ в XX в. становится кибернетика, а универсальным вычислительным средством - ЭВМ Задачи анализа и конструирования сложных систем послужили стимулом для разработки теории графов; задачи хранения, обработки и передачи информации привели к теории кодирования (дискретной теории информации); задачи оптимизации вызвали появление дискретного программирования (методы исследования и решения экстремальных задач на конечных множествах); исследование основных понятий вычислительной математики - вычислимости и алгоритма -стимулировало появление теории алгоритмов и теории сложности.

* * *

Напомним некоторые основные понятия базового курса [10]. Множество - это совокупность объектов, называемых