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

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

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

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

Знаменитая задача из области теории графов — проблема четырёх красок. Кеннет Аппель и Вольфганг Хакель решили её в 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

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

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

ФУНКЦИИ

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

Свойства

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

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

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

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

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

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

Комбинации

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

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

ГРАФЫ

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

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

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

Читать ещё:

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

Символом [math] \star [/math] помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.

Отношения

• Множества
• Определение отношения
• Композиция отношений, степень отношения, обратное отношение
• Рефлексивное отношение. Антирефлексивное отношение.
• Симметричное отношение
• Антисимметричное отношение
• Транзитивное отношение
• Отношение порядка
• Изоморфизмы упорядоченных множеств [math]^\star[/math]
• Отношение эквивалентности
• Транзитивное замыкание отношения
• Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
• Транзитивный остов

Булевы функции

• Определение булевой функции
• Побитовые операции [math]^\star[/math]
• Суперпозиции
• ДНФ
• Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна
• КНФ
• 2-SAT
• XOR-SAT [math]^\star[/math]
• Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
• Полином Жегалкина, преобразование Мёбиуса
• Полные системы функций. Теорема Поста о полной системе функций
• Представление функции класса DM с помощью медианы
• Выражение функции XOR через медианы
• Пороговая функция
• Троичная логика [math]^\star[/math]

Схемы из функциональных элементов

• Реализация булевой функции схемой из функциональных элементов
• Простейшие методы синтеза схем из функциональных элементов
• Шифратор и дешифратор
• Мультиплексор и демультиплексор
• Метод Лупанова синтеза схем
• Представление булевых функций линейными программами
• Нижняя оценка размера схем из функциональных элементов
• Cумматор
• Каскадный сумматор
• Двоичный каскадный сумматор
• Троичный сумматор [math]^\star[/math]
• Реализация вычитания сумматором
• Матричный умножитель
• Дерево Уоллеса
• Контактная схема
• Триггеры [math]^\star[/math]
• Квантовые гейты [math]^\star[/math]
• Квантовые алгоритмы [math]^\star[/math]

Представление информации

• Кодирование информации
• Представление целых чисел: прямой код, код со сдвигом, дополнительный код
• Представление вещественных чисел
• Представление символов, таблицы кодировок [math]^\star[/math]

Алгоритмы сжатия

• Алгоритм Хаффмана
• Алгоритм Хаффмана за O(n)
• Алгоритм Ху-Таккера [math]^\star[/math]
• Неравенство Крафта
• Неравенство Макмиллана
• Код Шеннона
• Оптимальный префиксный код с длиной кодового слова не более L бит [math]^\star[/math]
• Алгоритмы LZ77 и LZ78
• Алгоритм LZW
• Алгоритм LZSS [math]^\star[/math]
• Алгоритм LZMA [math]^\star[/math]
• Преобразование Барроуза-Уиллера и обратное ему
• Преобразование MTF
• Расстояние Хэмминга
• Избыточное кодирование, код Хэмминга
• Обнаружение и исправление ошибок кодирования
• Гамма-, дельта- и омега-код Элиаса [math]^\star[/math]
• Арифметическое кодирование
• Контекстное моделирование

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

Комбинаторные объекты

• Комбинаторные объекты
• Лексикографический порядок
• Коды Грея
• Коды Грея для перестановок
• Коды антигрея
• Монотонный код Грея
• Цепные коды
• Правильные скобочные последовательности

Генерация комбинаторных объектов

• Генерация комбинаторных объектов в лексикографическом порядке
• Получение номера по объекту
• Получение объекта по номеру
• Получение следующего объекта
• Получение предыдущего объекта [math]^\star[/math]
• Метод генерации случайной перестановки, алгоритм Фишера-Йетса
• Методы генерации случайного сочетания [math]^\star[/math]
• Методы получения случайных комбинаторных объектов

Подсчёт числа объектов

• Формула включения-исключения, подсчет числа беспорядков
• Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
• Лемма Бёрнсайда и Теорема Пойа
• Задача об ожерельях
• Числа Стирлинга первого рода
• Числа Стирлинга второго рода
• Символ Похгаммера
• Числа Белла
• Числа Эйлера первого и второго рода. Подъемы в перестановках [math]^\star[/math]
• Числа Каталана
• Конструирование комбинаторных объектов и их подсчет
• Подсчет деревьев
• Метод производящих функций

Свойства комбинаторных объектов

• Умножение перестановок, обратная перестановка, группа перестановок
• Действие перестановки на набор из элементов, представление в виде циклов
• Таблица инверсий
• Теорема Кэли
• Матричное представление перестановок
• Задача о минимуме/максимуме скалярного произведения
• Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП

Производящие функции

• Производящая функция
• Арифметические действия с формальными степенными рядами
• Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности
• Асимптотическое поведение последовательности, заданной рекуррентным соотношением
• Использование производящих функций для доказательства тождеств
• Производящие функции нескольких переменных
• Разложение рациональной функции в ряд
• Представление производящей функций в виде непрерывных дробей
• Задача о счастливых билетах
• Произведение Адамара
• Интегрирование/дифференцирование производящих функций
• Производящая функция Дирихле
• Решение рекуррентных соотношений
• Язык Дика
• Уравнение Лагранжа и теорема Лагранжа
• Асимптотика коэффициентов функций, связанных между собой уравнением Лагранжа
• Обращение Лагранжа
• Автокорреляционный многочлен

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

Санкт-Петербургский государственный университет

Факультет математики и компьютерных наук

Исследовательская лаборатория им. П. Л. Чебышева

Теоретическая информатика, дискретная математика и математическая логика

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

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

Теория сложности вычислений

Теория сложности вычислений, как правило, имеет дело не с конкретными алгоритмическими задачами, а с целыми классами задач, которые объединяются в зависимости от моделей вычислений и необходимых для решения этих задач ресурсов. Широкой публике известен вопрос о равенстве классов P и NP (одна из «проблем тысячелетия»): существует ли полиномиальный по времени алгоритм для конкретной задачи — распознавания тавтологий логики высказываний. Хотя до сих пор на многие естественные вопросы ответ еще не получен, известно внушительное количество неожиданных соотношений между сложностными классами (IP=PSPACE, MIP=NEXP, PCP-теорема и др.). Более точно сложность конкретных функций изучается на языке булевых схем (это теоретическая основа микросхем) — стандартной модели вычислений, в которой сложность можно сформулировать очень точно как количество требуемых операций.

В данном направлении работают Э.А. Гирш, Д.М. Ицыксон и А.С. Куликов.

Теория сложности доказательств

Все ли теоремы имеют короткие доказательства? Вопрос этот открыт даже в «простом» случае логики высказываний (в которой есть только логические переменные и связки), где он эквивалентен равенству сложностных классов NP и co-NP. Хотя в общем случае вопрос не разрешён, экспоненциальные нижние оценки известны для ряда конкретных систем доказательств. «Программа Кука» по изучению сложности доказательств состоит в получении новых экспоненциальных нижних оценок для всё более мощных систем доказательств. Концепции и методы, применяемые в этих системах, относятся к разнообразным областям математики: алгебре, геометрии, комбинаторике.

В данном направлении работают Э.А. Гирш и Д.М. Ицыксон .

Алгоритмы для NP-трудных задач

Многие возникающие на практике задачи (например, составление расписаний, доставка грузов, верификация аппаратного и программного обеспечения) являются NP-трудными. Это, в частности, означает, что мы до сих пор не знаем алгоритмов, которые решали бы эти задачи за приемлемое в худшем случае время. Тем не менее, эти задачи надо решать — к возможным подходам относятся «слабоэкспоненциальные» алгоритмы, параметризованные алгоритмы, приближенные алгоритмы.

В данном направлении работают И.А. Близнец и А.С. Куликов.

Вычислительная геометрия

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

В данном направлении работают К.В. Вяткина и Е.А. Храмцова.

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

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

— Математическая логика —

Одной из основных задач математической логики является разработка и изучение формальных моделей различного рода языковых явлений — от семантических и грамматических проблем в естественных языках до дедуктивных и алгоритмических свойств математических теорий и семантики языков программирования. В частности, на счету математической логики формализация понятий «доказательства» и «вычислимой функции», а также получение классических результатов о дедуктивной невыводимости (например, континуум-гипотезы в рамках аксиоматической теории множеств) и алгоритмической неразрешимости (скажем, элементарной теории групп). Логические методы позволяют достаточно точно описывать синтаксис и семантику различных языков, а затем успешно изучать их как математические объекты. Математическая логика интересуется как дедуктивно-алгоритмической, так и выразительной функцией языков. Её применения разнообразны и включают среди прочего информатику, лингвистику и формальную философию. Она тесно связана с основаниями математики и информатики. К числу ключевых логических понятий относятся «доказуемость», «вычислимость», «выразимость» и «истинность».

В данной области работает С.О. Сперанский.