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

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

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

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

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

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

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

Грандиозные проблемы, прошлые и настоящие [ править ]

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

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

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

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

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

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

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

Темы дискретной математики [ править ]

Теоретическая информатика [ править ]

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

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

Теория информации [ править ]

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

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

Логика [ править ]

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

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

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

Теория множеств [ править ]

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

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

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

Комбинаторика [ править ]

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

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

Теория графов [ править ]

Основная статья: Теория графов
Теория графов тесно связана с теорией групп . Этот усеченный тетраэдрический граф связан с альтернированной группой A 4 .

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

Вероятность [ править ]

Основная статья: Дискретная теория вероятностей

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

Теория чисел [ править ]

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

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

Алгебраические структуры [ править ]

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

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

Исчисление конечных разностей, дискретное исчисление или дискретный анализ [ править ]

Основная статья: Конечная разница

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

Геометрия [ править ]

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

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

Топология [ править ]

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

Исследование операций [ править ]

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

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

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

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

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

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

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

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

Дискретизация [ править ]

Основная статья: Дискретность

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

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

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

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ Ричард Джонсонбо , дискретная математика , Prentice Hall, 2008.
  2. ^ Вайсштейн, Эрик В. "Дискретная математика" . MathWorld .
  3. ^ https://cse.buffalo.edu/~rapaport/191/S09/whatisdiscmath.html, по состоянию на 16 ноября 18.
  4. ^ Биггс, Норман Л. (2002), Дискретная математика , Oxford Science Publications (2-е изд.), Нью-Йорк: The Clarendon Press Oxford University Press, стр. 89, ISBN 9780198507178, MR  1078626 , Дискретная математика - это раздел математики, в котором мы имеем дело с вопросами, касающимися конечных или счетно бесконечных множеств.
  5. ^ Брайан Хопкинс, Ресурсы для преподавания дискретной математики , Математическая ассоциация Америки, 2008.
  6. ^ Кен Левассер; Аль Дёрр. Прикладные дискретные конструкции . п. 8.
  7. ^ Альберт Джеффри Хаусон, изд. (1988). Математика как служебный предмет . Издательство Кембриджского университета. С. 77–78. ISBN 978-0-521-35395-3.
  8. ^ Джозеф Г. Розенштейн. Дискретная математика в школе . American Mathematical Soc. п. 323. ISBN 978-0-8218-8578-9.
  9. ^ "UCSMP" . uchicago.edu .
  10. ^ a b Уилсон, Робин (2002). Достаточно четырех цветов . Лондон: Penguin Books. ISBN 978-0-691-11533-7.
  11. ^ Ходжес, Эндрю (1992). Алан Тьюринг: Загадка . Случайный дом .
  12. ^ Тревор Р. Ходкинсон; Джон А. Н. Парнелл (2007). Реконструкция Древа жизни: систематика и систематика крупных и видовых таксонов . CRC PressINC. п. 97. ISBN 978-0-8493-9579-6.
  13. ^ "Проблемы премии тысячелетия" . 2000-05-24 . Проверено 12 января 2008 .
  14. ^ AS Troelstra; Х. Швихтенберг (27.07.2000). Основная теория доказательств . Издательство Кембриджского университета. п. 186. ISBN. 978-0-521-77911-1.
  15. ^ Сэмюэл Р. Басс (1998). Справочник по теории доказательств . Эльзевир. п. 13. ISBN 978-0-444-89840-1.
  16. ^ Франц Баадер; Герхард Брюка; Томас Эйтер (16.10.2001). KI 2001: Достижения в области искусственного интеллекта: совместная немецко-австрийская конференция по ИИ, Вена, Австрия, 19-21 сентября 2001 г. Материалы . Springer. п. 325. ISBN 978-3-540-42612-7.
  17. ^ Brotherston, J .; Bornat, R .; Кальканьо, К. (январь 2008 г.). «Циклические доказательства завершения программы в логике разделения». Уведомления ACM SIGPLAN . 43 (1). CiteSeerX 10.1.1.111.1105 . DOI : 10.1145 / 1328897.1328453 . 
  18. ^ Графы на поверхностях , Боян Мохар и Карстен Томассен , издательство Университета Джона Хопкинса, 2001

Дальнейшее чтение [ править ]

  • Норман Л. Биггс (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.

Внешние ссылки [ править ]

  • СМИ, связанные с дискретной математикой на Викискладе?
  • Дискретная математика в Архиве математики utk.edu, где есть ссылки на учебные планы, учебные пособия, программы и т. Д.
  • Центр Айовы: Программа электрических технологий Дискретная математика для электротехники .