Дискретная математика

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

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

Введение в дискретную математику

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

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

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

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

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

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

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