Введение

Дискретная математика – это изучение математических структур, которые можно рассматривать как «дискретные» (аналогично дискретным переменным, имеющим биекцию с множеством натуральных чисел), а не «непрерывные» (аналогично непрерывным функциям). Объекты, изучаемые в дискретной математике, включают целые числа, графы и утверждения логики. В отличие от этого, дискретная математика исключает темы из «непрерывной математики», такие как действительные числа, математический анализ или евклидова геометрия. Дискретные объекты часто можно перечислить целыми числами; более формально, дискретная математика характеризуется как раздел математики, имеющий дело со счетными множествами (конечными множествами или множествами с той же кардинальностью, что и множество натуральных чисел). Однако точного определения термина «дискретная математика» не существует. Множество объектов, изучаемых в дискретной математике, может быть конечным или бесконечным. Термин «конечная математика» иногда применяется к частям области дискретной математики, которые имеют дело с конечными множествами, особенно в тех областях, которые актуальны для бизнеса. Исследования в области дискретной математики возросли во второй половине двадцатого века отчасти благодаря развитию цифровых компьютеров, которые работают в «дискретных» шагах и хранят данные в «дискретных» битах. Концепции и обозначения из дискретной математики полезны для изучения и описания объектов и задач в различных областях информатики, таких как компьютерные алгоритмы, языки программирования, криптография, автоматическое доказательство теорем и разработка программного обеспечения. В свою очередь, компьютерные реализации важны для применения идей из дискретной математики к реальным задачам. Хотя основными объектами изучения в дискретной математике являются дискретные объекты, аналитические методы из «непрерывной» математики также часто используются. В университетских учебных планах дискретная математика появилась в 1980-х годах, первоначально как поддерживающий курс для информатики; в то время её содержание было несколько разрозненным. Впоследствии учебный план, в сочетании с усилиями ACM и MAA, превратился в курс, который в основном предназначен для развития математической зрелости у студентов первого курса; поэтому в настоящее время он является обязательным требованием для математических специальностей в некоторых университетах. Появились также некоторые учебники по дискретной математике для старших классов школы. На этом уровне дискретная математика иногда рассматривается как подготовительный курс, подобно курсу прекалькулуса. Премия Фулкерсона присуждается за выдающиеся работы в области дискретной математики.

Теоретическая информатика

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

Теория информации

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

Логика

Логика – это изучение принципов корректного рассуждения и вывода, а также непротиворечивости, обоснованности и полноты. Например, в большинстве систем логики (но не в интуиционистской логике) закон Пирса (((P→Q)→P)→P) является теоремой. Для классической логики его можно легко проверить с помощью таблицы истинности. Изучение математических доказательств особенно важно в логике и привело к развитию автоматического доказательства теорем и формальной верификации программного обеспечения. Логические формулы и доказательства являются дискретными структурами, образующими конечные деревья или, в более общем случае, направленные ациклические графы (при этом каждый шаг вывода объединяет одну или несколько исходных ветвей для получения единственного заключения). Множество значений истинности логических формул обычно конечно, как правило, ограничивается двумя значениями: истиной и ложью, но логика может быть и непрерывнозначной, например, нечёткая логика. Также изучались такие понятия, как бесконечные деревья доказательств или бесконечные деревья вывода, например, в бесконечной логике.

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

Теория множеств — это раздел математики, изучающий множества, которые представляют собой коллекции объектов, например, {синий, белый, красный} или (бесконечное) множество всех простых чисел. Частично упорядоченные множества и множества с другими отношениями находят применение в различных областях. В дискретной математике основное внимание уделяется счетным множествам (включая конечные множества). Начало теории множеств как самостоятельной отрасли математики обычно связывают с работами Георга Кантора, который разделил бесконечные множества на различные типы, исходя из изучения тригонометрических рядов, а дальнейшее развитие теории бесконечных множеств выходит за рамки дискретной математики. Фактически, современные исследования в описательной теории множеств широко используют традиционную непрерывную математику.

Комбинаторная теория

Комбинаторика изучает способы объединения и упорядочивания дискретных структур. Энумеративная комбинаторика сосредоточена на подсчете числа определенных комбинаторных объектов, например, "двенадцатикратный путь" предоставляет единую основу для подсчета перестановок, сочетаний и разбиений. Аналитическая комбинаторика занимается перечислением (то есть определением числа) комбинаторных структур с использованием инструментов комплексного анализа и теории вероятностей. В отличие от энумеративной комбинаторики, которая использует явные комбинаторные формулы и производящие функции для описания результатов, аналитическая комбинаторика направлена на получение асимптотических формул. Топологическая комбинаторика изучает применение методов топологии и алгебраической/комбинаторной топологии в комбинаторике. Теория конструкций занимается изучением комбинаторных конструкций – коллекций подмножеств с определенными свойствами пересечения. Теория разбиений изучает различные задачи перечисления и асимптотики, связанные с разбиениями целых чисел, и тесно связана с q-рядами, специальными функциями и ортогональными многочленами. Изначально являясь частью теории чисел и анализа, теория разбиений теперь рассматривается как часть комбинаторики или самостоятельная область. Теория порядка изучает частично упорядоченные множества, как конечные, так и бесконечные.

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

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

Теория чисел

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

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

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

Дискретные аналоги непрерывной математики

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

Расчет конечных различий, дискретный анализ и дискретный исчисление

В дискретном исчислении и исчислении конечных разностей функция, определенная на интервале целых чисел, обычно называется последовательностью. Последовательность может быть конечной последовательностью из источника данных или бесконечной последовательностью из дискретной динамической системы. Такая дискретная функция может быть определена явно списком (если ее область определения конечна), формулой для общего члена или неявно отношением рекурренции или разностным уравнением. Разностные уравнения аналогичны дифференциальным уравнениям, но заменяют дифференцирование вычислением разности между соседними членами; они могут использоваться для аппроксимации дифференциальных уравнений или (чаще) изучаются как самостоятельный объект. Многие вопросы и методы, относящиеся к дифференциальным уравнениям, имеют аналоги в теории разностных уравнений. Например, там, где в гармоническом анализе для изучения непрерывных функций или аналоговых сигналов используются интегральные преобразования, для дискретных функций или цифровых сигналов существуют дискретные преобразования. Помимо дискретных метрических пространств, существуют более общие дискретные топологические пространства, конечные метрические пространства и конечные топологические пространства. Исчисление по шкалам времени объединяет теорию разностных уравнений с теорией дифференциальных уравнений и находит применение в областях, требующих одновременного моделирования дискретных и непрерывных данных. Другой подход к моделированию подобных ситуаций – понятие гибридных динамических систем.

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

Дискретная геометрия и комбинаторная геометрия изучают комбинаторные свойства дискретных множеств геометрических объектов. Давняя тема в дискретной геометрии – это мощение плоскости. В алгебраической геометрии понятие кривой можно расширить на дискретные геометрии, рассматривая спектры многочленных колец над конечными полями как модели аффинных пространств над этими полями, а подмногообразия или спектры других колец – как кривые, лежащие в этом пространстве. Хотя пространство, в котором появляются кривые, содержит конечное число точек, сами кривые представляют собой не просто наборы точек, а аналоги кривых в непрерывных пространствах. Например, каждую точку вида для поля можно изучать либо как , как точку, либо как спектр локального кольца в (x c), как точку вместе с окрестностью вокруг неё. Алгебраические многообразия также имеют чётко определённое понятие касательного пространства, называемого касательным пространством Зариски, что позволяет применять многие методы исчисления даже в конечных условиях.

Дискретное моделирование

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

Вызовы

История дискретной математики связана с рядом сложных задач, которые привлекли внимание к различным областям этой науки. В теории графов значительная часть исследований была мотивирована попытками доказать теорему о четырёх красках, впервые сформулированную в 1852 году, но доказанную лишь в 1976 году (Кеннетом Аппелем и Вольфгангом Хакеном с использованием существенной помощи компьютера). Холодная война способствовала сохранению важности криптографии, и в последующие десятилетия были сделаны фундаментальные прорывы, такие как криптография с открытым ключом. Телекоммуникационная индустрия также стимулировала развитие дискретной математики, особенно в теории графов и теории информации. Формальная верификация логических утверждений стала необходимой при разработке программного обеспечения для систем, критичных к безопасности, и эта потребность послужила стимулом для развития автоматического доказательства теорем. Вычислительная геометрия играет важную роль в компьютерной графике, используемой в современных видеоиграх и системах автоматизированного проектирования. Несколько областей дискретной математики, в частности теоретическая информатика, теория графов и комбинаторика, имеют важное значение для решения сложных задач биоинформатики, связанных с пониманием эволюционного древа жизни. В настоящее время одной из самых известных нерешённых проблем в теоретической информатике является проблема P = NP, которая касается взаимосвязи между классами сложности P и NP. Институт математики Клэя объявил приз в 1 миллион долларов США за первое корректное доказательство, а также призы за решение ещё шести математических задач.