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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Логика

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

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

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

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

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

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

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

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

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

Теория чисел

Теория чисел занимается свойствами чисел в целом, особенно целых чисел . Он имеет приложения в криптографии и криптоанализе , особенно в отношении модульной арифметики , диофантовых уравнений , линейных и квадратичных сравнений, простых чисел и проверки на простоту . Другие дискретные аспекты теории чисел включают геометрию чисел . В аналитической теории чисел также используются методы непрерывной математики. Темы, выходящие за рамки дискретных объектов, включают трансцендентные числа , диофантовую аппроксимацию , 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) — точка вместе с окрестностью вокруг нее. Алгебраические многообразия также имеют четко определенное понятие касательного пространства, называемого касательным пространством Зарисского , что делает многие особенности исчисления применимыми даже в конечных условиях.

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

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

Проблемы

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

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

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

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

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

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

См. также

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

Ссылки

^ Ричард Джонсонбо , Дискретная математика , Прентис Холл, 2008.
^ Франклин, Джеймс (2017). «Дискретное и непрерывное: фундаментальная дихотомия в математике» . Журнал гуманистической математики . 7 (2): 355–378. дои : 10.5642/jhummath.201702.18 . S2CID 6945363 . Проверено 30 июня 2021 г.
^ «Дискретные структуры: что такое дискретная математика?» . cse.buffalo.edu . Проверено 16 ноября 2018 г. .
^ Биггс, Норман Л. (2002), Дискретная математика , Oxford Science Publications (2-е изд.), The Clarendon Press Oxford University Press, стр. 89, ISBN 9780198507178 , MR 1078626 , Дискретная математика - это раздел математики, в котором мы занимаемся вопросами, связанными с конечными или счетными бесконечными множествами.
^ Хопкинс, Брайан, изд. (2009). Ресурсы для преподавания дискретной математики: классные проекты, исторические модули и статьи . Математическая ассоциация Америки. ISBN 978-0-88385-184-5 .
^ Левассер, Кен; Дорр, Ал. Прикладные дискретные структуры . п. 8.
^ Джеффри Хаусон, Альберт, изд. (1988). Математика как предмет службы . Издательство Кембриджского университета. стр. 77–78. ISBN 978-0-521-35395-3 .
^ Розенштейн, Джозеф Г. Дискретная математика в школах . Американское математическое общество. п. 323. ИСБН 978-0-8218-8578-9 .
^ «УЦМП» . uchicago.edu .
^ Троэльстра, А.С.; Швихтенберг, Х. (27 июля 2000 г.). Основная теория доказательств . Издательство Кембриджского университета. п. 186. ИСБН 978-0-521-77911-1 .
^ Басс, Сэмюэл Р. (1998). Справочник по теории доказательств . Эльзевир. п. 13. ISBN 978-0-444-89840-1 .
^ Баадер, Франц; Брюка, Герхард; Эйтер, Томас (16 октября 2001 г.). KI 2001: Достижения в области искусственного интеллекта: Совместная немецко-австрийская конференция по искусственному интеллекту, Вена, Австрия, 19–21 сентября 2001 г. Материалы . Спрингер. п. 325. ИСБН 978-3-540-42612-7 .
^ Бразерстон, Дж.; Борнат, Р.; Кальканьо, К. (январь 2008 г.). «Циклические доказательства завершения программы в логике разделения». Уведомления ACM SIGPLAN . 43 (1): 101–112. дои : 10.1145/1328897.1328453 .
^ Мохар, Боян ; Томассен, Карстен (2001). Графы на поверхностях . Издательство Университета Джонса Хопкинса. ISBN 978-0-8018-6689-0 . OCLC 45102952 .
^ Jump up to: ^а ^б Уилсон, Робин (2002). Четырех цветов достаточно . Лондон: Книги Пингвина. ISBN 978-0-691-11533-7 .
^ Ходжес, Эндрю (1992). Алан Тьюринг: Загадка . Случайный дом .
^ Ходкинсон, Тревор Р.; Парнелл, Джон А.Н. (2007). Реконструкция Древа Жизни: Таксономия и систематика крупных и видовых таксонов . ЦРК Пресс. п. 97. ИСБН 978-0-8493-9579-6 .
^ «Проблемы премии тысячелетия» . 24 мая 2000 г. Проверено 12 января 2008 г.

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

Биггс, Норман Л. (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, содержит ссылки на учебные планы, учебные пособия, программы и т. д.
Центральный штат Айовы: Программа электротехнологий. Дискретная математика для электротехники .

[1] Ричард Джонсонбо , Дискретная математика , Прентис Холл, 2008.

[2] Франклин, Джеймс (2017). «Дискретное и непрерывное: фундаментальная дихотомия в математике» . Журнал гуманистической математики . 7 (2): 355–378. дои : 10.5642/jhummath.201702.18 . S2CID 6945363 . Проверено 30 июня 2021 г.

[3] «Дискретные структуры: что такое дискретная математика?» . cse.buffalo.edu . Проверено 16 ноября 2018 г. .

[4] Биггс, Норман Л. (2002), Дискретная математика , Oxford Science Publications (2-е изд.), The Clarendon Press Oxford University Press, стр. 89, ISBN 9780198507178 , MR 1078626 , Дискретная математика - это раздел математики, в котором мы занимаемся вопросами, связанными с конечными или счетными бесконечными множествами.

[5] Хопкинс, Брайан, изд. (2009). Ресурсы для преподавания дискретной математики: классные проекты, исторические модули и статьи . Математическая ассоциация Америки. ISBN 978-0-88385-184-5 .

[LevasseurDoerr-6] Левассер, Кен; Дорр, Ал. Прикладные дискретные структуры . п. 8.

[Howson1988-7] Джеффри Хаусон, Альберт, изд. (1988). Математика как предмет службы . Издательство Кембриджского университета. стр. 77–78. ISBN 978-0-521-35395-3 .

[Rosenstein-8] Розенштейн, Джозеф Г. Дискретная математика в школах . Американское математическое общество. п. 323. ИСБН 978-0-8218-8578-9 .

[9] «УЦМП» . uchicago.edu .

[10] Троэльстра, А.С.; Швихтенберг, Х. (27 июля 2000 г.). Основная теория доказательств . Издательство Кембриджского университета. п. 186. ИСБН 978-0-521-77911-1 .

[11] Басс, Сэмюэл Р. (1998). Справочник по теории доказательств . Эльзевир. п. 13. ISBN 978-0-444-89840-1 .

[12] Баадер, Франц; Брюка, Герхард; Эйтер, Томас (16 октября 2001 г.). KI 2001: Достижения в области искусственного интеллекта: Совместная немецко-австрийская конференция по искусственному интеллекту, Вена, Австрия, 19–21 сентября 2001 г. Материалы . Спрингер. п. 325. ИСБН 978-3-540-42612-7 .

[13] Бразерстон, Дж.; Борнат, Р.; Кальканьо, К. (январь 2008 г.). «Циклические доказательства завершения программы в логике разделения». Уведомления ACM SIGPLAN . 43 (1): 101–112. дои : 10.1145/1328897.1328453 .

[14] Мохар, Боян ; Томассен, Карстен (2001). Графы на поверхностях . Издательство Университета Джонса Хопкинса. ISBN 978-0-8018-6689-0 . OCLC 45102952 .

[4colors-15] Jump up to: ^а ^б Уилсон, Робин (2002). Четырех цветов достаточно . Лондон: Книги Пингвина. ISBN 978-0-691-11533-7 .

[16] Ходжес, Эндрю (1992). Алан Тьюринг: Загадка . Случайный дом .

[17] Ходкинсон, Тревор Р.; Парнелл, Джон А.Н. (2007). Реконструкция Древа Жизни: Таксономия и систематика крупных и видовых таксонов . ЦРК Пресс. п. 97. ИСБН 978-0-8493-9579-6 .

[CMI_Millennium_Prize_Problems-18] «Проблемы премии тысячелетия» . 24 мая 2000 г. Проверено 12 января 2008 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

v т и Основные математики области
History Timeline Future Lists Glossary
Foundations	Category theory Information theory Mathematical logic Philosophy of mathematics Set theory Type theory
Algebra	Abstract Commutative Elementary Group theory Linear Multilinear Universal Homological
Analysis	Calculus Real analysis Complex analysis Hypercomplex analysis Differential equations Functional analysis Harmonic analysis Measure theory
Discrete	Combinatorics Graph theory Order theory
Geometry	Algebraic Analytic Arithmetic Differential Discrete Euclidean Finite
Number theory	Arithmetic Algebraic number theory Analytic number theory Diophantine geometry
Topology	General Algebraic Differential Geometric Homotopy theory
Applied	Engineering mathematics Mathematical biology Mathematical chemistry Mathematical economics Mathematical finance Mathematical physics Mathematical psychology Mathematical sociology Mathematical statistics Probability Statistics Systems science Control theory Game theory Operations research
Computational	Computer science Theory of computation Computational complexity theory Numerical analysis Optimization Computer algebra
Related topics	Mathematicians lists Informal mathematics Films about mathematicians Recreational mathematics Mathematics and art Mathematics education
Mathematics portal Category Commons WikiProject

Базы данных авторитетного контроля
International	FAST
National	Germany Israel United States Japan Czech Republic
Other	Encyclopedia of Modern Ukraine