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

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

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

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

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

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

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

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

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

ДИСКРЕТНАЯ МАТЕМАТИКА, раздел математики, изучающий свойства дискретных структур, которые возникают как в самой математике, так и в её приложениях. При этом дискретными структурами называются объекты, для которых важнейшие характеристики принимают конечное или счётное число значений. К числу таких структур относятся, например, конечные группы, конечные графы, некоторые математические модели преобразователей информации, конечные автоматы, Тьюринга машины. Это примеры структур финитного (конечного) характера. Часть дискретной математики, изучающая их, иногда называется конечной математикой. Помимо финитных структур, дискретная математика изучает также дискретные бесконечные структуры (например, бесконечные алгебраические системы, бесконечные графы, бесконечные автоматы).

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

Реклама

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

Исторический очерк. Элементы дискретной математики возникли в глубокой древности; развиваясь параллельно с другими разделами математики, они являлись их составной частью. Типичными были задачи, связанные со свойствами целых чисел, позднее эти задачи привели к созданию теории чисел. Примеры таких задач: отыскание алгоритмов сложения и умножения натуральных чисел у древних египтян, вопросы делимости натуральных чисел и задачи суммирования в пифагорейской школе, а в более позднее время — вопросы, связанные с разрешимостью уравнений в целых числах. Этот этап развития дискретной математики связан с именами Диофанта, Евклида, Пифагора и Эратосфена. В 17-18 веках, в основном в связи с игровыми задачами, появились элементы комбинаторного анализа и дискретной теории вероятностей, а в связи с общими проблемами теории чисел, алгебры и геометрии в 18-19 веках возникли такие важнейшие понятия алгебры, как группа, поле, кольцо, определившие дальнейшее развитие и содержание алгебры и имевшие, по существу, дискретную природу. На протяжении 17-19 века развитие дискретной математики связано с именами Н. Абеля, Э. Варинга,   У. Гамильтона,   Э. Галуа, А. Кэли, Ж. Лагранжа, А. Лежандра, П. Ферма, Л. Эйлера. В 19-20 веках стремление к строгости математических рассуждений и анализ методов математики привели к выделению ещё одного раздела — математической логики. В это время проблемами дискретной математики занимались Л. Брауэр,   Дж. Буль,  Н.  Винер,  К.  Гёдель, Д. Гильберт, А. Чёрч, К. Шеннон. В создании российской школы дискретной математики участвовали И. М. Виноградов, А. Н. Колмогоров, О. Б. Лупанов и С. В. Яблонский.

Современные задачи дискретной математики. В 20 веке развитие дискретной математики определялось главным образом запросами практики. Возникла новая наука — кибернетика и её теоретическая часть — математическая кибернетика, изучающая математическими методами разнообразные проблемы, которые ставит перед кибернетикой практическая деятельность человека. Математическая кибернетика является поставщиком идей и задач дискретной математики. Так, прикладные вопросы, требующие больших вычислений, стимулировали появление и развитие численных методов решения задач, что привело к созданию вычислительной математики. Анализ понятий «вычислимость» и «алгоритм» привёл к созданию теории алгоритмов. Задачи хранения, обработки и передачи информации способствовали возникновению информации теории, теории кодирования и теоретической криптографии. Экономические задачи, задачи электротехники, равно как и внутренние проблемы математики, потребовали развития теории графов. Задачи описания работы и конструирования сложных управляющих систем составили предмет теории управляющих систем и теории автоматов.

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

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

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

Лит.: Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. 2-е изд. М., 1965; Кудрявцев В. Б. Функциональные системы. М., 1982; Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М., 1985; Гашков С. Б., Чубариков В. Н. Арифметика. Алгоритмы. Сложность вычислений.

2-е изд. М., 2000; Кнут Д. Искусство программирования: В 3 т. 3-е изд. М., 2000; Яблонский С. В. Введение в дискретную математику. 4-е изд. М., 2006.

В. Б. Кудрявцев.

Занятие со студентами вузов могут проходить в разных формах:

1. Небольшая серия из 2-6 занятий с целью компактно и быстро изучить отдельную тему (раздел) предмета, а иногда и весь предмет (ну это, скорее, для заочников); часто так делается непосредственно при подготовке к экзаменам, в сессию.
2. Регулярные занятия в течении семестра (или учебного года) по какому-либо предмету (или двум предметам) обычно одно занятие в неделю по 3 академических часа.
3. Интенсивная серия занятий ( по 2-3 занятия в неделю, а то и каждый день) в течении достаточно длительного времени (от 10 дней до 2-3 месяцев). Только так можно заниматься со студентами, приехавшими домой из другого города или страны и имеющим много свободного времени (ну и денег, конечно )

Вот перечень предметов по которым я провожу (могу проводить) занятия со студентами:

• Математический анализ
• Дифференциальные и разномастные уравнения
• Теория вероятности и математическая статистика
• Статистика (так называемая «общая теория статистики»)
• Эконометрика
• Дискретная математика
• Теория игр
• Методы оптимальных решений (еще недавно предмет назывался «Математическое программирование»)
• Финансовая математика
• Исследование операций
• Математическая экономика
• Актуарная математика
• Микроэкономика
• Логика
• Численные методы
• ФКП
• И другие, порой, довольно «экзотические» (ну то есть один ученик в 5-10 лет), например, методы принятия решений, тензоры, операционные исчисление, специальные функции и методы матфизики…

Стоимость занятий со студентами (по «неэкзотическми» предметам) у меня несколько ниже, чем со школьниками, ведь студентом быть (особенно в наше время) нелегко, и родители уже меньше помогают