История дискретной математики

Что такое дискретная математика?

Разберемся с терминами и определениями. Термин «дискретный» произошел от латинского слова discretus – прерывистый, состоящий из отдельных частей.

«Дискретная величина» — такая величина, между отдельными значениями которой заключеноконечное число других ее значений.

«Математика» происходит от греческого слова mathema – познание, наука. В настоящее время математика известна как наука о количественных отношениях и пространственных формах действительного мира.

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

Определение 1. Дискретная математика это описание процессов математическим языком, нахождение закономерностей между полученными данными и применение к ним известных правил для дальнейшего использования этой информации.

Определение 2. Ряд математических дисциплин, рассматривающих решение задач на дискретных структурах данных.

Определение 3. Дискретная математика — наука о структурах, связях и алгоритмах.

История дискретной математики

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

Еще в IV веке до н.э. Аристотель сформулировал основные законы логики: закон противоречия и закон исключенного третьего. Более 1000 лет назад персидский ученый аль-Хорезми описал Индийскую десятичную систему счисления и заменил пропущенную позицию цифрой «0». Он же определил правила вычислений, которые стали называть алгоритмами, вероятно от латинского произношения имени аль-Хорезми: Algorithmi.

Следующий этап развития дискретной математики был положен в XVIII веке: известный математик Леонард Эйлер своей знаменитой статьей ответил на вопрос: «Существует ли маршрут, проходящий по семи мостам, соединяющим два острова и берега реки Преголя в г. Кёнигсберге при условии, что по каждому мосту можно пройти только один раз». Рассуждения Л. Эйлера считаются началом теории графов, одного из разделов дискретной математики.

Длительное время эти знания использовались для разгадки головоломок. Дальнейшее развитие дискретной математики произошло спустя 100 лет после выхода знаменитой статьи Л. Эйлера вследствие открытия электрических сетей, молекул, а так же изучения кристаллов.

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

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

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

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

Дискретная (конечная) математика – это раздел математики, не связанный с понятиями предела, непрерывности и бесконечности.

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

В отличие от Д. м., классическая математика в основном занимается изучением свойств объектов непрерывного характера. Использование классической математики или Д. м. как аппаратов исследования связано с тем, какие задачи ставит перед собой исследователь и, в связи с этим, какую модель изучаемого явления он рассматривает, дискретную или непрерывную.

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

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

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

Основные разделы дискретной математики:

1. Теория множеств.

2. Алгебраические структуры.

3. Логика и булевы функции.

4. Комбинаторика.

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

6. Теория кодирования.

7. Логические исчисления и др.