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

Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Дискретная математика»  – Новости  · газеты  · книги  · ученый  · JSTOR (Февраль 2015 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Логика

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

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

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

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

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

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

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

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

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

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

Вероятность

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

Теория чисел

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

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

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

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

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

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

Геометрия

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

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

Топология

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

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

ПЕРТ диаграммы, подобные этой, обеспечивают технику управления проектами, основанную на теория графов.

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

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

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

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

Теория социального выбора около голосование. Подход к голосованию, основанный на головоломках: теория голосования.

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

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

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

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

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

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

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

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

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

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

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

Рекомендации

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

• Норман Л. Биггс (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-4a в штучной упаковке. Эддисон-Уэсли Профессионал. 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.
• Веерараджан, Т. (2007), Дискретная математика с теорией графов и комбинаторикой, Тата Макгроу Хилл

внешняя ссылка

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