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

Чтобы узнать о математическом журнале, см. Дискретная математика (журнал) .

«Конечная математика» перенаправляется сюда. Программу см. в разделе Конечная математика .

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

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

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

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

Хотя основными объектами исследования в дискретной математике являются дискретные объекты, аналитические часто используются и методы «непрерывной» математики.

В университетских учебных программах дискретная математика появилась в 1980-х годах, первоначально как вспомогательный курс по информатике; в то время его содержание было несколько бессистемным. Впоследствии учебная программа была преобразована совместно с усилиями ACM и MAA в курс, который в основном предназначен для развития математической зрелости у студентов первого курса; поэтому в настоящее время это также является обязательным условием для поступления на математические специальности в некоторых университетах. Появилось также несколько учебников по дискретной математике для средней школы. На этом уровне дискретная математика иногда рассматривается как подготовительный курс, подобно предварительному исчислению в этом отношении.

Премия Фулкерсона присуждается за выдающиеся работы в области дискретной математики.

Темы по дискретной математике

Смотрите также: Очерк дискретной математики.

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

Основная статья: Теоретическая информатика

Сложность изучает время, затрачиваемое алгоритмами , такими как эта процедура сортировки .

Вычислительная геометрия применяет компьютерные алгоритмы к представлениям геометрических объектов.

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

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

Основная статья: Теория информации

Коды ASCII для слова «Arc.Ask3.Ru», приведенные здесь в двоичном виде , обеспечивают способ представления этого слова в теории информации , а также для алгоритмов обработки информации .

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

Логика

Основная статья: Математическая логика

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

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

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

Основная статья: Теория множеств

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

В дискретной математике счетным множествам (включая конечные множества основное внимание уделяется ). Начало теории множеств как раздела математики обычно отмечается работой Георга Кантора , проводившей различие между различными видами бесконечных множеств , мотивированной изучением тригонометрических рядов, а дальнейшее развитие теории бесконечных множеств выходит за рамки дискретных множеств. математика. Действительно, современные работы в области дескриптивной теории множеств широко используют традиционную непрерывную математику.

Комбинаторика

Основная статья: Комбинаторика

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

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

Основная статья: Теория графов

Теория графов тесно связана с теорией групп . Этот усеченный граф тетраэдра относится к знакопеременной группе A ₄ .

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

Теория чисел

Спираль Улама чисел с черными пикселями, показывающими простые числа . Эта диаграмма намекает на закономерности в распределении простых чисел.

Основная статья: Теория чисел

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

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

Основная статья: Абстрактная алгебра

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

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

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

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

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

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

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

Дискретная геометрия и комбинаторная геометрия посвящены комбинаторным свойствам дискретных наборов геометрических объектов. Давняя тема в дискретной геометрии — замощение плоскости .

В алгебраической геометрии понятие кривой может быть расширено до дискретной геометрии, если принять спектры над колец многочленов конечными полями в качестве моделей аффинных пространств над этим полем и позволить подмногообразиям или спектрам других колец предоставить кривые, лежащие в это пространство. Хотя пространство, в котором появляются кривые, имеет конечное число точек, кривые представляют собой не столько наборы точек, сколько аналоги кривых в непрерывных условиях. Например, каждая точка вида $V(x-c)\subset \operatorname {Spec} K[x]=\mathbb {A} ^{1}$ для $K$ поле можно изучать либо как $\operatorname {Spec} K[x]/(x-c)\cong \operatorname {Spec} K$, точка или как спектр $\operatorname {Spec} K[x]_{(x-c)}$ локального кольца в (xc) — точка вместе с окрестностью вокруг нее. Алгебраические многообразия также имеют четко определенное понятие касательного пространства, называемого касательным пространством Зарисского , что делает многие особенности исчисления применимыми даже в конечных условиях.

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

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

Проблемы

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

История дискретной математики включает в себя ряд сложных проблем, которые привлекли внимание отдельных областей этой области. В теории графов многие исследования были мотивированы попытками доказать теорему о четырех цветах , впервые сформулированную в 1852 году, но не доказанную до 1976 года (Кеннет Аппель и Вольфганг Хакен, используя существенную помощь компьютера).

В логике из второй задачей списка Дэвида Гильберта открытых задач было доказательство аксиом арифметики представленного в 1900 году , непротиворечивости , . Вторая теорема Гёделя о неполноте , доказанная в 1931 году, показала, что это невозможно – по крайней мере, в самой арифметике. Десятая проблема Гильберта заключалась в том, чтобы определить, имеет ли данное полиномиальное диофантово уравнение с целыми коэффициентами целочисленное решение. В 1970 году Юрий Матиясевич доказал, что этого сделать невозможно .

Необходимость взлома немецких кодов во Второй мировой войне привела к достижениям в криптографии и теоретической информатике : первый программируемый цифровой электронный компьютер был разработан в английском Блетчли-парке под руководством Алана Тьюринга и его основополагающей работы «О вычислимых числах». Холодная война фундаментальные достижения, такие как криптография с открытым ключом означала, что криптография оставалась важной, и в последующие десятилетия были разработаны . Телекоммуникационная теории отрасль также способствовала развитию дискретной математики, особенно теории графов и информации . Формальная проверка логических утверждений была необходима для разработки программного обеспечения систем, критически важных для безопасности , и достижения в области автоматизированного доказательства теорем были обусловлены этой необходимостью.

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

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

В настоящее время одной из самых известных открытых задач в теоретической информатике является проблема P=NP , которая предполагает взаимосвязь между классами сложности P и NP . Институт математики Клея предложил приз в 1 миллион долларов США за первое правильное доказательство, а также призы за шесть других математических задач .

См. также

• Очерк дискретной математики
• Cyberchase — шоу, обучающее детей дискретной математике.

Дальнейшее чтение

• Биггс, Норман Л. (2002). Дискретная математика . Издательство Оксфордского университета. ISBN  978-0-19-850717-8 .
• Дуайер, Джон (2010). Введение в дискретную математику для бизнеса и вычислений . ISBN  978-1-907934-00-1 .
• Эпп, Сюзанна С. (4 августа 2010 г.). Дискретная математика с приложениями . Томсон Брукс/Коул. ISBN  978-0-495-39132-6 .
• Грэм, Рональд ; Кнут, Дональд Э .; Паташник, Орен (1994). Конкретная математика (2-е изд.). Аддисон-Уэсли. ISBN  0-201-55802-5 .
• Гримальди, Ральф П. (2004). Дискретная и комбинаторная математика: прикладное введение . Эддисон Уэсли. ISBN  978-0-201-72634-3 .
• Кнут, Дональд Э. (2011). Искусство компьютерного программирования . Том. 1–4а Коробочный набор. Аддисон-Уэсли. ISBN  978-0-321-75104-1 .
• Матушек, Иржи ; Нешетрил, Ярослав (1998). Дискретная математика . Издательство Оксфордского университета. ISBN  978-0-19-850208-1 .
• Обренич, Бояна (2003). Практические задачи по дискретной математике . Прентис Холл. ISBN  978-0-13-045803-2 .
• Розен, Кеннет Х.; Майклс, Джон Г. (2000). Справочник по дискретной и комбинаторной математике . ЦРК Пресс. ISBN  978-0-8493-0149-0 .
• Розен, Кеннет Х. (2007). Дискретная математика: и ее приложения . МакГроу-Хилл. ISBN  978-0-07-288008-3 .
• Симпсон, Эндрю (2002). Дискретная математика на примерах . МакГроу-Хилл. ISBN  978-0-07-709840-7 .

Внешние ссылки

• Дискретная математика. Архивировано 29 августа 2011 г. на Wayback Machine в математических архивах utk.edu, содержит ссылки на учебные планы, учебные пособия, программы и т. д.
• Центральный штат Айовы: Программа электротехнологий. Дискретная математика для электротехники .