Что изучает дискретная математика

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

Привет, хабр. В преддверии старта базового курса «Математика для Data Science» делимся с вами переводом еще одного полезного материала.

Об этой статье

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

ЧТО ТАКОЕ ДИСКРЕТНАЯ МАТЕМАТИКА?

Это область математики, изучающая объекты, которые могут принимать только уникальные отдельные значения.

Мы рассмотрим пять основных разделов в следующем порядке.

ЛОГИКА

Что такое логика?

Это наука о корректных рассуждениях. Мы будем использовать приемы идеализации и формализации. Неформальная логика изучает использование аргументов в естественном языке.

Формальная логика анализирует выводы с чисто формальным содержанием. Примерами формальной логики являются символическая логика и силлогистическая логика (о которой писал Аристотель).

Начнем с азов. Рассмотрим следующее высказывание на естественном языке:

«Если я голоден, я ем».

Пусть «голоден» будет посылкой A, а «ем» — следствием B. Попробуем формализовать:

A => B (то есть из A следует B)

NB. Посылка и следствие являются суждениями.

Логические выражения

Для нас важна форма, а НЕ содержание. Значение будет истинным, если оно соответствует форме.

Например, 10 4 — ИСТИНА.

Логические операции

Суждение P — это утверждение, которое может быть как истинным, так и ложным.

Обозначим истинное значение P единицей (1), а ложное значение P нулем (0).

Существует другое суждение; обозначим истинное значение Q единицей (1), а ложное значение Q нулем (0).

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

Источник

Дискретные структуры: матан для айтишников

Посмотришь на любую программу обучения по IT-специальности, и тут же увидишь дисциплину «Дискретная математика» (возможно, под другим названием), обычно для перво- или второкурсников. И её наличие вполне разумно, поскольку дискретная математика и непрерывная математика (представленная на первом курсе институтов с незапамятных времён математическим анализом) — две грани единой Математики, — красивой, могучей науки.

Хотя раньше такого понятия, как «дискретная математика» вовсе не было, это не значит, что не возникало дискретных задач: Абель, Дирихле, Фибоначчи, Эйлер, чьи имена возникают по ходу изучения дискретной математики, — отнюдь не наши современники! Но просто в те времена для выделения самостоятельной ветви математики ещё не сложилось критической массы задач и приёмов, не было видно взаимосвязей между ними. А большое количество плодотворных взаимосвязей между, на первый взгляд, различными понятиями, — то, что математики в своей науке очень ценят.

Ну хорошо, математикам всё математическое интересно. А зачем дискретная математика программисту?

Зачем это айтишнику

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

Рекурсия — это, дословно, возврат, обращение к самому себе. Хорошо известные вездесущие числа Фибоначчи проще всего определяются рекурсивно: первые два числа Фибоначчи равны единице, а каждое следующее число равно сумме двух своих предшественников: 1,1,2,3,5,8,… Таким образом, для вычисления очередного числа мы обращаемся к уже рассчитанным числам такого же вида. Трудно представить, как можно изучить функциональное программирование, да и многое из других областей информатики, не освоившись хорошо с рекурсией. Очень близкий процесс к рекурсии — это индукция, способ доказательства математических утверждений, при котором в доказательстве сложных случаев мы опираемся на более простые. Параллели с рекурсией очевидны, и действительно, обычное дело, когда индуктивное доказательство существования какого-то объекта можно переформулировать в описание рекурсивного способа построения этого объекта.

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

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

Ещё одно архиважное умение — считать точно и оценивать приблизительно количества. Например, как вычислить количество раз, которые выполняется операция сравнения в цикле:

Или вот ещё пример. Нужно из списка из 100 товаров выбрать 20, так, чтобы их суммарная стоимость была ровно 2000 рублей («без сдачи»). Это вариант классической задачи о рюкзаке. Допустим, ваш коллега, подумав ночь, предложил решать задачу перебором: перебрать всевозможные наборы из двадцати товаров, и, как только в ходе перебора возникнет нужный набор, выдать его в качестве ответа. Между прочим, характеристика «переборный» далеко не всегда ставит клеймо на алгоритме. Всё зависит от размера входных данных. Так вот, как прикинуть, удастся ли за разумное время решить перебором эту задачу выбора 20 объектов из 100?

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

Онлайн-курс «Дискретные структуры»

С верой в то, что перечисленные понятия из дискретной математики действительно не помешают любому программисту, а, скорее, помешает их незнание, я читаю соответствующий курс на факультете ФИВТ МФТИ. А недавно у меня появилась возможность сделать онлайн-курс, чем я с радостью воспользовался. Записаться на него можно по ссылке. Главное, чего я пожелаю всем записавшимся: не побоявшись трудностей, пройти курс до самого конца, и получить заслуженное звание Дипломированного Дискретчика. В общем, чтобы MOOC прошёл без мук и обогатил знаниями! Да и собственная корысть у меня тут тоже есть: чем больше онлайн-учеников у меня будет, тем большему я смогу научиться, читая обсуждения и наблюдая статистику решения задач. Ведь учиться учить тоже никогда не поздно!

Какие знания потребуются

Для прохождения первых двух модулей потребуются только школьные знания. Третий модуль потребует знание основ математического анализа на уровне «что такое предел» и «какая из функций x 20 или 2 x растёт быстрее (чему равны производные функций)». Для последних трёх модулей понадобится представление о том, что такое вероятность, условная вероятность, математическое ожидание, дисперсия. Также хорошо бы знать, что такое базис и размерность линейного пространства. Если с вероятностью и линейной алгеброй вы не знакомы, можно записаться заодно на эти вводные курсы. Тогда как раз, к моменту, когда нам потребуются эти знания, они у вас будут.

Post scriptum

Меня можно было бы упрекнуть в конфликте интересов, всё-таки я математик, и, естественно, хочу приобщить к своей секте как можно больше завсегдатаев Хабра. В своё оправдание могу сослаться на этот ответ на Quora. Под большей частью тем, перечисленных в этом ответе, я готов лично подписаться, в онлайн-курс многие из них вошли. Ещё сошлюсь на подборку мнений яндексоидов.

Источник

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

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

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

Содержание

Разделы дискретной математики

Примечания

Литература

См. также

Ссылки

Полезное

Смотреть что такое «Дискретная математика» в других словарях:

ДИСКРЕТНАЯ МАТЕМАТИКА — то же, что конечная математика … Большой Энциклопедический словарь

дискретная математика — то же, что конечная математика. * * * ДИСКРЕТНАЯ МАТЕМАТИКА ДИСКРЕТНАЯ МАТЕМАТИКА, то же, что конечная математика (см. КОНЕЧНАЯ МАТЕМАТИКА) … Энциклопедический словарь

ДИСКРЕТНАЯ МАТЕМАТИКА — конечная математика, раздел математики, занимающийся изучением св в объектов конечного характера. К их числу могут быть отнесены, напр., конечные группы, конечные графы, нек рые матем. модели преобразователей информации. Д. м. теоретич. основа… … Большой энциклопедический политехнический словарь

ДИСКРЕТНАЯ МАТЕМАТИКА — то же, что конец ноя математика … Естествознание. Энциклопедический словарь

«Дискретная математика» — научный журнал РАН, с 1989, Москва. Учредитель (1998) Отделение математики РАН. 4 номера в год … Энциклопедический словарь

Теория функциональных систем (дискретная математика) — У этого термина существуют и другие значения, см. Теория функциональных систем (значения). Теория функциональных систем раздел дискретной математики, занимающийся изучением функций, описывающих работу дискретных преобразователей. В теории… … Википедия

МАТЕМАТИКА — (греч. mathematike от mathema наука), наука, в которой изучаются пространственные формы и количественные отношения. До нач. 17 в. математика преимущественно наука о числах, скалярных величинах и сравнительно простых геометрических фигурах;… … Большой Энциклопедический словарь

Математика — Евклид. Деталь «Афинской школы» Рафаэля Математика (от др. греч … Википедия

математика — и; ж. [греч. mathēmatikē] 1. Наука о количественных отношениях и пространственных формах действительного мира. Высшая м. Элементарная м. Прикладная м. Законы математики. // Учебный предмет, изучающий эту науку. Экзамен по математике. Преподавать… … Энциклопедический словарь

Математика гармонии — Эта статья предлагается к удалению. Пояснение причин и соответствующее обсуждение вы можете найти на странице Википедия:К удалению/22 ноября 2012. Пока процесс обсуждени … Википедия

Источник

Почему школам важно уделять больше времени изучению дискретной математики

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

Большинство программ по математике [в США] для средних и старших классов следуют четко прописанной схеме:

Предалгебраические задачи → Алгебра 1 → Геометрия → Алгебра 2 → Тригонометрия/начала матанализа → Матанализ

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

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

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

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

Дискретная математика — это математика вычислительных процессов.

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

Дискретная математика больше всего приближена к задачам реального мира.

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

Дискретная математика — популярное направление большинства математических соревнований средней и старшей школы.

Видные математические олимпиады вроде MATHCOUNTS (средняя школа) и American Mathematics Competitions (старшие классы) включают значительное количество заданий по дискретной математике. В более сложных соревнования для старшеклассников, таких, как AIME, количество задач увеличивается еще сильнее. Ученики, не имеющие соответствующей базы знаний будут иметь гораздо меньше шансов на успех в таких соревнованиях. Один известный преподаватель, занимающийся подготовкой учеников к MATHCOUNTS, даже уделяет половину времени подготовке к заданиям по комбинаторике и теории вероятности. Настолько он считает их важными.

Дискретная математика развивает логическое мышление и учит техникам доказательства.

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

Дискретная математика — это весело.

Многие студенты, особенно одаренные и мотивированные находят алгебру, геометрию и даже методы матанализа скучными, не вызывающими живого интереса. Что же касается дискретной математики, то в ней такие темы встречаются редко. Когда мы интересуемся у учащихся их любимыми темами, большинство называет комбинаторику или теорию чисел. Самой непопулярной темой при этом оказывается геометрия. Иными словами, большинство студентов находят дискретную математику более интересной, чем алгебра или геометрия.

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

Источник

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

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

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

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

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

Содержание

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

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

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

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

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

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

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

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

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

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

Логика

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

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

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

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

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

Вероятность

Теория чисел

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

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

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

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

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

Геометрия

Топология

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

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

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

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

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

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

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

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

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

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

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

Источник