Дискретная математика — это изучение математических структур , которые можно считать «дискретными» (аналогично дискретным переменным , имеющим биекцию с множеством натуральных чисел ), а не «непрерывными» (аналогично непрерывным функциям ). Объекты, изучаемые в дискретной математике, включают целые числа , графики и утверждения в логике . [1] [2] [3] Напротив, дискретная математика исключает темы в «непрерывной математике», такие как действительные числа , исчисление или евклидова геометрия . Дискретные объекты часто можно перечислить целыми числами ; более формально дискретная математика была охарактеризована как раздел математики, имеющий дело со счетными множествами [4] (конечные множества или множества с той же мощностью, что и натуральные числа). Однако точного определения термина «дискретная математика» не существует. [5]
Набор объектов, изучаемых в дискретной математике, может быть конечным или бесконечным. Термин «конечная математика» иногда применяется к частям области дискретной математики, которые имеют дело с конечными множествами, в частности, к областям, имеющим отношение к бизнесу.
Исследования в области дискретной математики возросли во второй половине двадцатого века отчасти из-за развития цифровых компьютеров , которые работают в "дискретных" шагах и хранят данные в "дискретных" битах. Концепции и обозначения из дискретной математики полезны при изучении и описании объектов и проблем в таких областях компьютерной науки , как компьютерные алгоритмы , языки программирования , криптография , автоматическое доказательство теорем и разработка программного обеспечения . И наоборот, компьютерные реализации важны для применения идей из дискретной математики к проблемам реального мира.
Хотя основными объектами изучения дискретной математики являются дискретные объекты, также часто применяются аналитические методы из «непрерывной» математики.
В университетских учебных программах дискретная математика появилась в 1980-х годах, изначально как вспомогательный курс по информатике; в то время ее содержание было несколько бессистемным. Впоследствии учебная программа была разработана совместно с усилиями ACM и MAA в курс, который в основном предназначен для развития математической зрелости у студентов первого курса; поэтому в настоящее время это также является предварительным условием для студентов-математиков в некоторых университетах. [6] [7] Также появились некоторые учебники по дискретной математике для старших классов. [8] На этом уровне дискретная математика иногда рассматривается как подготовительный курс, как в этом отношении предварительный исчисление . [9]
Премия Фулкерсона присуждается за выдающиеся работы в области дискретной математики.
Теоретическая информатика включает области дискретной математики, относящиеся к вычислениям. Она в значительной степени опирается на теорию графов и математическую логику . В теоретическую информатику входит изучение алгоритмов и структур данных. Вычислимость изучает то, что может быть вычислено в принципе, и тесно связана с логикой, в то время как сложность изучает время, пространство и другие ресурсы, занимаемые вычислениями. Теория автоматов и теория формального языка тесно связаны с вычислимостью. Сети Петри и алгебры процессов используются для моделирования компьютерных систем, а методы из дискретной математики используются при анализе электронных схем СБИС . Вычислительная геометрия применяет алгоритмы к геометрическим задачам и представлениям геометрических объектов, в то время как анализ компьютерных изображений применяет их к представлениям изображений. Теоретическая информатика также включает изучение различных непрерывных вычислительных тем.
Теория информации включает в себя квантификацию информации . Тесно связана с ней теория кодирования , которая используется для разработки эффективных и надежных методов передачи и хранения данных. Теория информации также включает в себя непрерывные темы, такие как: аналоговые сигналы , аналоговое кодирование , аналоговое шифрование .
Логика — это изучение принципов обоснованного рассуждения и вывода , а также последовательности , обоснованности и полноты . Например, в большинстве систем логики (но не в интуиционистской логике ) закон Пирса ((( P → Q )→ P )→ P ) является теоремой. Для классической логики его можно легко проверить с помощью таблицы истинности . Изучение математического доказательства особенно важно в логике и накопилось до автоматизированного доказательства теорем и формальной проверки программного обеспечения.
Логические формулы являются дискретными структурами, как и доказательства , которые образуют конечные деревья [10] или, в более общем смысле, направленные ациклические графовые структуры [11] [12] (при этом каждый шаг вывода объединяет одну или несколько ветвей предпосылок , чтобы дать одно заключение). Значения истинности логических формул обычно образуют конечный набор, как правило, ограниченный двумя значениями: истина и ложь , но логика также может быть непрерывно-значной, например, нечеткая логика . Также были изучены такие концепции, как бесконечные деревья доказательств или бесконечные деревья вывода, [13] например, бесконечная логика .
Теория множеств — это раздел математики, изучающий множества , которые представляют собой наборы объектов, например {синий, белый, красный} или (бесконечное) множество всех простых чисел . Частично упорядоченные множества и множества с другими отношениями имеют приложения в нескольких областях.
В дискретной математике основное внимание уделяется счетным множествам (включая конечные множества ). Начало теории множеств как раздела математики обычно отмечается работой Георга Кантора , различающей различные виды бесконечных множеств , мотивированной изучением тригонометрических рядов, а дальнейшее развитие теории бесконечных множеств выходит за рамки дискретной математики. Действительно, современная работа в области описательной теории множеств широко использует традиционную непрерывную математику.
Комбинаторика изучает способы, которыми дискретные структуры могут быть объединены или организованы. Перечислительная комбинаторика концентрируется на подсчете количества определенных комбинаторных объектов - например, двенадцатикратный способ обеспечивает единую структуру для подсчета перестановок , комбинаций и разделов . Аналитическая комбинаторика занимается перечислением (т. е. определением количества) комбинаторных структур с использованием инструментов из комплексного анализа и теории вероятностей . В отличие от перечислительной комбинаторики, которая использует явные комбинаторные формулы и производящие функции для описания результатов, аналитическая комбинаторика нацелена на получение асимптотических формул . Топологическая комбинаторика занимается использованием методов из топологии и алгебраической топологии / комбинаторной топологии в комбинаторике . Теория дизайна - это изучение комбинаторных дизайнов , которые представляют собой наборы подмножеств с определенными свойствами пересечения . Теория разбиений изучает различные перечисления и асимптотические проблемы, связанные с целочисленными разбиениями , и тесно связана с q-рядами , специальными функциями и ортогональными многочленами . Первоначально являясь частью теории чисел и анализа , теория разбиений теперь считается частью комбинаторики или независимой областью. Теория порядка изучает частично упорядоченные множества , как конечные, так и бесконечные.
Теория графов, изучение графов и сетей , часто считается частью комбинаторики, но она стала достаточно большой и достаточно обособленной, со своим собственным типом проблем, чтобы рассматриваться как самостоятельный предмет. [14] Графы являются одним из основных объектов изучения в дискретной математике. Они являются одними из самых распространенных моделей как естественных, так и созданных человеком структур. Они могут моделировать многие типы отношений и динамики процессов в физических, биологических и социальных системах. В информатике они могут представлять сети связи, организацию данных, вычислительные устройства, поток вычислений и т. д. В математике они полезны в геометрии и некоторых частях топологии , например, теории узлов . Алгебраическая теория графов тесно связана с теорией групп, а топологическая теория графов тесно связана с топологией . Существуют также непрерывные графы ; однако по большей части исследования в области теории графов относятся к области дискретной математики.
Теория чисел занимается свойствами чисел в целом, в частности целых чисел . Она имеет приложения к криптографии и криптоанализу , в частности, в отношении модульной арифметики , диофантовых уравнений , линейных и квадратичных сравнений, простых чисел и проверки простоты . Другие дискретные аспекты теории чисел включают геометрию чисел . В аналитической теории чисел также используются методы из непрерывной математики. Темы, выходящие за рамки дискретных объектов, включают трансцендентные числа , диофантовы приближения , p-адический анализ и функциональные поля .
Алгебраические структуры встречаются как в дискретных, так и в непрерывных примерах. Дискретные алгебры включают: Булеву алгебру, используемую в логических вентилях и программировании; реляционную алгебру, используемую в базах данных ; дискретные и конечные версии групп , колец и полей важны в алгебраической теории кодирования ; дискретные полугруппы и моноиды появляются в теории формальных языков .
В непрерывной математике существует множество концепций и теорий, которые имеют дискретные версии, такие как дискретное исчисление , дискретные преобразования Фурье , дискретная геометрия , дискретные логарифмы , дискретная дифференциальная геометрия , дискретное внешнее исчисление , дискретная теория Морса , дискретная оптимизация , дискретная теория вероятностей , дискретное распределение вероятностей , разностные уравнения , дискретные динамические системы и дискретные векторные меры .
В дискретном исчислении и исчислении конечных разностей функция , определенная на интервале целых чисел , обычно называется последовательностью . Последовательность может быть конечной последовательностью из источника данных или бесконечной последовательностью из дискретной динамической системы . Такая дискретная функция может быть определена явно списком (если ее область определения конечна), или формулой для ее общего члена, или она может быть задана неявно рекуррентным соотношением или разностным уравнением . Разностные уравнения похожи на дифференциальные уравнения , но заменяют дифференцирование взятием разности между соседними членами; их можно использовать для аппроксимации дифференциальных уравнений или (чаще) изучать сами по себе. Многие вопросы и методы, касающиеся дифференциальных уравнений, имеют аналоги для разностных уравнений. Например, там, где есть интегральные преобразования в гармоническом анализе для изучения непрерывных функций или аналоговых сигналов, есть дискретные преобразования для дискретных функций или цифровых сигналов. Помимо дискретных метрических пространств , существуют более общие дискретные топологические пространства , конечные метрические пространства , конечные топологические пространства .
Исчисление шкалы времени представляет собой объединение теории разностных уравнений с теорией дифференциальных уравнений , которая имеет приложения к областям, требующим одновременного моделирования дискретных и непрерывных данных. Другим способом моделирования такой ситуации является понятие гибридных динамических систем .
Дискретная геометрия и комбинаторная геометрия изучают комбинаторные свойства дискретных наборов геометрических объектов. Долговременной темой в дискретной геометрии является замощение плоскости .
В алгебраической геометрии понятие кривой может быть расширено до дискретных геометрий, если взять спектры полиномиальных колец над конечными полями в качестве моделей аффинных пространств над этим полем и позволить подмногообразиям или спектрам других колец предоставить кривые, которые лежат в этом пространстве. Хотя пространство, в котором появляются кривые, имеет конечное число точек, кривые являются не столько множествами точек, сколько аналогами кривых в непрерывных условиях. Например, каждая точка формы для поля может быть изучена либо как , точка, либо как спектр локального кольца в (xc) , точка вместе с окрестностью вокруг нее. Алгебраические многообразия также имеют четко определенное понятие касательного пространства, называемого касательным пространством Зарисского , что делает многие особенности исчисления применимыми даже в конечных условиях.
В прикладной математике дискретное моделирование является дискретным аналогом непрерывного моделирования . В дискретном моделировании дискретные формулы подгоняются под данные . Распространенным методом в этой форме моделирования является использование рекуррентного соотношения . Дискретизация касается процесса перевода непрерывных моделей и уравнений в дискретные аналоги, часто в целях упрощения вычислений за счет использования приближений. Численный анализ дает важный пример.
История дискретной математики включала ряд сложных проблем, которые привлекли внимание в различных областях этой области. В теории графов многие исследования были мотивированы попытками доказать теорему о четырех цветах , впервые сформулированную в 1852 году, но не доказанную до 1976 года (Кеннетом Аппелем и Вольфгангом Хакеном с использованием существенной компьютерной помощи). [15]
В логике второй проблемой в списке открытых проблем Давида Гильберта , представленном в 1900 году, было доказательство того, что аксиомы арифметики непротиворечивы . Вторая теорема Гёделя о неполноте , доказанная в 1931 году, показала, что это невозможно — по крайней мере, в рамках самой арифметики. Десятой проблемой Гильберта было определить, имеет ли заданное полиномиальное диофантово уравнение с целыми коэффициентами целочисленное решение. В 1970 году Юрий Матиясевич доказал, что это невозможно .
Необходимость взлома немецких кодов во время Второй мировой войны привела к достижениям в криптографии и теоретической информатике , при этом первый программируемый цифровой электронный компьютер был разработан в английском Блетчли-парке под руководством Алана Тьюринга и его основополагающей работы «О вычислимых числах». [16] Холодная война означала, что криптография оставалась важной, и в последующие десятилетия были разработаны такие фундаментальные достижения, как криптография с открытым ключом . Телекоммуникационная отрасль также мотивировала достижения в дискретной математике, особенно в теории графов и теории информации . Формальная проверка утверждений в логике была необходима для разработки программного обеспечения критически важных для безопасности систем , и достижения в области автоматического доказательства теорем были обусловлены этой потребностью.
Вычислительная геометрия стала важной частью компьютерной графики, включенной в современные видеоигры и средства автоматизированного проектирования .
Несколько областей дискретной математики, в частности теоретическая информатика, теория графов и комбинаторика , играют важную роль в решении сложных проблем биоинформатики , связанных с пониманием древа жизни . [17]
В настоящее время одной из самых известных открытых проблем в теоретической информатике является проблема P = NP , которая включает в себя связь между классами сложности P и NP . Математический институт Клэя предложил приз в размере 1 миллиона долларов США за первое правильное доказательство, а также призы за шесть других математических проблем . [18]
Дискретная математика — это раздел математики, в котором мы имеем дело с вопросами, связанными с конечными или счетно бесконечными множествами.
![{\displaystyle V(xc)\subset \operatorname {Spec} K[x]=\mathbb {A} ^{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/147df15a1780a002602cd26438adbec315699e2b)
![{\displaystyle \operatorname {Spec} K[x]/(xc)\cong \operatorname {Spec} K}](https://wikimedia.org/api/rest_v1/media/math/render/svg/80cc3220b7c86e6d0862f1bcf3fbac3ffc0191a7)
![{\displaystyle \operatorname {Spec} K[x]_{(xc)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/76e6e66e203e1805ec5b90fa25d9f0c817f28dd7)
