Дискретная математика – область математики, занимающаяся изучением свойств структур конечного характера, которые возникают как внутри математики, так и в её приложениях. К числу таких конечных структур могут быть отнесены, например, конечные группы, конечные графы, а также некоторые математические модели преобразователей информации, конечные автоматы, машина Тьюринга и т. п.
Дискретная (конечная) математика – это раздел математики, не связанный с понятиями предела, непрерывности и бесконечности.
Дискретная математика имеет широкий спектр приложений, прежде всего в областях, связанных с информационными технологиями и компьютерами (компьютер – цифровая вычислительная машина, следовательно, имеет дискретный характер работы).
В отличие от Д. м., классическая математика в основном занимается изучением свойств объектов непрерывного характера. Использование классической математики или Д. м. как аппаратов исследования связано с тем, какие задачи ставит перед собой исследователь и, в связи с этим, какую модель изучаемого явления он рассматривает, дискретную или непрерывную.
|
|
Само деление математики на классическую и дискретную в значительной мере условно, поскольку, например, с одной стороны, происходит активная циркуляция идей и методов между ними, а с другой – часто возникает необходимость исследования моделей, обладающих как дискретными, так и непрерывными свойствами одновременно.
Следует отметить также, что в математике существуют подразделы, использующие средства дискретной математики для изучения непрерывных моделей, и, наоборот, часто средства и постановки задач классического анализа используются при исследовании дискретных структур.
Д. м. представляет собой важное направление в математике, в котором можно выделить характерные для Д. м. предмет исследования, методы и задачи, специфика которых обусловлена в первую очередь необходимостью отказа в Д. м. от основополагающих понятий классической математики - предела и непрерывности - и в связи с этим тем, что для многих задач Д. м. сильные средства классической математики оказываются, как правило, мало приемлемыми.
Наряду с выделением Д. м. путём указания её предмета можно также определить Д. м. посредством перечисления подразделов, составляющих Д. м. К ним в первую очередь должны быть отнесены комбинаторный анализ, графов теория, теория кодирования, теория функциональных системи некоторые другие.
Элементы Д. м. возникли в глубокой древности и, развиваясь параллельно с другими разделами математики, в значительной мере являлись их составной частью. Типичными для того периода были задачи, связанные со свойствами целых чисел и приведшие затем к созданию теории чисел. К их числу могут быть отнесены отыскания алгоритмов сложения и умножения натуральных чисел у древних египтян (2-е тыс. до н. э.), задачи о суммировании и вопросы делимости натуральных чисел в пифагорийской школе (6 в. до н. э.) и т. п. Позже (17-18 вв.), в основном в связи с игровыми задачами, появились элементы комбинаторного анализа и дискретной теории вероятностей (Б. Паскаль, П. Ферма и др.), а в связи с общими проблемами теории чисел, алгебры и геометрии (18-19 вв.) возникли важнейшие понятия алгебры, такие как группа, поле, кольцо и др. (Ж. Лагранж, Э. Галуа и др.), определившие развитие и содержание алгебры на много лет вперёд и имевшие по существу дискретную природу.
|
|
Стремление к строгости математических рассуждений и анализ рабочего инструмента математики – логики привели к выделению ещё одного важного раздела математики – математической логики (19-20 вв.). Однако наибольшего развития Д. м. достигла в связи с запросами практики, приведшими к появлению новой науки – кибернетики и её теоретической части – математической кибернетики (20 в.).
Дискретная математика, по существу, стала активно развиваться с начала XX века, когда стали изучаться возможности формализации математики и были получены фундаментальные результаты в области математической логики. Информатизация и компьютеризация общества во второй половине XX века в значительной степени стимулировала развитие дискретной математики.
Математическая кибернетика, непосредственно изучающая с позиций математики самые разнообразные проблемы, которые ставит перед кибернетикой практическая деятельность человека, является мощным поставщиком идей и задач для Д. м., вызывая к жизни целые новые направления в Д. м.
Так, прикладные вопросы, требующие большой числовой обработки, стимулировали появление сильных численных методов решения задач, оформившихся затем в вычислительную математику, а анализ понятий "вычислимость" и "алгоритм" привёл к созданию важного раздела математической логики - теории алгоритмов. Растущий поток информации и связанные с ним задачи хранения, обработки и передачи информации привели к возникновению теории кодирования; экономические задачи, задачи электротехники, равно как и внутренние задачи математики, потребовали разработки теории графов; задачи конструирования и описания работы сложных управляющих систем составили теорию функциональных систем и т. д. В то же время математическая кибернетика широко использует результаты Д. м. при решении своих задач.
Основные разделы дискретной математики:
1. Теория множеств.
2. Алгебраические структуры.
3. Логика и булевы функции.
4. Комбинаторика.
5. Теория графов.
6. Теория кодирования.
7. Логические исчисления и др.