Дискретная математика — это исследование математических структур , которые можно считать «дискретными» (по аналогии с дискретными переменными , имеющими биекцию с набором натуральных чисел ), а не «непрерывными» (аналогично непрерывным функциям ). Объекты, изучаемые в дискретной математике, включают целые числа , графики и логические утверждения . [1] [2] [3] Напротив, дискретная математика исключает темы «непрерывной математики», такие как действительные числа , исчисление или евклидова геометрия . Дискретные объекты часто могут быть пронумерованы целыми числами ; более формально, дискретная математика характеризуется как раздел математики, изучающий счетные множества [4] (конечные множества или множества той же мощности , что и натуральные числа). Однако точного определения термина «дискретная математика» не существует. [5]
Множество объектов, изучаемых в дискретной математике, может быть конечным или бесконечным. Термин «конечная математика» иногда применяется к частям области дискретной математики, которые имеют дело с конечными множествами, особенно к тем областям, которые имеют отношение к бизнесу.
Исследования в области дискретной математики расширились во второй половине двадцатого века, отчасти благодаря развитию цифровых компьютеров , которые работают «дискретно» и хранят данные в «дискретных» битах. Концепции и обозначения дискретной математики полезны при изучении и описании объектов и проблем в таких областях информатики , как компьютерные алгоритмы , языки программирования , криптография , автоматическое доказательство теорем и разработка программного обеспечения . И наоборот, компьютерные реализации играют важную роль в применении идей дискретной математики к реальным проблемам.
Хотя основными объектами исследования в дискретной математике являются дискретные объекты, часто используются и аналитические методы «непрерывной» математики.
В университетских учебных программах дискретная математика появилась в 1980-х годах, первоначально как вспомогательный курс по информатике; в то время его содержание было несколько бессистемным. Впоследствии учебная программа была преобразована совместно с усилиями ACM и MAA в курс, который в основном предназначен для развития математической зрелости у студентов первого курса; поэтому в настоящее время это также является обязательным условием для поступления на математические специальности в некоторых университетах. [6] [7] [8] Также появилось несколько учебников по дискретной математике для старших классов. [9] На этом уровне дискретная математика иногда рассматривается как подготовительный курс, подобно предварительному исчислению в этом отношении. [10]
Премия Фулкерсона присуждается за выдающиеся работы в области дискретной математики.
Теоретическая информатика включает области дискретной математики, имеющие отношение к вычислениям. Он в значительной степени опирается на теорию графов и математическую логику . В теоретическую информатику входит изучение алгоритмов и структур данных. Вычислимость изучает то, что можно вычислить в принципе, и тесно связана с логикой, тогда как сложность изучает время, пространство и другие ресурсы, используемые вычислениями. Теория автоматов и теория формального языка тесно связаны с вычислимостью. Сети Петри и алгебры процессов используются для моделирования компьютерных систем, а методы дискретной математики используются для анализа электронных схем СБИС . Вычислительная геометрия применяет алгоритмы к геометрическим задачам и представлениям геометрических объектов, а компьютерный анализ изображений применяет их к представлениям изображений. Теоретическая информатика также включает изучение различных тем, связанных с непрерывными вычислениями.
Теория информации предполагает количественную оценку информации . Тесно связана теория кодирования , которая используется для разработки эффективных и надежных методов передачи и хранения данных. Теория информации также включает в себя сплошные темы, такие как: аналоговые сигналы , аналоговое кодирование , аналоговое шифрование .
Логика – это изучение принципов обоснованных рассуждений и выводов , а также последовательности , обоснованности и полноты . Например, в большинстве систем логики (но не в интуиционистской логике ) закон Пирса ((( P → Q )→ P )→ P ) является теоремой. Для классической логики это легко проверить с помощью таблицы истинности . Изучение математических доказательств особенно важно в логике и связано с автоматизированным доказательством теорем и формальной проверкой программного обеспечения.
Логические формулы представляют собой дискретные структуры, как и доказательства , которые образуют конечные деревья [11] или, в более общем смысле, ориентированные ациклические графовые структуры [12] [13] (при этом каждый шаг вывода объединяет одну или несколько ветвей посылок для получения единственного заключения). Значения истинности логических формул обычно образуют конечное множество, обычно ограниченное двумя значениями: true и false , но логика также может быть непрерывнозначной, например, нечеткая логика . Также изучались такие концепции, как бесконечные деревья доказательств или бесконечные деревья вывода, [14], например, бесконечная логика .
Теория множеств — это раздел математики, изучающий множества , которые представляют собой коллекции объектов, таких как {синий, белый, красный} или (бесконечное) множество всех простых чисел . Частично упорядоченные множества и множества с другими отношениями находят приложения в нескольких областях.
В дискретной математике основное внимание уделяется счетным множествам (включая конечные множества ). Начало теории множеств как раздела математики обычно отмечают работы Георга Кантора , проводившие различие между различными видами бесконечных множеств , мотивированные изучением тригонометрических рядов, а дальнейшее развитие теории бесконечных множеств выходит за рамки дискретных множеств. математика. Действительно, современные работы в области дескриптивной теории множеств широко используют традиционную непрерывную математику.
Комбинаторика изучает способы объединения или расположения дискретных структур. Перечислительная комбинаторика концентрируется на подсчете количества определенных комбинаторных объектов - например, двенадцатикратный способ обеспечивает единую основу для подсчета перестановок , комбинаций и разделов . Аналитическая комбинаторика занимается перечислением (т. е. определением количества) комбинаторных структур с использованием инструментов комплексного анализа и теории вероятностей . В отличие от перечислительной комбинаторики, которая использует явные комбинаторные формулы и производящие функции для описания результатов, аналитическая комбинаторика направлена на получение асимптотических формул . Топологическая комбинаторика касается использования методов топологии и алгебраической топологии / комбинаторной топологии в комбинаторике . Теория дизайна — это исследование комбинаторных проектов , которые представляют собой коллекции подмножеств с определенными свойствами пересечения . Теория разбиений изучает различные проблемы перечисления и асимптотики, связанные с целочисленными разбиениями , и тесно связана с q-рядами , специальными функциями и ортогональными полиномами . Теория разделов, первоначально являвшаяся частью теории чисел и анализа , теперь считается частью комбинаторики или независимой областью. Теория порядка — это изучение частично упорядоченных множеств , как конечных, так и бесконечных.
Теория графов, изучение графов и сетей , часто считается частью комбинаторики, но она стала достаточно большой и четкой, со своими собственными проблемами, чтобы ее можно было рассматривать как отдельный предмет. [15] Графы являются одним из основных объектов исследования в дискретной математике. Они являются одними из наиболее распространенных моделей как природных, так и искусственных сооружений. Они могут моделировать многие типы отношений и динамику процессов в физических, биологических и социальных системах. В информатике они могут представлять сети связи, организацию данных, вычислительные устройства, поток вычислений и т. д. В математике они полезны в геометрии и некоторых частях топологии , например теории узлов . Алгебраическая теория графов тесно связана с теорией групп, а топологическая теория графов тесно связана с топологией . Существуют также непрерывные графики ; однако по большей части исследования в области теории графов относятся к области дискретной математики.
Теория чисел занимается свойствами чисел в целом, особенно целых чисел . Он имеет приложения в криптографии и криптоанализе , особенно в отношении модульной арифметики , диофантовых уравнений , линейных и квадратичных сравнений, простых чисел и проверки на простоту . Другие дискретные аспекты теории чисел включают геометрию чисел . В аналитической теории чисел также используются методы непрерывной математики. Темы, выходящие за рамки дискретных объектов, включают трансцендентные числа , диофантовую аппроксимацию , p-адический анализ и функциональные поля .
Алгебраические структуры встречаются как в виде дискретных, так и в виде непрерывных примеров. К дискретным алгебрам относятся: булева алгебра, используемая в логических элементах и программировании; реляционная алгебра , используемая в базах данных ; дискретные и конечные версии групп , колец и полей важны в алгебраической теории кодирования ; дискретные полугруппы и моноиды появляются в теории формальных языков .
В непрерывной математике существует множество концепций и теорий, которые имеют дискретные версии, такие как дискретное исчисление , дискретные преобразования Фурье , дискретная геометрия , дискретные логарифмы , дискретная дифференциальная геометрия , дискретное внешнее исчисление , дискретная теория Морса , дискретная оптимизация , дискретная теория вероятностей , дискретная вероятность. распределение , разностные уравнения , дискретные динамические системы и дискретные векторные меры .
В дискретном исчислении и исчислении конечных разностей функция , определенная на интервале целых чисел , обычно называется последовательностью . Последовательность может быть конечной последовательностью из источника данных или бесконечной последовательностью из дискретной динамической системы . Такая дискретная функция может быть определена явно списком (если ее область определения конечна) или формулой для ее общего термина, или она может быть задана неявно с помощью рекуррентного соотношения или разностного уравнения . Разностные уравнения подобны дифференциальным уравнениям , но заменяют дифференцирование , беря разность между соседними членами; их можно использовать для аппроксимации дифференциальных уравнений или (чаще) изучать самостоятельно. Многие вопросы и методы, касающиеся дифференциальных уравнений, имеют аналоги для разностных уравнений. Например, там, где в гармоническом анализе используются интегральные преобразования для изучения непрерывных функций или аналоговых сигналов, существуют дискретные преобразования для дискретных функций или цифровых сигналов. Помимо дискретных метрических пространств , существуют более общие дискретные топологические пространства , конечные метрические пространства , конечные топологические пространства .
Исчисление шкалы времени представляет собой объединение теории разностных уравнений с теорией дифференциальных уравнений , которое имеет приложения к областям, требующим одновременного моделирования дискретных и непрерывных данных. Другим способом моделирования такой ситуации является понятие гибридных динамических систем .
Дискретная геометрия и комбинаторная геометрия посвящены комбинаторным свойствам дискретных наборов геометрических объектов. Давняя тема в дискретной геометрии — замощение плоскости .
В алгебраической геометрии понятие кривой может быть расширено до дискретной геометрии, если принять спектры колец многочленов над конечными полями в качестве моделей аффинных пространств над этим полем и позволить подмногообразиям или спектрам других колец предоставить кривые, лежащие в это пространство. Хотя пространство, в котором появляются кривые, имеет конечное число точек, кривые представляют собой не столько наборы точек, сколько аналоги кривых в непрерывных условиях. Например, каждую точку вида поля можно изучать либо как , точку, либо как спектр локального кольца в (xc) , точку вместе с окрестностью вокруг нее. Алгебраические многообразия также имеют четко определенное понятие касательного пространства, называемого касательным пространством Зарисского , что делает многие особенности исчисления применимыми даже в конечных условиях.
В прикладной математике дискретное моделирование является дискретным аналогом непрерывного моделирования . В дискретном моделировании дискретные формулы соответствуют данным . Распространенным методом в этой форме моделирования является использование рекуррентного отношения . Дискретизация касается процесса перевода непрерывных моделей и уравнений в дискретные аналоги, часто с целью упрощения вычислений за счет использования аппроксимаций. Численный анализ дает важный пример.
История дискретной математики включает в себя ряд сложных проблем, которые привлекли внимание отдельных областей этой области. В теории графов многие исследования были мотивированы попытками доказать теорему о четырех цветах , впервые сформулированную в 1852 году, но не доказанную до 1976 года (Кеннет Аппель и Вольфганг Хакен, используя существенную помощь компьютера). [16]
В логике второй задачей из списка открытых задач Дэвида Гильберта , представленного в 1900 году, было доказательство непротиворечивости аксиом арифметики . Вторая теорема Гёделя о неполноте , доказанная в 1931 году, показала, что это невозможно – по крайней мере, в самой арифметике. Десятая проблема Гильберта заключалась в том, чтобы определить, имеет ли данное полиномиальное диофантово уравнение с целыми коэффициентами целочисленное решение. В 1970 году Юрий Матиясевич доказал, что этого сделать невозможно .
Необходимость взлома немецких кодов во Второй мировой войне привела к достижениям в криптографии и теоретической информатике : первый программируемый цифровой электронный компьютер был разработан в английском Блетчли-парке под руководством Алана Тьюринга и его основополагающей работы «О вычислимых числах». [17] Холодная война означала, что криптография оставалась важной, и в последующие десятилетия были разработаны фундаментальные достижения, такие как криптография с открытым ключом . Телекоммуникационная отрасль также способствовала развитию дискретной математики, особенно теории графов и теории информации . Формальная проверка логических утверждений была необходима для разработки программного обеспечения систем, критически важных для безопасности , и достижения в области автоматизированного доказательства теорем были обусловлены этой необходимостью.
Вычислительная геометрия стала важной частью компьютерной графики , включенной в современные видеоигры и инструменты автоматизированного проектирования .
Некоторые области дискретной математики, особенно теоретическая информатика, теория графов и комбинаторика , играют важную роль в решении сложных проблем биоинформатики , связанных с пониманием древа жизни . [18]
В настоящее время одной из самых известных открытых задач в теоретической информатике является проблема P=NP , которая предполагает взаимосвязь между классами сложности P и NP . Институт математики Клея предложил приз в 1 миллион долларов США за первое правильное доказательство, а также призы за шесть других математических задач . [19]
Дискретная математика - это раздел математики, в котором мы занимаемся вопросами, связанными с конечными или счетными бесконечными множествами.
![{\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)
