Что изучает дискретная математика
Дискретная математика
Дискре́тная матема́тика — область математики, занимающаяся изучением дискретных структур, которые возникают как в пределах самой математики, так и в её приложениях.
К числу таких структур могут быть отнесены конечные группы, конечные графы, а также некоторые математические модели преобразователей информации, конечные автоматы, машины Тьюринга и так далее. Это примеры структур конечного (финитного) характера. Раздел дискретной математики, изучающий их, называется конечной математикой. Иногда само это понятие расширяют до дискретной математики. Помимо указанных конечных структур, дискретная математика изучает некоторые алгебраические системы, бесконечные графы, вычислительные схемы определённого вида, клеточные автоматы и т. д. В качестве синонима иногда употребляется термин «дискретный анализ».
Содержание
Разделы дискретной математики
Примечания
Литература
См. также
Ссылки
Полезное
Смотреть что такое «Дискретная математика» в других словарях:
ДИСКРЕТНАЯ МАТЕМАТИКА — то же, что конечная математика … Большой Энциклопедический словарь
дискретная математика — то же, что конечная математика. * * * ДИСКРЕТНАЯ МАТЕМАТИКА ДИСКРЕТНАЯ МАТЕМАТИКА, то же, что конечная математика (см. КОНЕЧНАЯ МАТЕМАТИКА) … Энциклопедический словарь
ДИСКРЕТНАЯ МАТЕМАТИКА — конечная математика, раздел математики, занимающийся изучением св в объектов конечного характера. К их числу могут быть отнесены, напр., конечные группы, конечные графы, нек рые матем. модели преобразователей информации. Д. м. теоретич. основа… … Большой энциклопедический политехнический словарь
ДИСКРЕТНАЯ МАТЕМАТИКА — то же, что конец ноя математика … Естествознание. Энциклопедический словарь
«Дискретная математика» — научный журнал РАН, с 1989, Москва. Учредитель (1998) Отделение математики РАН. 4 номера в год … Энциклопедический словарь
Теория функциональных систем (дискретная математика) — У этого термина существуют и другие значения, см. Теория функциональных систем (значения). Теория функциональных систем раздел дискретной математики, занимающийся изучением функций, описывающих работу дискретных преобразователей. В теории… … Википедия
МАТЕМАТИКА — (греч. mathematike от mathema наука), наука, в которой изучаются пространственные формы и количественные отношения. До нач. 17 в. математика преимущественно наука о числах, скалярных величинах и сравнительно простых геометрических фигурах;… … Большой Энциклопедический словарь
Математика — Евклид. Деталь «Афинской школы» Рафаэля Математика (от др. греч … Википедия
математика — и; ж. [греч. mathēmatikē] 1. Наука о количественных отношениях и пространственных формах действительного мира. Высшая м. Элементарная м. Прикладная м. Законы математики. // Учебный предмет, изучающий эту науку. Экзамен по математике. Преподавать… … Энциклопедический словарь
Математика гармонии — Эта статья предлагается к удалению. Пояснение причин и соответствующее обсуждение вы можете найти на странице Википедия:К удалению/22 ноября 2012. Пока процесс обсуждени … Википедия
Дискретные структуры: матан для айтишников
Посмотришь на любую программу обучения по IT-специальности, и тут же увидишь дисциплину «Дискретная математика» (возможно, под другим названием), обычно для перво- или второкурсников. И её наличие вполне разумно, поскольку дискретная математика и непрерывная математика (представленная на первом курсе институтов с незапамятных времён математическим анализом) — две грани единой Математики, — красивой, могучей науки.
Хотя раньше такого понятия, как «дискретная математика» вовсе не было, это не значит, что не возникало дискретных задач: Абель, Дирихле, Фибоначчи, Эйлер, чьи имена возникают по ходу изучения дискретной математики, — отнюдь не наши современники! Но просто в те времена для выделения самостоятельной ветви математики ещё не сложилось критической массы задач и приёмов, не было видно взаимосвязей между ними. А большое количество плодотворных взаимосвязей между, на первый взгляд, различными понятиями, — то, что математики в своей науке очень ценят.
Ну хорошо, математикам всё математическое интересно. А зачем дискретная математика программисту?
Зачем это айтишнику
Во-первых, многие идеи, которые особенно ярко иллюстрируются на дискретных задачах, неотъемлемы и для информатики. Взять, хотя бы, фундаментальные понятия рекурсии и индукции.
Рекурсия — это, дословно, возврат, обращение к самому себе. Хорошо известные вездесущие числа Фибоначчи проще всего определяются рекурсивно: первые два числа Фибоначчи равны единице, а каждое следующее число равно сумме двух своих предшественников: 1,1,2,3,5,8,… Таким образом, для вычисления очередного числа мы обращаемся к уже рассчитанным числам такого же вида. Трудно представить, как можно изучить функциональное программирование, да и многое из других областей информатики, не освоившись хорошо с рекурсией. Очень близкий процесс к рекурсии — это индукция, способ доказательства математических утверждений, при котором в доказательстве сложных случаев мы опираемся на более простые. Параллели с рекурсией очевидны, и действительно, обычное дело, когда индуктивное доказательство существования какого-то объекта можно переформулировать в описание рекурсивного способа построения этого объекта.
Раз речь зашла о таких фундаментальных вещах, как индукция и рекурсия, не могу не сказать, что многие приёмы, которые очень хорошо видны на примерах из дискретной математики, эффективны в математике в целом. Это не только индукция, но и принцип Дирихле, принцип выбора по среднему значению и другие.
Следующий элемент, без которого информатику нельзя представить — это графы. Простейшие алгоритмы на графах обязательно входят в любой, даже самый вводный, курс по алгоритмам. Скажем, с понятием гамильтонова цикла связана одна из классических задач информатики, задача коммивояжёра.
Ещё одно архиважное умение — считать точно и оценивать приблизительно количества. Например, как вычислить количество раз, которые выполняется операция сравнения в цикле:
Или вот ещё пример. Нужно из списка из 100 товаров выбрать 20, так, чтобы их суммарная стоимость была ровно 2000 рублей («без сдачи»). Это вариант классической задачи о рюкзаке. Допустим, ваш коллега, подумав ночь, предложил решать задачу перебором: перебрать всевозможные наборы из двадцати товаров, и, как только в ходе перебора возникнет нужный набор, выдать его в качестве ответа. Между прочим, характеристика «переборный» далеко не всегда ставит клеймо на алгоритме. Всё зависит от размера входных данных. Так вот, как прикинуть, удастся ли за разумное время решить перебором эту задачу выбора 20 объектов из 100?
Наконец, для современного «дизайнера алгоритмов» обязателен к пониманию и вероятностный метод. Это общий метод, позволяющей решать многие задачи в современной комбинаторике. Очень часто наилучшие решения задач, известные на сегодняшний день, получены именно этим методом. Для практика же овладение этим методом полезно постольку, поскольку вероятностные алгоритмы прочно заняли место в современной информатике. И при анализе работы таких алгоритмов очень помогает интуиция, развитая в ходе изучения вероятностного метода.
Онлайн-курс «Дискретные структуры»
С верой в то, что перечисленные понятия из дискретной математики действительно не помешают любому программисту, а, скорее, помешает их незнание, я читаю соответствующий курс на факультете ФИВТ МФТИ. А недавно у меня появилась возможность сделать онлайн-курс, чем я с радостью воспользовался. Записаться на него можно по ссылке. Главное, чего я пожелаю всем записавшимся: не побоявшись трудностей, пройти курс до самого конца, и получить заслуженное звание Дипломированного Дискретчика. В общем, чтобы MOOC прошёл без мук и обогатил знаниями! Да и собственная корысть у меня тут тоже есть: чем больше онлайн-учеников у меня будет, тем большему я смогу научиться, читая обсуждения и наблюдая статистику решения задач. Ведь учиться учить тоже никогда не поздно!
Какие знания потребуются
Для прохождения первых двух модулей потребуются только школьные знания. Третий модуль потребует знание основ математического анализа на уровне «что такое предел» и «какая из функций x 20 или 2 x растёт быстрее (чему равны производные функций)». Для последних трёх модулей понадобится представление о том, что такое вероятность, условная вероятность, математическое ожидание, дисперсия. Также хорошо бы знать, что такое базис и размерность линейного пространства. Если с вероятностью и линейной алгеброй вы не знакомы, можно записаться заодно на эти вводные курсы. Тогда как раз, к моменту, когда нам потребуются эти знания, они у вас будут.
Post scriptum
Меня можно было бы упрекнуть в конфликте интересов, всё-таки я математик, и, естественно, хочу приобщить к своей секте как можно больше завсегдатаев Хабра. В своё оправдание могу сослаться на этот ответ на Quora. Под большей частью тем, перечисленных в этом ответе, я готов лично подписаться, в онлайн-курс многие из них вошли. Ещё сошлюсь на подборку мнений яндексоидов.
Основы дискретной математики
Привет, хабр. В преддверии старта базового курса «Математика для Data Science» делимся с вами переводом еще одного полезного материала.
Об этой статье
Эта статья содержит лишь малую часть информации по заявленной теме. Рассматривайте ее как вводный курс перед началом всестороннего изучения предмета. Надеюсь, вы найдете в ней полезную информацию. Знание дискретной математики помогает описывать объекты и задачи в информатике, особенно когда дело касается алгоритмов, языков программирования, баз данных и криптографии. В дальнейшем я планирую подробнее раскрыть темы, затронутые в этой статье. Приятного чтения!
ЧТО ТАКОЕ ДИСКРЕТНАЯ МАТЕМАТИКА?
Это область математики, изучающая объекты, которые могут принимать только уникальные отдельные значения.
Мы рассмотрим пять основных разделов в следующем порядке.
ЛОГИКА
Что такое логика?
Это наука о корректных рассуждениях. Мы будем использовать приемы идеализации и формализации. Неформальная логика изучает использование аргументов в естественном языке.
Формальная логика анализирует выводы с чисто формальным содержанием. Примерами формальной логики являются символическая логика и силлогистическая логика (о которой писал Аристотель).
Начнем с азов. Рассмотрим следующее высказывание на естественном языке:
«Если я голоден, я ем».
Пусть «голоден» будет посылкой A, а «ем» — следствием B. Попробуем формализовать:
A => B (то есть из A следует B)
NB. Посылка и следствие являются суждениями.
Логические выражения
Для нас важна форма, а НЕ содержание. Значение будет истинным, если оно соответствует форме.
Например, 10 4 — ИСТИНА.
Логические операции
Суждение P — это утверждение, которое может быть как истинным, так и ложным.
Обозначим истинное значение P единицей (1), а ложное значение P нулем (0).
Существует другое суждение; обозначим истинное значение Q единицей (1), а ложное значение Q нулем (0).
Рассмотрим логические операции с суждениями, значение которых истинно. Они могут сами образовывать истинные значения путем выполнения соответствующих операций над истинными значениями.
Что изучает дискретная математика
Что же такое «Дискретная математика»? Чем она отличается от обычной математики? Почему имеет широкое применение в информатике? Будем разбираться в этих и других вопросах, касательно этой интересной и очень важной темы в современном мире [1].
Математика в переводе с греческого означает изучение, наука, исторически возникла на основе измерения формы объектов, подсчёта чего-либо и т.д. Люди считали овец в своих стадах, высчитывали сколько материала понадобится для строительства, сейчас математика используется во многих науках узкого и широкого направлениях: экономика, физика, астрономия, информатика и так далее [2].
Дискретная математика изучается столько же, сколько и обычная, частью которой и является. Термин «дискретный» означает прерывистый и имеет противоположный по свойствам термин «непрерывный».
Если открыть кран так, чтобы текла струя воды, то поток будет описывать некоторую непрерывную прямую. Если сделать так, чтобы из крана капали капли, то это будет дискретная совокупность. Причём не важно, как часто капают капли. Главное, что нас интересует, то, что через какое-то время появляется новая капля, которая не соединена с первой в пространстве. В математике нет чёткой границы между понятиями «дискретный» и «непрерывный».
Дискретная математика используется нами повседневно, мы совершаем расчёты, выводы и операции даже не подозревая, что это часть такой интересной науки. Школьные знания, которые просты и понятны нам, людям, которые уже не сидят за партой, предстают для нас с новыми названиями, описаниями с точки зрения высшей математики. Это лишний раз подтверждает, что дискретная математика позволяет решать не только простейшие задания, но и те, над которыми трудятся доктора наук [3].
На момент появления первых компьютеров большинство электронных устройств, а именно: радио, телевизоры, магнитофоны и другие, было аналоговым. Это значит, что в данных устройствах использовались непрерывные сигналы. А при проектировании подобных устройств использовались методы непрерывной математики.
Первые ЭВМ были невероятно большого размера, они занимали целые здания, и были исключением среди электронных устройств того времени потому, что в них как раз и нужна была дискретная математика. Со временем ЭВМ превратились из больших и пугающих машин в те, что могут помещаться в отдельной комнате, затем на рабочем столе, а после в обыденные и незаменимые «Мобильники». Теперь мы чуть ли не каждый день имеем дело с электроникой, использующей достижения дискретной математики. Почти все современные устройства являются цифровыми: от фотоаппаратов и видеокамер до интернета и спутникового телевидения. Уже полвека дискретная математика является важным компонентом компьютеров. А значит, она необходима и в информатике [4–6].
Информатика – это наука, которая изучает компьютер, автоматическую переработку информации, взаимодействие человека с компьютером.
Информация – это сведения об окружающем нас мире. С разных точек зрения, может быть рассмотрена по разному. Является функциональной и абстрактной, такой же, как категория материи, энергии и пространства, следовательно, информация тоже неисчерпаемая.
Информатика использовалась людьми с древних времён. Логика мышления компьютера не стала чем-то новым. Но то, что компьютер, в отличие от человека никогда не ошибается и справляется с рутиной работой с невероятной скоростью и без малейшей усталости, является тем, что упростило нашу жизнь. Таким образом, у нас появилось свободное время на новые духовные и культурные свершения.
Информатика стала отдельной наукой относительно недавно, потому что с появлением ЭВМ необходимость в специалистах, умеющих правильно обращаться с аппаратурой, стала важным критерием для работы с передовым оборудованием. В современном мире компьютеры и программы для них стали намного проще, и теперь многие люди являются пользователями-любителями. Но есть и те компьютеры, для которых нужны узкоспециализированные работники или другими словами пользователи-профессионалы. К примеру, они нужны для правильной эксплуатации таких устройств как: сонары на подводных лодках, солнечные панели на космических кораблях и лунных базах, роботы-спасатели, супер-компьютеры, устройства для информационной и компьютерной безопасности, и так далее [7, 8].
Как и информатика, дискретная математика помогает современному человеку находить общий язык с компьютером, программами. Эти две, относительно молодые, науки позволяют создавать «Умные» дома; машины, управляемые без человека; космические корабли и оборудование, для высадки на Марс и дальнейшего создания на нём колонии.
Информатика сейчас очень актуальная тема для исследования и создания всё более умных машин, роботов, программ, различных устройств.
Дискретная математика служит необходимым инструментом для реализации идей в информатике (и не только).
Такой раздел дискретной математики как теория множеств составляет базу, основу для изучения других разделов. Научившись составлять и задавать математически множества, элементы которых обладают характерным изучаемым свойством, в дальнейшем можно устанавливать, какие есть между ними отношения, выполнять операции над ними. В более сложных случаях применяют теорию нечётких множеств, применение которой позволяет правильно сделать выбор в пользу конкурентоспособного товара или услуги методом нечеткого предпочтения, поэтому эта теория используется в маркетологии, когда нужно проанализировать рынки экономических благ.
Математическая логика, теория предикатов, теория алгоритмов позволяют алгоритмизировать знания, накопленные математикой. Причём в дискретной математике есть базовые элементы, понятные и простые в применении, но есть и более сложные структуры, позволяющие математически точно отражать явления и процессы. Математическая логика нашла своё применение в различных областях деятельности человека, даже в тех, которые кажутся далёкими от математики – биологии, медицине, лингвистике, педагогике, психологии, экономике, технике, но, конечно же, стала базовым разделом дискретной математики в развитии вычислительной техники, в разработке искусственных языков для общения с компьютером. Средства математической логики позволяют решать логические задачи, имеющих много исходных условий, которые после перевода на язык алгебры логики становятся более обозримыми и удобными для дальнейшего анализа, приводящего к верному умозаключению.
Математическая логика непосредственно используется как для создания материальной части компьютера – «железа», так и для математического – программного обеспечения, то есть к релейно-контактным (переключательным) схемам и к языкам программирования и к самому процессу программирования и получающимся в результате этого программам. Математическая логика оказалась единственной математической наукой, методы которой стали мощнейшими инструментами познания во всех разделах информатики. Поэтому сколько-нибудь серьезное изучение информатики немыслимо без освоения основ математической логики.
Теория графов, математическая логика широко применяются в таких секторах экономики как эконометрика, логистика, математическое моделирование. Так в эконометрике, например, используются булевские переменные для построения регрессионных моделей по неоднородным данным и для анализа регрессионных моделей с переменной структурой. В логистике при необходимости задать маршруты или описать потоки, удобнее применить теорию графов, с помощью которой схему дорог можно изобразить, как ориентированный граф, и далее выбрать самый короткий маршрут. Теория графов позволяет описывать сетевые взаимодействия как на примитивном, бытовом уровне, так и при сетевом планировании огромных промышленных предприятий.
А такие разделы дискретной математики как булева алгебра, комбинаторика, различные математические алгоритмы, хэш-функции и квантовые алгоритмы позволяют шифровать и дешифровать огромное количество информации. Так в криптографии с помощью средств комбинаторики чаще всего просчитывается возможное число вариантов при исходных данных, а вот использование сложных хэш-функций приводит к невозможности по конечному результату – хэшу – вычислить начальный массив данных, обработанный хеш-функцией.
Комбинаторика является неотъемлемой частью создания искусственных нейронных сетей, способствующих развитию отраслей, связанных с искусственным интеллектом. Также применяется при анализе сложности различных алгоритмов, выборе оптимальной стратегии перебора.
Дискретная математика является основой проектирования многих электронных приборов. Появление математической теории управляющих систем стало новым шагом к продвижению новых разделов дискретной математики, таких как: теория сложности; теория надёжности схем; теория автоматов. Теория сложности говорит о том, что не все алгоритмы равны с точки зрения их практической пригодности и есть некая «функция сложности», которая «измеряет» качество этих алгоритмов. На базе теории алгоритмов возникла теория автоматов, то есть математических моделей, преобразующих дискретную информацию по шагам в дискретные моменты времени и формирующих получаемые результаты по шагам заданного алгоритма.
Методы дискретной математики и информатики дают возможность анализировать, исследовать и моделировать многие экономические, технические, технологические процессы.
Человек использует нужные ему инструменты для достижения всё более грандиозных проектов. Дискретная математика и информатика, в правильных руках, являются невероятно действенными и незаменимыми инструментами [9, 10].
Таким образом, мы получили ответы на поставленные вопросы и разобрались в некоторых тонкостях данных областей. Так же становится понятно, что данные темы лишь набирают обороты в современном мире и помогают учёным совершать новые открытия в разных областях, ведь компьютеры нужны и химикам, и археологам, и историкам, и многим исследователям других областей. Человечество открывает новое (науки, знания) и это новое помогает открыть нечто большее, что будет обыденным уже для следующих поколений.