Войти
Графики, подобные этому, относятся к объектам, изучаемым дискретной математикой, так как они интересны математические свойства, их полезность в качестве моделей реальных проблем и их важность при разработке компьютерных алгоритмов.Дискретная математика - это исследование математических структур, которые принципиально дискретный, а не непрерывный. В отличие от вещественных чисел, которые обладают свойством «плавного изменения», объекты, изучаемые в дискретной математике, такие как целые числа, графики и операторы в логике - не изменяются плавно таким образом, но имеют различные, разделенные значения. Таким образом, дискретная математика исключает такие разделы «непрерывной математики», как исчисление или евклидова геометрия. Дискретные объекты часто могут быть пронумерованы целыми числами. Более формально дискретная математика была охарактеризована как раздел математики, имеющий дело с счетными множествами (конечными множествами или множествами с той же мощностью, что и натуральные числа). Однако точного определения термина «дискретная математика» не существует. В самом деле, дискретная математика описывается не тем, что включено, а тем, что исключено: постоянно меняющимися величинами и связанными с ними понятиями.
Набор объектов, изучаемых в дискретной математике, может быть конечным или бесконечным. Термин конечная математика иногда применяется к частям области дискретной математики, которая имеет дело с конечными множествами, особенно в тех областях, которые имеют отношение к бизнесу.
Исследования в области дискретной математики расширились во второй половине двадцатого века отчасти из-за развития цифровых компьютеров, которые работают дискретными шагами и хранят данные в дискретных битах. Понятия и обозначения из дискретной математики полезны при изучении и описании объектов и задач в отраслях информатики, таких как компьютерные алгоритмы, языки программирования, криптография, автоматическое доказательство теорем и разработка программного обеспечения. И наоборот, компьютерные реализации играют важную роль в применении идей из дискретной математики к реальным задачам, например, в исследовании операций.
Хотя основными объектами изучения в дискретной математике являются дискретные объекты, часто используются аналитические методы из непрерывной математики. также.
В университетских программах "Дискретная математика" появилась в 1980-х годах, первоначально как вспомогательный курс по информатике; в то время его содержимое было несколько случайным. Учебный план впоследствии был разработан совместно с усилиями ACM и MAA в курс, который в основном предназначен для развития математической зрелости у студентов первого курса; поэтому в настоящее время это является обязательным условием для получения дипломов по математике в некоторых университетах. Также появились учебники по дискретной математике для средней школы. На этом уровне дискретная математика иногда рассматривается как подготовительный курс, в отличие от предварительного вычисления в этом отношении.
Премия Фулкерсона присуждается за выдающиеся работы по дискретной математике..
Многие исследования в области теории графов были мотивированы попытками доказать, что все карты, как и этот может быть окрашен с использованием только четырех цветов, так что никакие области одного цвета не имеют общих краев. Кеннет Аппель и Вольфганг Хакен доказали это в 1976 году. История дискретной математики включает в себя ряд сложных проблем, которые привлекли внимание в разных областях этой области. В теории графов многие исследования были мотивированы попытками доказать теорему о четырех цветах, впервые сформулированную в 1852 году, но не доказанную до 1976 года (Кеннетом Аппелем и Вольфгангом Хакеном при значительной помощи компьютера).
В логике , вторая проблема в списке Дэвида Гилберта открытых проблем, представленных в 1900 году, должна была доказать, что аксиомы из арифметики непротиворечивы. Вторая теорема Гёделя о неполноте, доказанная в 1931 году, показала, что это невозможно - по крайней мере, не в рамках самой арифметики. Десятая проблема Гильберта заключалась в том, чтобы определить, имеет ли данный полином диофантово уравнение с целыми коэффициентами целочисленное решение. В 1970 году Юрий Матиясевич доказал, что это невозможно..
Необходимость взлома немецких кодов в Второй мировой войне привела к успехам в криптография и теоретическая информатика, с первым программируемым цифровым электронным компьютером, разрабатываемым в Англии Bletchley Park под руководством Алан Тьюринг и его основополагающая работа «О вычислимых числах». В то же время военные потребности стимулировали успехи в исследовании операций . Холодная война означала, что криптография оставалась важной, и в последующие десятилетия были разработаны такие фундаментальные достижения, как криптография с открытым ключом. Исследование операций оставалось важным инструментом в управлении бизнесом и проектами, поскольку в 1950-х годах был разработан метод критического пути. Отрасль электросвязи также способствовала развитию дискретной математики, особенно теории графов и теории информации. Формальная проверка утверждений в логике была необходима для разработки программного обеспечения систем, критичных к безопасности, и были достигнуты успехи в автоматическом доказательстве теорем. движимый этой необходимостью.
Вычислительная геометрия была важной частью компьютерной графики, включенной в современные видеоигры и инструменты автоматизированного проектирования.
Некоторые области дискретной математики, в частности теоретическая информатика, теория графов и комбинаторика, важны для решения сложных проблем биоинформатики, связанных с пониманием дерево жизни.
В настоящее время одной из самых известных открытых проблем в теоретической информатике является проблема P = NP, которая включает взаимосвязь между классами сложности P и НП. Институт математики Клэя предложил приз в размере 1 миллиона долларов долларов США за первое верное доказательство, а также призы за шесть других математических задач.
Сложность изучает время, затрачиваемое алгоритмами, такими как эта процедура сортировки.Теоретическая информатика включает области дискретной математики, относящиеся к вычислениям. Он в значительной степени опирается на теорию графов и математическую логику. В теоретическую информатику входит изучение алгоритмов и структур данных. Вычислимость изучает, что можно вычислить в принципе, и имеет тесную связь с логикой, в то время как сложность изучает время, пространство и другие ресурсы, используемые вычислениями. Теория автоматов и теория формального языка тесно связаны с вычислимостью. Сети Петри и алгебры процессов используются для моделирования компьютерных систем, а методы дискретной математики используются при анализе электронных схем СБИС. Вычислительная геометрия применяет алгоритмы к геометрическим задачам, тогда как компьютерный анализ изображений применяет их к представлениям изображений. Теоретическая информатика также включает изучение различных тем, связанных с непрерывными вычислениями.
Коды ASCII для слова «Википедия», приведенные здесь в двоичном формате, обеспечивают способ представления слова в информации теория, а также для обработки информации алгоритмы.Теория информации включает количественную оценку информации. Тесно связана теория кодирования, которая используется для разработки эффективных и надежных методов передачи и хранения данных. Теория информации также включает непрерывные темы, такие как: аналоговые сигналы, аналоговое кодирование, аналоговое шифрование.
Логика - это изучение принципов обоснованное обоснование и вывод, а также согласованности, обоснованности и полноты. Например, в большинстве систем логики (но не в интуиционистской логике ) закон Пирса (((P → Q) → P) → P) является теоремой. Для классической логики это можно легко проверить с помощью таблицы истинности. Изучение математического доказательства особенно важно в логике и имеет приложения для автоматического доказательства теорем и формальной проверки программного обеспечения.
Логические формулы представляют собой дискретные структуры, как и доказательства, которые образуют конечные деревья или, в более общем смысле, структуры ориентированного ациклического графа (с каждой шаг вывода, объединяющий одну или несколько ветвей посылки для получения единого вывода). значения истинности логических формул обычно образуют конечный набор, обычно ограниченный двумя значениями: истинным и ложным, но логика также может иметь непрерывные значения, например, нечеткая логика. Также изучались такие концепции, как бесконечные деревья доказательства или бесконечные деревья вывода, например бесконечная логика.
Теория множеств - это раздел математики, изучающий множества, которые представляют собой совокупности объектов, таких как {синий, белый, красный} или (бесконечный) набор всех простых чисел. Частично упорядоченные наборы и наборы с другими отношениями имеют применения в нескольких областях.
В дискретной математике счетные множества (включая конечные множества ) являются основным объектом внимания. Начало теории множеств как раздела математики обычно отмечается в работе Георга Кантора, в которой проводится различие между различными видами бесконечного множества, мотивированных изучением тригонометрических рядов и дальнейшим развитием теории бесконечных множеств выходит за рамки дискретной математики. Действительно, современные работы по описательной теории множеств широко используют традиционную непрерывную математику.
Комбинаторика изучает способ, которым дискретные структуры могут быть объединены или расположены. Перечислительная комбинаторика концентрируется на подсчете количества определенных комбинаторных объектов - например, двенадцатикратный способ обеспечивает единую структуру для подсчета перестановок, комбинаций и разделов. Аналитическая комбинаторика касается перечисления (т. Е. Определения количества) комбинаторных структур с использованием инструментов из комплексного анализа и теории вероятностей. В отличие от перечислительной комбинаторики, которая использует явные комбинаторные формулы и производящие функции для описания результатов, аналитическая комбинаторика стремится получить асимптотические формулы. Теория дизайна - это исследование комбинаторных планов, которые представляют собой коллекции подмножеств с определенными свойствами пересечения. Теория разделов изучает различные проблемы перечисления и асимптотики, связанные с целочисленными разделами, и тесно связана с q-серией, специальными функциями и ортогональные многочлены. Первоначально являясь частью теории чисел и анализа, теория разделов теперь считается частью комбинаторики или независимой областью. Теория порядка - это изучение частично упорядоченных множеств, как конечных, так и бесконечных.
Теория графов имеет тесные связи с теорией групп. Этот усеченный тетраэдрический граф относится к переменной группе A4.Теория графов, изучение графов и сетей, часто считается частью комбинаторики., но стал достаточно большим и достаточно отчетливым, со своими собственными проблемами, чтобы его можно было рассматривать как самостоятельный предмет. Графы - один из основных объектов изучения дискретной математики. Они являются одними из самых распространенных моделей как природных, так и созданных руками человека. Они могут моделировать многие типы отношений и динамику процессов в физических, биологических и социальных системах. В информатике они могут представлять сети связи, организацию данных, вычислительные устройства, поток вычислений и т. Д. В математике они используются в геометрии и некоторых частях топологии , например теория узлов. Алгебраическая теория графов имеет тесные связи с теорией групп. Также есть непрерывные графики ; однако по большей части исследования теории графов относятся к области дискретной математики.
Теория дискретной вероятности имеет дело с событиями, которые происходят в счетных пробелах. Например, данные подсчета, такие как количество птиц в стаях, содержат только натуральные числа {0, 1, 2,...}. С другой стороны, непрерывные наблюдения, такие как вес птиц, содержат действительные числовые значения и обычно моделируются непрерывным распределением вероятностей, таким как нормальное. Дискретные распределения вероятностей могут использоваться для аппроксимации непрерывных и наоборот. Для ситуаций с жесткими ограничениями, таких как бросание игральных костей или эксперименты с колодами карт, вычисление вероятности событий в основном выполняется перечислительной комбинаторикой.
Спираль Улама чисел, с черными пикселями, показывающими простые числа. Эта диаграмма намекает на закономерности в распределении простых чисел. Теория чисел занимается свойствами чисел в целом, особенно целых чисел. Он может применяться в криптографии и криптоанализе, особенно в отношении модульной арифметики, диофантовых уравнений, линейных и квадратичных сравнений, простых чисел и проверка простоты. Другие дискретные аспекты теории чисел включают геометрию чисел. В аналитической теории чисел также используются методы непрерывной математики. Темы, выходящие за рамки дискретных объектов, включают трансцендентные числа, диофантово приближение, p-адический анализ и функциональные поля.
Алгебраические структуры встречаются как в дискретных, так и в непрерывных примерах. Дискретные алгебры включают: логическую алгебру, используемую в логических элементах и программировании; реляционная алгебра, используемая в базах данных ; дискретные и конечные версии групп, колец и полей важны в алгебраической теории кодирования ; дискретные полугруппы и моноиды появляются в теории формальных языков.
A функция, определенная на интервале из целых чисел обычно называется последовательностью. Последовательность может быть конечной последовательностью из источника данных или бесконечной последовательностью из дискретной динамической системы. Такая дискретная функция может быть определена явно списком (если ее область определения конечна), или формулой для ее общего члена, или она может быть задана неявно с помощью рекуррентного отношения или разностного уравнения.. Уравнения разности аналогичны дифференциальным уравнениям, но заменяют дифференцирование, беря разность между соседними членами; их можно использовать для аппроксимации дифференциальных уравнений или (чаще) изучать самостоятельно. Многие вопросы и методы, касающиеся дифференциальных уравнений, имеют аналоги для разностных уравнений. Например, там, где есть интегральные преобразования в гармоническом анализе для изучения непрерывных функций или аналоговых сигналов, есть дискретные преобразования для дискретных функций или цифровых сигналов. Помимо дискретной метрики существуют более общие дискретные или конечные метрические пространства и конечные топологические пространства.
Вычислительная геометрия применяет компьютер алгоритмы к представлениям геометрических объектов. Дискретная геометрия и комбинаторная геометрия касаются комбинаторных свойств дискретных наборов геометрических объектов. Давняя тема в дискретной геометрии - мозаика плоскости. Вычислительная геометрия применяет алгоритмы к геометрическим задачам.
Хотя топология - это область математики, которая формализует и обобщает интуитивное понятие «непрерывной деформации» объектов, она порождает множество отдельных тем; Отчасти это можно объяснить акцентом на топологические инварианты , которые сами обычно принимают дискретные значения. См. комбинаторную топологию, топологическую теорию графов, топологическую комбинаторику, вычислительную топологию, дискретное топологическое пространство, конечное топологическое пространство, топология (химия).
PERT диаграммы, подобные этой, обеспечивают технику управления проектами, основанную на теории графов.Исследование операций предоставляет методы для решение практических задач в инженерии, бизнесе и других областях - таких как выделение ресурсов для максимизации прибыли и планирование деятельности по проекту для минимизации рисков. Методы исследования операций включают линейное программирование и другие области оптимизации, теорию массового обслуживания, теорию расписания и теорию сетей. Исследование операций также включает в себя непрерывные темы, такие как марковский процесс в непрерывном времени, непрерывный мартингейл, оптимизация процессов, а также непрерывное и гибридное теория управления.
| Сотрудничать | Дефект | |
| Сотрудничать | -1, -1 | -10, 0 |
| Дефект | 0, −10 | −5, −5 |
| Матрица выплат для дилеммы заключенного, распространенный пример в теории игр. Один игрок выбирает строку, другой - столбец; результирующая пара дает свои результаты | ||
Теория принятия решений занимается определением значений, неопределенностей и других вопросов, относящихся к данному решению, его рациональности и итогового оптимального решения.
Теория полезности измеряет относительную экономическую удовлетворенность или желательность потребления различных товаров и услуг.
Теория социального выбора о голосовании. Более основанный на головоломках подход к голосованию - это теория бюллетеней.
Теория игр имеет дело с ситуациями, когда успех зависит от выбора других, что усложняет выбор наилучшего образа действий. Есть даже непрерывные игры, см. дифференциальная игра. Темы включают теорию аукционов и справедливое разделение.
Дискретизация касается процесса преобразования непрерывных моделей и уравнений в дискретные аналоги, часто с целью упрощения вычислений с помощью приближения. Численный анализ является важным примером.
В непрерывной математике существует множество концепций, которые имеют дискретные версии, такие как дискретное исчисление, дискретные распределения вероятностей, дискретное преобразование Фурье, дискретная геометрия, дискретные логарифмы, дискретная дифференциальная геометрия, дискретное внешнее исчисление, дискретная теория Морса, разностные уравнения, дискретные динамические системы и дискретные векторные меры.
В прикладной математике, Дискретное моделирование является дискретным аналогом непрерывного моделирования. При дискретном моделировании дискретные формулы соответствуют данным. Распространенным методом в этой форме моделирования является использование рекуррентного соотношения.
В алгебраической геометрии концепция кривой может быть расширена до дискретных геометрий, взяв спектры колец многочленов над конечными полями, чтобы быть моделями аффинных пространств над этим полем, и позволяя подмногообразиям или спектрам других колец обеспечивать кривые, лежащие в этом пространстве. Хотя пространство, в котором появляются кривые, имеет конечное число точек, кривые представляют собой не столько наборы точек, сколько аналоги кривых в непрерывных настройках. Например, каждая точка вида ![V (xc) \ subset \ operatorname {Spec} K [x] = \ mathbb {A} ^ {1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/147df15a1780a002602cd26438adbec315699e2b)
![\ operatorname {Spec} K [x] / (xc) \ cong \ operatorname {Spec} K](https://wikimedia.org/api/rest_v1/media/math/render/svg/80cc3220b7c86e6d0862f1bcf3fbac3ffc0191a7)
![\ operatorname {Spec} K [x] _ {(xc)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/76e6e66e203e1805ec5b90fa25d9f0c817f28dd7)
исчисление шкалы времени представляет собой объединение теории разностных уравнений с теорией дифференциальных уравнений, который имеет приложения к областям, требующим одновременного моделирования дискретных и непрерывных данных. Другой способ моделирования такой ситуации - понятие гибридных динамических систем.
Математический портал  | В Викиучебнике есть книга по теме: Дискретная математика |
Средства массовой информации, связанные с Дискретной математикой на Wikimedia Commons