Дискретная математика что это
Перейти к содержимому

Дискретная математика что это

  • автор:

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

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

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

Знаменитая задача из области теории графов — проблема четырёх красок. Кеннет Аппель и Вольфганг Хакель решили её в 1976 г. [1]

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

Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена.
Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники.
Эта отметка установлена 30 августа 2011.

  • Математическая логика
  • Математическая кибернетика
  • Теория функциональных систем
  • Общая алгебра
  • Комбинаторика (отдельные разделы)*
  • Комбинаторная логика
  • Сортировки
  • Теория графов
  • Машинная арифметика
  • Теория алгоритмов
  • Теория игр
  • Теория кодирования
  • Теория автоматов
  • Теория множеств (отдельные разделы)
  • Теория чисел (отдельные разделы)
  • Теория формальных грамматик
  • Вычислительная геометрия
  • Теория булевых функций
  • Логическое программирование
  • Функциональное программирование
  • λ-исчисление
  • Булева алгебра
  • Комбинационная логика
  • Секвенциальная логика
  • Асинхронная логика
  • Математическая лингвистика
  • Теория искусственного интеллекта

Примечания

  1. ↑Wilson Robin Four Colors Suffice. — Penguin Books, 2002. — ISBN 0-691-11533-8

Литература

  • Андерсон Джеймс. Дискретная математика и комбинаторика = Discrete Mathematics with Combinatorics. — М .: «Вильямс», 2006. — С. 960. — ISBN 0-13-086998-8
  • Белоусов А. И., Ткачев С. Б. Дискретная математика. Серия: Математика в техническом университете. Изд-во: МГТУ им. Н. Э. Баумана, 2001.- 744 с. ISBN 5-7038-1769-2, 5-7038-1270-4
  • Виленкин Н. Я. Комбинаторика. — М ., 1969.
  • Ерусалимский Я. М.Дискретная математика. — М ., 2000.
  • Иванов Б. Н. Дискретная математика. Алгоритмы и программы. Издательство: Физматлит, 2007. — 408 с. ISBN 978-5-9221-0787-7
  • Капитонова Ю. В., Кривой С. Л., Летичевский А. А., Луцкий Г. М. Лекции по дискретной математике. — СПб. : БХВ-Петербург, 2004. — С. 624. — ISBN 5-94157-546-7
  • Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. — М ., 1963. — С. 486.
  • МЭС (1995), — М., БРЭ.
  • Новиков Ф.А. Дискретная математика для программистов. — 2-е изд. — СПб. : «Питер», 2005. — С. 364. — ISBN 5-94723-741-5
  • Редькин Н. П. Дискретная математика. Издательство: Лань, 2006. — 96 с. ISBN 5-8114-0522-7
  • Романовский И. В. Дискретный анализ. — 4-е изд. — СПб. : Невский Диалект; БХВ-Петербург, 2008. — С. 336.
  • Яблонский С. В.Введение в дискретную математику. — М .: Наука, 1979. — С. 272.

См. также

  • Информатика
  • Исследование операций

Ссылки

  • Журнал «Дискретная математика»
  • Дискретная математика — дискретная математика и математическая кибернетика в МГУ.
  • Дискретная математика: алгоритмы — дискретная математика в СПбГУ ИТМО
  • http://www.simvol.biz/uploadfiles/File/sostav/books/Diskret_mat2.pdf Ю. П. Шевелёв. Дискретная математика. Часть 2. Теория конечных автоматов. Комбинаторика. Теория графов. Томск 2003.

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

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

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

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

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

  • Логика
  • Теория множеств
  • Отношения
  • Функции
  • Комбинаторика
  • Графы

ЛОГИКА

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

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

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

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

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

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

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

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

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

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

Например, 10 < 4 — ЛОЖЬ, а 10 > 4 — ИСТИНА.

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

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

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

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

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

Три закона

Теперь введем суждение R — утверждение, которое может быть как истинным, так и ложным.

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

Законы де Моргана

Логическая формула

Включает суждения, выражения в скобках и следующие символы:

Квантификаторы

Что такое квантификатор? Квантификатор в естественном языке — это слово, которое используется для обозначения количественных отношений (сколько). Например: все, несколько, много, мало, большинство и нисколько.

ТЕОРИЯ МНОЖЕСТВ

Что такое множество?

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

Например, если A = и B = и порядок неважен, то A = B

Разобравшись в этом, мы можем дать более точное определение множества — это коллекция различных, строго определенных объектов.

Иногда нам нужно определить бесконечное множество. Проблема очевидна: мы не сможем записать все его элементы. Значит, мы можем определить множество с помощью характерных признаков всех его элементов.

Операции над множествами

ОТНОШЕНИЯ

Логика отношений изучает отношения между математическими объектами. Мы можем установить связь с N элементами (где N — положительное натуральное число).

Бинарное отношение — это отношение между двумя элементами (объектами). Формально мы можем записать любое отношение между x и y так: x ~ y

Свойства бинарных отношений

Числовые множества

ФУНКЦИИ

Функция — это отношение, которое присваивает переменным новые значения. То есть это отношение между множеством А и множеством В.

Свойства

Функциональная композиция

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

КОМБИНАТОРИКА

Простыми словами, это наука о счете.

Перестановки

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

Комбинации

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

Блок-схема алгоритма

ГРАФЫ

Что такое граф?

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

Если вам понравилась эта статья, приглашаю почитать также мой блог:

Читать ещё:

Научный форум dxdy

Правильно ли я понимаю, что дискретная математика работает с конечными объектами? А если и встречаются бесконечные объекты, то изучаются некоторые их конечные части.

Относятся ли к дискретной математике
теория множеств,
общая алгебра,
теория чисел ?

Re: Что такое дискретная математика?
09.02.2011, 17:11
Ерусалимский Я.М. в «Дискретная математика: теория, задачи, приложения», «Введение писал(а):

Математика как наука, естественно, от рождения делится на дискретную и континуальную математику. Что мы относим к континуальной математике? Все, что явно или неявно содержит идеи теории пределов и непрерывности. Все остальное — дискретная математика (т.е. арифметика, алгебра, теория множеств и общая теория отображений, математическая логика, комбинаторный анализ, теория алгоритмов и многое другое).
В учебный предмет «Дискретная математика» включают только тот круг вопросов, который можно озаглавить «Теоретические основы компьютерной математики».

Поэтому лично я думаю, что теория чисел относится к дискретной математике — используемые результаты из ТФВП и ТФКП все же не составляют основного ее содержания.

Re: Что такое дискретная математика?
09.02.2011, 17:20

А вообще все эти деления и классификации всегда довольно условны. Ну какая разница, отнесем ли мы эти предметы к ДМ или нет? что от этого поменяется?

Re: Что такое дискретная математика?
09.02.2011, 17:51
PAV в сообщении #411020 писал(а):
какая разница, отнесем ли мы эти предметы к ДМ или нет? что от этого поменяется?

Как это какая? Учебные планы менять надо будет!
Re: Что такое дискретная математика?
09.02.2011, 18:56

Я вот теорию множеств и алгебру не отношу к дискретной математике, а с теорией чисел сомневаюсь. Интересует мнение специалистов по дискретной математике. В чем её суть?

Re: Что такое дискретная математика?
09.02.2011, 18:58

Боюсь, что «дискретная математика» — это чисто организационное образование. Сюда «свалили» всё, что не входит в традиционные для технических ВУЗов курсы математики, но считается нужным для «компьютерных дисциплин». И придумали «обоснование», как у Ерусалимского.

Re: Что такое дискретная математика?
10.02.2011, 08:12

Полностью согласна с Someone. Собрали всего помаленьку и назвали Дискретной математикой. Тут и теория высказываний, булева алгебра, предикаты, множества и графы, еще и теория автоматов и многое другое.

Re: Что такое дискретная математика?
10.02.2011, 09:40

Есть разделы, которые не задумываясь можно назвать ДМ, например комбинаторика. Алгебру ДМ я бы называть поостерегся, ну а теорию множеств называть ДМ смешно — именно теория множеств является основой того, что было здесь названо «континуальной математикой».

Как насчет того, чтобы определить дискретность математики, как меру на множестве математических теорий?

Re: Что такое дискретная математика?
10.02.2011, 14:02

Из той же серии. Мои преподы в универе вводили следующее разделение: всё, что использует топологию и пределы (т.е. от матана до функана и дальше), называется высшей математикой; всё остальное — элементарной. Вот такая вот классификация.

Re: Что такое дискретная математика?
11.02.2011, 14:12
Цитата:
Интересует мнение специалистов по дискретной математике. В чем её суть?

А кто такой «специалист по дискретной математике»? Я вижу в дискретной математике такие вещи как теоретические аспекты любых вычислительных алгоритмов, теорию графов, логику, комбинаторику, туда же можно сунуть задачи оптимизации. Хотя как же так! Этим занимается уже математическое программирование. Но нет, грани настолько условны, что сказать точно, кто чем занимается весьма трудно. Может, например, получиться, что задача по комбинаторике, а ответ получается в виде интеграла, исследовать который нужно методами матанализа.

Re: Что такое дискретная математика?
11.02.2011, 14:54

Рискну высказать свое ИМХО, что более-менее точным критерием принадлежности к дискретной математике является, если можно так сказать, «конструктивность» изучаемых объектов. То есть их конечное число, они могут быть точно описаны конечной записью, и задачи обычно в теории допускают точное «переборное» решение. Как-то так.

— Пт фев 11, 2011 16:19:31 —

i Тема перенесена из «Помогите решить/разобраться» в корневой раздел

Re: Что такое дискретная математика?
12.02.2011, 19:49

По-моему, конструктивистская математика — это ортогональное понятие. Вроде у конструктивистов и для понятий из классического матанализа (производные там всякие) конструкции есть.

Re: Что такое дискретная математика?
17.02.2011, 13:37

В свое время Демокрит, один из отцов гипотезы о дискретном основании природы, попробовал создать дискретную математику. Сегодня ей соответствует целочисленная арифметика. Там всегда была и всегда будет одна нерешенная задача, а именно — что делать с остатком от целочисленного деления. Математика не может дать ответа на этот вопрос. Поэтому с дискретной матаматикой у Демокрита не получилось.
Если предположить мир дискретным, то природа обязана давать на этот вопрос ответ. Если этот мир дискретный, то любая энергия должна состоять из квантов. Предположим, что при соударении двух молекул газа их кинетическая энергия в 11 квант должна разделиться между ними пополам. Тогда возможны 3 варианта деления (5 и 6 квантов) (6 и 5 квантов) (5 и 5 квантов и квант в остатке, не присоединенный ни к одной из молекул). Последний вариант нарушает закон сохранения энергии. А два первых требуют от природы случайного решения, что она по всей видимости и делает.
Согласившись с этой гипотезой, можно насмешить 99,999. % мехматовцев, но зато получить строгий ответ по крайней мере на несколько вопросов:
1) откуда в природе берется случайное
2) почему между квадратами скоростей (кинетичекими энергиями) частиц газа в термодинамическом процессе устанавливается нормальное распределение
3) почему практически все процессы в природе необратимы.

! PAV:
Предупреждение за оффтопик! Ваше сообщение: (а) не относится к вопросу темы; (б) спорное и малосодержательное

Re: Что такое дискретная математика?
24.02.2018, 11:24

Извиняюсь, что поднимаю древнюю тему. IMHO, пока существует понятие «дискретная математика», тема будет актуальна.

$\operatorname</p> <p>Есть нетопологический оператор замыкания. Он получается, если из определения топологического оператора замыкания выбросить аксиому A\lor B \leq (\operatornameA)\lor(\operatornameB).$» /> Точное определение можно посмотреть в Википедии. Нетопологический оператор замыкания определён для предпорядка. Часто рассматривается его частный случай, когда в качестве этого предпорядка взято включение множеств. Примеры нетопологического оператора замыкания: замыкание по алгебраической структуре, замыкание по системе вывода (замыкание по дедукции). Многие понятия топологии обобщаются для нетопологического оператора замыкания. В частности, понятие непрерывной функции обобщается.</p> <p>У меня сложилось впечатление, что теория порядков, алгебра, логика относятся к дискретной математике. Но непрерывность принадлежит непрерывной математике. Нетопологический оператор замыкания ещё принадлежит дискретной математике или уже нет? Хотелось бы услышать ответ от сторонников деления математики на дискретную и непрерывную.</p> <p><b>Re: Что такое дискретная математика?</b><br /> 24.02.2018, 11:39</p> <p>Последний раз редактировалось eugensk 24.02.2018, 11:57, всего редактировалось 1 раз.</p> <h2>Дискретная математика что это</h2> <p>Печатается по решению учебно-методического комиссии Экономического отделения Набережночелнинского филиала федерального государственного автономного образовательного учреждения высшего профессионального образования «Казанский (Приволжский) федеральный университет», протокол № 5 от «20» октября 2014 г.</p> <p>Дискретная математика – область математики, изучающая дискретные математические объекты и структуры. Ее элементы возникли в глубокой древности. С незапамятных времен известны комбинаторно-логические задачи, решение которых связано с перебором комбинаций дискретных объектов и логическим анализом возникающих вариантов. Некоторые из них сохранились до нашего времени в занимательной математике в виде задач-головоломок. Дискретные системы с древнейших времен применяются в вычислительной практике. Широко известны изобретенные в древности различные системы представления чисел и связанные с ними алгоритмы выполнения арифметических операций, решения уравнений и т.д., повсеместно были распространены дискретные вычислительные приспособления: абак, различные виды счетов.</p> <p>Развиваясь параллельно с другими разделами математики, элементы дискретной математики являлись их составной частью. Важнейшие примеры дискретных математических объектов: натуральный ряд чисел; конечное множество элементов произвольной природы; функция (отображение) из конечного множества в конечное множество; слово (последовательность символов) и формальный язык (множество слов) в конечном алфавите; конечный граф и другие. Содержательно дискретный объект обычно мыслится как состоящий из строго отделенных друг от друга неделимых частей. Объекты рассматривают как дискретные также в тех случаях, когда по каким-либо причинам отвлекаются от присущих им свойств непрерывности. Следует подчеркнуть, что деление математики на «непрерывную» и «дискретную» весьма условно, т.к. вся математика едина и пронизана глубокими аналогиями.</p> <p>Дискретная математика – область математики, занимающаяся изучением свойств структур конечного характера, которые возникают как внутри математики, так и в её приложениях.</p> <p>Само деление математики на классическую и дискретную в значительной мере условно, поскольку, например, с одной стороны, происходит активная циркуляция идей и методов между ними, а с другой – часто возникает необходимость исследования моделей, обладающих как дискретными, так и непрерывными свойствами одновременно.</p> <p>Начиная с середины XX в. в нашу жизнь бурно вошли и заняли доминирующее место информационные системы различного назначения. Определяющими в таких системах являются информационно-логические, принципиально дискретные процессы решения разнообразных задач. Для этих процессов не существенны место и время их решения, они мало зависят от преобразования энергии и вещества. Классической высшей математики недостаточно и для моделирования кибернетических и интеллектуальных систем. Для описания главных систем информационного периода и появилась новая математика, которую называют в России дискретной математикой (выделяется дискретность структуры информации, собственно информационной системы и ее функционирования); в США – Computer Science (на первое место выдвигается техническая сторона дела – компьютеры); в Западной Европе – информатикой (акцент делается на информационные процессы).</p> <p>Несмотря на наличие ряда учебников по дискретной математике, студентам предлагается новое учебное пособие. Появление учебного пособия «Введение в дискретную математику: теория и практика» связано в первую очередь с появлением учебной программой по дискретной математике в рамках реализации основных образовательных программ по направлениям «Прикладная информатика», «Прикладная математика и информатика», «Бизнес-информатика» в НЧИ КФУ, но, кроме этого, в пособии учтены некоторые современные тенденции развития преподавания и научных исследований за рубежом, а также личный опыт автора, преподающего дискретную математику.</p> <p>В учебном пособии материал разбит по главам, в которых приводятся исторические факты и материалы о возникновении тех или иных задач и путей их решения. В доступной и весьма увлекательной форме автор рассказывает о фундаментальных понятиях дискретной математики – о логике, множествах, графах, отношениях и булевых функциях. Теория изложена кратко и иллюстрируется многочисленными простыми примерами, что делает ее доступной даже школьнику. Пособие состоит из четырех разделов: элементы теории множеств, алгебраические системы и теория кодирования, математическая логика, комбинаторика, теория графов. Каждый раздел учебного пособия можно рассматривать как самостоятельный курс. Приведенные в учебном материале примеры и задачи позволяют успешно овладеть знаниями по изучаемой дисциплине. В пособии представлены решения некоторых задач, а также задачи для самостоятельного решения. К задачам прилагаются, если это необходимо, чертежи и рисунки, исторические факты. После каждой главы рассматривается приложение описанных методов к информатике. Есть и решения некоторых задач, а также задачи для самостоятельного решения. К задачам прилагаются, если это необходимо, чертежи и рисунки.</p> <p>Книга представляет собой учебное пособие для студентов университетов, полностью соответствующее программе курса «Дискретна математика» для направлений «Прикладная информатика», «Прикладная математика и информатика», «Бизнес-информатика». Может быть использовано студентам смежных специальностей и специалистами в области теоретической и прикладной информатики, программистами и разработчиками компьютерных систем.</p> <div class='yarpp yarpp-related yarpp-related-website yarpp-template-list'> <!-- YARPP List --> <div>Похожие публикации:</div><ol> <li><a href=Как добавить кнопки на форму с

  • Как объединить ячейки в 1с
  • Как скачать файл по ссылке
  • Как установить астра линукс

    • Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *