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

Дискретная математика - область математики, изучающая дискретные математические объекты и структуры.

Важнейшие примеры дискретных математических объектов: натуральный ряд чисел; конечное множество элементов произвольной природы; функция (отображение) из конечного множества в конечное множество; слово (последовательность символов) в конечном алфавите; формальный язык (множество слов в конечном алфавите); конечный граф и другие.

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

В обычном понимании дискретность и непрерывность являются оппозитными (противоположными, взаимно дополнительными) понятиями. Следует, однако, подчеркнуть, что деление математики на "непрерывную" и "дискретную" весьма условно; математика едина: вся она пронизана глубокими аналогиями, сходные идеи и конструкции одинаково успешно работают в различных ее разделах.

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

↑История развития

Возникновение дискретной математики относят к глубокой древности. С незапамятных времен известны комбинаторно-логические задачи, решение которых связано с перебором комбинаций дискретных объектов и логическим анализом возникающих вариантов. Некоторые из них сохранились до нашего времени в занимательной математике в виде задач-головоломок или салонных игр (простейшие примеры: широко известные задачи о волке, козе и капусте, о Ханойской башне и другие). Когда число возникающих вариантов велико, а перебор сократить не удается, решение задачи становится затруднительным.

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

Широко известны изобретенные в древности различные системы представления чисел, включая позиционную, и связанные с ними алгоритмы выполнения арифметических операций, решения уравнений и т.д. В древнем мире и средневековье (да и в совсем недалекие от нас времена) повсеместно были распостранены дискретные вычислительные приспособления: абак, различные виды счетов. Кстати, английское слово "calculation" - "вычисление", как и русское "калькуляция", "калькулятор", восходят к латинскому слову "calculus" - "камешек" (имеются в виду камешки, применявшиеся для счета). В странах юго-восточной Азии (Китае, Малайзии, Японии и других) счеты до сих пор считают незаменимым средством для обучения детей арифметике и регулярно проводят международные соревнования на эту тему среди школьников. 

Начало современного этапа в развитии дискретной математики относят к XVII веку и связывают с появлением работ Л. Эйлера в области комбинаторного анализа и теории графов, Я. Бернулли по комбинаторной теории вероятностей. Большую роль в развитии идеологии дискретной математики сыграл Г. В. Лейбниц. В XIX веке в области дискретной математики работали известные математики: Ж. Л. Лагранж, А. Кэли, Дж. Буль, К. Жордан и многие другие.

В начале XX века значительное развитие получили "предтечи" современной дискретной математики: дескриптивная теория множеств, комбинаторная топология, общая алгебра.

Большое значение для осознания роли дискретной математики в науке XX века имело возникновение и распостранение в современном естествознании представлений о дискретном характере окружающей нас реальности (атомно-молекулярная теория, квантовая и статистическая физика). Существенное влияние на развитие дискретной математики на этом этапе оказали исследования в области оснований математики, в частности, финитистские установки А. Пуанкаре и Д. Гильберта (грубо говоря, стремление считать «законными» лишь такие математические построения, которые сводятся к выполнению в конечное число шагов процедур над конечными объектами), работы Э.Л. Поста, А.М.Тьюринга и других по теории алгоритмов, исследования Э.Л.Поста в области выразимости функций алгебры логики.

Бурное развитие дискретной математики во второй половине XX века связывают с произошедшей в те годы (и продолжающейся поныне) "цифровой революцией" в телекоммуникационной и вычислительной технике. Дискретная математика стала основой проектирования и применения многочисленных цифровых электронных устройств. Первые применения дискретной математики в этой области связаны с именами В. А. Котельникова, К. Э. Шеннона, В.И. Шестакова. Возникновение в рамках кибернетики математической теории управляющих систем привело к развитию целых новых разделов дискретной математики: теории сложности, теории тестов, теории надежности схем, теории автоматов и других. Существенный вклад в дискретную математику на этом этапе был сделан Дж. фон Нейманом, А.А. Ляпуновым, С.В. Яблонским, О.Б. Лупановым.

↑Методы, задачи и разделы дискретной математики

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

В современном комбинаторном анализе помимо традиционных перечислительных задач большое внимание уделяется изучению комбинаторных конфигураций (дизайнов), алгоритмам решения комбинаторных задач, комбинаторной оптимизации, вероятностной комбинаторике. В теории графов развились новые разделы: экстремальная теория графов, теория матроидов, теория потоков в сетях и другие. В 1976 году К. Аппелем и В. Хакеном было предложено «машинное» решение известной проблемы четырех красок, вызвавшее ожесточенные споры о правомерности использования вычислительных машин для доказательства математических утверждений.

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

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

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

К числу наиболее известных нерешенных задач дискретной математики относится ряд проблем теории сложности, касающихся умножения двоичных чисел, умножения матриц, дискретного логарифмирования, распознавания изоморфизма графов; особо важное значение придается проблеме получения нелинейных нижних оценок сложности булевых функций и проблеме равенства классов P и NP в теории сводимости комбинаторных задач (проблема P=NP?).

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

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

↑Рекомендуемая литература

1. Дискретная математика и математические вопросы кибернетики. Т. I. / Под общ. ред. С. В. Яблонского и О. Б. Лупанова. М.: Наука, 1974.

2. Мак-Вильямс Ф., Слоэн Н. Теория кодов, исправляющих ошибки. М.: Советское радио, 1977.

3. Робертс Ф. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986.

4. Саати Т. Целочисленные методы оптимизации и связанные с ними экстремальные проблемы. М.: Мир, 1973.

5. Яблонский С. В. Введение в дискретную математику. М.: Наука, 1979.