Дискретная математика - Discrete mathematics

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

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

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

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

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

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

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

Грандиозные вызовы прошлого и настоящего

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

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

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

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

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

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

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

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

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

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

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

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

В ASCII - кода для слова «Википедия», приведенная здесь в двоичном виде , обеспечивает способ представления слова в теории информации , а также для обработки информации , алгоритмов .

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

Логика

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

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

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

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

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

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

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

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

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

Вероятность

Теория дискретной вероятности имеет дело с событиями, которые происходят в счетных пространствах выборок . Например, данные подсчета, такие как количество птиц в стаях, содержат только натуральные числа {0, 1, 2, ...}. С другой стороны, непрерывные наблюдения, такие как вес птиц, содержат действительные числовые значения и обычно моделируются непрерывным распределением вероятностей, например нормальным . Дискретные распределения вероятностей могут использоваться для аппроксимации непрерывных и наоборот. Для ситуаций с жесткими ограничениями, таких как бросание игральных костей или эксперименты с колодами карт , вычисление вероятности событий в основном является комбинаторикой перечисления .

Теория чисел

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

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

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

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

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

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

Геометрия

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

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

Топология

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

Исследование операций

Подобные диаграммы PERT предоставляют технику управления проектами, основанную на теории графов .

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

Теория игр, теория принятия решений, теория полезности, теория социального выбора

Сотрудничать Дефект
Сотрудничать −1, −1 −10, 0
Дефект 0, -10 −5, −5
Матрица выплат для дилеммы заключенного , распространенный пример в теории игр . Один игрок выбирает строку, другой - столбец; полученная пара дает свои выплаты

Теория принятия решений занимается определением ценностей, неопределенностей и других вопросов, относящихся к данному решению, его рациональности и итогового оптимального решения.

Теория полезности касается показателей относительного экономического удовлетворения или желательности потребления различных товаров и услуг.

Теория социального выбора - это голосование . Более сложный подход к голосованию - это теория бюллетеней .

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

Дискретность

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

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

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

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

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

Гибридная дискретная и непрерывная математика

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

Смотрите также

использованная литература

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

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

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