Как и где можно применить дискретную математику в программировании?
Очень часто слышу о том, что дискретная математика крайне необходима программисту, но не увидел где бы то ни было четко аргументированного ответа с примерами, зачем она нужна и где применяется.
Посему, хочу попросить гуру программирования или просто прошаренных в этой области людей привести либо учебные материалы (можно и на русском и на английском), либо примеры из жизни, где будет желательно в деталях объясняться, как именно применяется этот раздел математики.
Убедительная просьба воздержаться от комментариев об очевидности данного вопроса, т.к. для меня он не очевиден и я бы хотел разобраться в нем.
- Вопрос задан более трёх лет назад
- 4898 просмотров
Комментировать
Решения вопроса 1
Software Engineer
Есть такая книга Дискретная математика для программистов. Там по моему в конце каждой главы применение выбранной темы в программировании.
Ответ написан более трёх лет назад
Комментировать
Нравится 1 Комментировать
Ответы на вопрос 4
if (c == ‘ ‘ || c == ‘\n’ || c == ‘\t’)
(из классики: K-R).
Ответ написан более трёх лет назад
Нравится 1 6 комментариев
А по-моему, это хороший пример для единорога с радугой.
Mercury13: Если напоминает единорога-педераста, то я в этом не виноват. Идите дискретку учить.
Имеется в виду PVS-Studio.
Код, возможно, с ошибкой, и разработчики PVS нашли закон: если в размноженном коде ошибка, вероятность 50%, что в последней строке.
Mercury13: Не знаю, что такое этот PVS-Studio (виндовое что-то?).
А код этот из классической книги, которую вы, похоже, не читали.
Не читал.
Программа статического анализа кода на Си.
Действительно в конце знак присваивания, а не равенства?
Mercury13: Ну так советую прочесть. Классика не только языка C, но вообще же культовая книга CS.
Конечно, равенство. Не заметил опечатку в источнике, откуда скопировал. Исправлено.
Андрей @VladimirAndreev
php web dev
в логистике, например..
маршрут найти, или алгоритм загрузки машины с учетом маршрута, чтоб максимально за раз перевезти.
Ответ написан более трёх лет назад
Комментировать
Нравится Комментировать
Владимир Мартьянов @vilgeforce
Раздолбай и программист
Криптография, например.
Ответ написан более трёх лет назад
StepanZharychev @StepanZharychev Автор вопроса
Если не затруднит можете привести какой-нибудь простенький пример?
Владимир Мартьянов @vilgeforce
StepanZharychev: Если ВАС не затруднит поищите описание простейших шифров и попробуйте там найти элементы дискретной математики. Очень, знаете, помогает пытаться искать ответ самому, после того как дали наводку.
Программист на «си с крестами» и не только
В программу дискретной математики моего факультета входили…
• теория множеств
• теория графов
• комбинаторика
• алгебра логики, исчисление высказываний
• теория автоматов
Теория множеств — это основа ВСЕЙ университетской математики. Не зря её повторяли ещё и на муть-анализе.
К тому же в теории множеств есть два классных понятия — отношение эквивалентности и отношение порядка. Операции == и Соответствие везде определённое, функциональное, сюръективное, инъективное, биективное. Теория баз данных. Допустим у нас есть сотрудник и телефон, как они соотносятся? У всех ли сотрудников есть телефоны? Бывает ли у сотрудника два телефона? У всех ли телефонов есть сотрудники? Бывает ли у телефона два сотрудника? Ну а биективное — это соответствие «1:1».
Теория графов — понятное дело, в алгоритмах на сетях. Создание, уничтожение, обход, поиск пути…
Комбинаторика — это а) количество элементов в том или ином конечном множестве; б) способы перебрать их все. Например, мне реально приходилось перебирать комбинации из N элементов не более чем по M. Нерекурсивно.
Алгебра логики — это основа работы компьютеров. Когда булевское условие многоэтажное — как записать его в понятном виде и как его упростить?
Теория автоматов — это крайне упрощённый принцип работы процессоров. Поэтому если надо написать предельно простого вида виртуальную машину — см. конечные автоматы. А также автомат Мура — это лексический анализатор в любом языке программирования.
Где применяется дискретная математика
1. Математическая логика. Типовые расчеты: методические указания и контрольные задания / сост.: Гулай Т.А., Мелешко С.В., Невидомская И.А. – Ставрополь: 2013. – 28 с.
2. Мамаев И.И., Долгополова А.Ф. Профессиональная направленность в обучении студентов математическим дисциплинам /Аграрная наука, творчество, рост. – 2013. – С. 268-371.
3. Мамаев И.И., Шибаев В.П. Активизация познавательной деятельности студентов при изучении математических дисциплин /Теоретические и прикладные проблемы современной педагогики. – 2012. – С. 62-67.
4. Донец З.Г.,Мамаев И.И., Шибаев В.П. Учебная организация как целостная модель организации обучения студентов на интегративной основе // Теоретические и прикладные проблемы современной педагогики : сборник научных статей по материалам научно-практической конференции. – Ставрополь, изд-во «АГРУС», 2012. – С. 40-48.
5. Невидомская И.А. Формирование готовности студентов к самообразованию при обучении будущих специалистов-аграриев математики./Сб.научных трудов Sworld. – 2012. Т. 17 № 1. – С. 3-6.
6. Невидомская И.А. Организация самостоятельной работы как средство мотивации студентов к профессиональному самообразованию / Европейский журнал социальных наук. – 2012. № 3. – С.88-91.
Предметом рассмотрения дискретной математики являются методы, которые применяются при исследовании, анализе и решении задач управленческого содержания. В таких отраслях экономики, как эконометрика, логистика, математическое моделирование широко используют графы и математическую логику.
Например, в эконометрике булевские переменные применяются в исследовании регрессионных моделей с переменной структурой, а также в построении регрессионных моделей по неоднородным данным. В этом случае рассматривается лишь одно уравнение регрессии, в которое вводятся булевские переменные, характеризующие изучаемый фактор. На наш взгляд, данный метод удобен для выявления зависимости модели от некоторого фактора.
В логистике широко используется теория графов для описания потоков, задания маршрутов. Например, схему дорог удобнее представить в виде ориентированного графа, в котором известными нам методами выбрать кратчайший путь.
Мы полагаем, что в современных условиях, прокладывая маршрут, особое внимание необходимо обратить на пропускную способность магистралей. В данном случае экономически выгодное решение можно получить, интерпретируя маршруты в графы.
Выбор конкурентоспособного товара или услуги можно выбрать с помощью теории нечетных множеств, которая часто применяется в маркетологии при исследовании рынка услуг.
История развития дискретной математики уходит своими корнями в древность, где уже тогда были известны комбинаторно-логические задачи, решение которых происходило путем перебора комбинаций дискретных объектов и логического анализа возникающих вариантов.
Начало развития дискретной математики относят к XVII в. и связывают с появлением работ Л. Эйлера в области комбинаторного анализа и теории графов и Я. Бернулли по комбинаторной теории вероятностей. Огромную роль в развитии идеологии дискретной математики сыграл Г.В. Лейбниц. В XIX веке в области дискретной математики работали такие математики как Ж.Л. Лагранж, А. Кэли, Дж. Буль, К. Жордан и другие.
Примерами дискретных математических объектов могут являться натуральный ряд чисел; конечное множество элементов произвольной природы; слово (последовательность символов) и формальный язык (множество слов) в конечном алфавите; функция (отображение) из конечного множества в конечное множество и другие.
Необходимо отметить, что, с одной стороны, дискретная математика включает в себя такие разделы, как алгебра, теория множеств, теория чисел, математическая логика и другие. С другой стороны, дискретная математика состоит из ряда специальных разделов и сравнительно новых разделов, которые стали активно развиваться с середины XX века. Это связано с изобретением и внедрением во все сферы жизни человека цифровых технологий и ЭВМ.
Дискретная математика послужила основой проектирования цифровых электронных устройств. Первые применения дискретной математики в этой области связаны с именами К.Э. Шеннона, В.А. Котельникова, В.И. Шестакова.
Возникновение математической теории управляющих систем привело к развитию новых разделов дискретной математики, таких как: теория сложности, теория надежности схем, теория автоматов и других. Существенный вклад в дискретную математику на этом этапе был сделан С.В. Яблонским, Дж. фон Нейманом, А.А. Ляпуновым, О.Б. Лупановым.
Начиная с середины XX века, в жизнь современного человека бурно вошли информационные системы. В начале своего развития это были кибернетические системы, затем – системы с интеллектуальными свойствами, определяющими в которых были информационно-логические, дискретные процессы решения различных задач.
На данном этапе развития общество возникло противоречие, которое не позволяло методами классической высшей математики моделировать интеллектуальные и кибернетические системы. В связи с этим, появилась дискретная математика, которая служила для описания главных систем информационного периода.
Роль дискретной математики заключается в определении следующих факторах:
– модели дискретной математики служат хорошим средством построения и анализа моделей в различных науках;
– дискретную математику можно рассматривать как теоретические основы компьютерной математики;
– язык дискретной математики удобен и фактически стал метаязыком современной математики.
В настоящее время знание дискретной математики необходимо специалистам различных сфер деятельности. Интерес к этой дисциплине не случаен. Это обусловлено широким кругом ее применения: электроника, информатика, вопросы оптимизации и принятия решений и т.д.
Например, суждение: «Если цены высокие (А), то и заработная плата должна быть высокой (В). Цены высокие или применяется регулирование цен (С). Если применяется регулирование цен, то нет инфляции (˥D). Инфляция есть. Следовательно, заработная плата должна быть высокой».
Решение. Формулы первых четырех высказываний формируют посылки, а формула пятого высказывания является заключением. Другими словами:
.
Посылки и заключения разделены между собой чертой.
X Международная студенческая научная конференция Студенческий научный форум — 2018
ПРИМЕНЕНИЕ ДИСКРЕТНОЙ МАТЕМАТИКИ В ПРОГРАММИРОВАНИИ
Андреев И. В.
Работа в формате PDF
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке «Файлы работы» в формате PDF
Дискретная математика и математическая логика — основа любого изучения информационных систем. В настоящий момент основы фундаментальной математической подготовки специалистов в области информатики, программирования и компьютерных наук описаны достаточно понятно: фундаментальные разделы математики, имеющие прикладную направленность на информатику, программирование и компьютеры, сосредоточены в курсах «Математическая логика», «Дискретная математика» и «Теория алгоритмов», являющиеся результатом алгоритмизации знаний, накопленных математикой. [1, 3]
Бурное развитие дискретной математики обусловлено прогрессом компьютерной техники, необходимостью создания средств обработки и передачи информации, а также представления различных моделей на компьютерах, являющихся по своей природе конечными структурами. Большинство задач исследования операций (распределение ресурсов, сетевое планирование и управление, календарное планирование) описываются математическими моделями дискретного программирования. [2, 9]
Умение логически понимать и решать задачу, которая будет поставлена перед любым программистом (независимо от языка программирования) является основополагающей, без логики невозможно полноценно и правильно решить задачу. Корректной можно считать только ту программу, которая исполняет функции, указанные в её технической спецификации, однако результат на уровне тестирования может кардинально отличаться в условиях реальной работы, поэтому необходимо проверить корректность алгоритма: нужно проверить изменения переменных программы, которые оно используется на всех этапах работы алгоритма (до, во время работы и после). Данные изменения будут рассматриваться как предикаты.
Пусть — предикат, верный для входных значений алгоритма , а — предикат, содержащий условия, которые удовлетворяют выходные значения. Высказывание означает следующее: «если алгоритм начинается с корректного значения , то она закончится при истинном значении ». Предикат называется предусловием, — постусловием. Высказывание тоже предикат, поэтому доказательство алгоритма равносильно доказательству верности . Основываясь на этом, можно доказать правильность алгоритма «Квадратный многочлен» на языке Pascal:
Поделим алгоритм на части и зафиксируем обозначения пред- и постусловий.
Подстановки показывают, что высказывания:
Верны. Таким образом, предикат
Верен, таким образом, алгоритм «Квадратный многочлен» корректен.
Алгоритм условных высказываний тоже поддается такому доказательству, необходимо только отразить альтернативные пути в алгоритме. [6]
Предположим, что высказывание
if условие then
вводит предусловие P и в конце даёт условие Q. Поэтому необходимо доказать истинность двух предикатов: высказывание 1
Теория множеств используется для наиболее удобного описания массы концепций в информатике. Одним из примеров применения теории множества в программировании является база данных. Возьмём за пример экспертную систему. [10]
Экспертная система создаётся с целью подмены собой специалистов в данной области. Реализуется это благодаря накоплению базы знаний известных событий с определением набора правил вывода, из-за чего ответы на запросы могут быть выведены логическим путём из базы знаний.
Создадим экспертную систему под названием «Королевская династия Англии». Для начала подготовим список фактов, используя предикаты «родитель» и «жена».
Родитель (Георг I, Георг II) жена (София, Георг I)
Родитель (Георг III, Георг IV) жена (Вильгельмина, Георг II)
Родитель (Георг III, Вильгельм IV) жена (Шарлотта, Георг III)
Родитель (Георг III, Эдвард) жена (Каролина, Георг IV)
Родитель (Эдвард, Виктория) жена (Аделаида, Вильгельм IV)
Родитель (Виктория, Эдвард VII) жена (Виктория, Альберт)
Родитель (Эдвард VII, Георг V) жена (Александра, Эдвард VII)
Родитель (Георг V, Эдвард VIII) жена (Виктория Мари, Георг V)
Родитель (Георг V, Георг VI) жена (Елизавета, Георг VI)
Родитель (Георг V, Елизавета II) жена (Елизавета II, Филипп)
Родитель (Виктория, Элис)
Родитель (Элис, Виктория Альберта)
Родитель (Виктория Альберта, Филипп)
Родитель (x, y) означает, что x является родителем y, а жена (x, y) означает, что x — жена y. Это стандартное чтение предикатов, используемых языками программирования, как, например, PROLOG. [4]
Для извлечения информации необходимо отправлять запросы в базу данных. Пример: «является ли Георг I отцом Георга III?», то ответ будет отрицательным, поскольку предикат родитель (Георг I, Георг III) не существует в списке. Формат запроса зависит от языка программирования, который поддерживает та или иная база данных. Таким образом, использование баз данных в работе помогает упорядочить информацию и наиболее эффективно работать с ней. Запросы формируются по принципу: «? — предикат». При этом подразумевается наличие переменной в предикате, которое будет равносильно вопросу о существовании того или иного элемента. [7]
Сформулируем правило вывода для получения информации о матерях из системы. Необходимо обозначить правило мать(x) так, чтобы положительный ответ на этот запрос формировался только в том случае, если x — жена чьего-то родителя или x — женщина и родитель. Правило такого вывода определяется таким образом:
Но данное правило вывода не найдёт всех матерей из-за того, что база данных не полная — в ней не записаны, например, дети Елизаветы Второй. Полученный результат показывает трудности, возникающие при попытках ограничения реального мира рамками математической модели. [5, 8]
1. Бондаренко В.А., Цыплакова О.Н., Родина Е.В Использование компьютерных математических систем в обучении математике.// Информационные системы и технологии как фактор развития экономики региона: сб. научных статей по материалам Международной НПК / Ставрополь: АГРУС Ставропольского ГАУ, 2013. С. 46-50.
2. Долгих Е.В., Тынянко Н.Н. Теоретические экономико-математические модели // Современные проблемы развития экономики и социальной сферы: сборник материалов Международной научно-практической конференции, посвященной 75-летию Ставропольского государственного аграрного университета. Ответственный редактор: Н. В. Кулиш. 2005. С. 553-556.
3. Дискретная математика для экономистов, Шелковой А.Н., Ююкин Н. А., 2014.
4. Зепнова Н.Н., Кузьмин О.В. Применение методов дискретной математики при решении логических задач // Омский научный вестник. 2014. № 2 (130). С. 14-17.
5. Попова С.В. Формирование алгоритмической культуры у студентов на занятиях по математике // Экономика регионов России: анализ современного состояния и перспективы развития: Сборник научных трудов по материалам ежегодной 68-й научно-практической конференции. Ответственный редактор Кулиш Н.В. 2004. с. 423-426.
6. Попова С.В., Колодяжная Т.А. Применение алгоритмов при обучении математике в вузе // Моделирование производственных процессов и развитие информационных систем: Даугавпилсский университет, Латвия, Европейский Союз Белорусский государственный университет, Беларусь Днепропетровский университет экономики и права, Украина Московский государственный университет им. М.В. Ломоносова, Россия Санкт-Петербургский государственный политехнический университет Северо-Кавказский государственный технический университет Ставропольский государственный университет Ставропольский государственный аграрный университет. Ставрополь, 2011. С. 278-281.
7. Попова С.В., Смирнова Н.Б. Элементы алгоритмизации в процессе обучения математике в высшей школе // Современные проблемы развития экономики и социальной сферы: сборник материалов Международной научно-практической конференции, посвященной 75-летию Ставропольского государственного аграрного университета. Ответственный редактор: Н. В. Кулиш. 2005. с. 526-531.
8. Смирнова Н.Б., Попова С.В. Основные принципы проектирования компьютерной математической модели // Сборник научных трудов по материалам Ежегодной 69-й научно-практической конференции, посвященной 75-летию СтГАУ. Ответственный редактор: Кулиш Н. В.. 2005. С. 185-189.
9. Смирнова Н.Б., Попова С.В. Модели, подходы к классификации моделей // Экономика регионов России: анализ современного состояния и перспективы развития: сборник научных трудов по материалам Ежегодной 69-й научно-практической конференции, посвященной 75-летию СтГАУ. Ответственный редактор: Кулиш Н. В. 2005. С. 181-185.
10. Смирнова Н.Б., Попова С.В., Хачатурян Р.Е. Использование логической символики при обучении математике в вузе // Совершенствование информационных и коммуникационных технологий с целью активизации учебного процесса в вузе. Ставрополь, 2006. С. 191-195.
Основы дискретной математики
Эта статья содержит лишь малую часть информации по заявленной теме. Рассматривайте ее как вводный курс перед началом всестороннего изучения предмета. Надеюсь, вы найдете в ней полезную информацию. Знание дискретной математики помогает описывать объекты и задачи в информатике, особенно когда дело касается алгоритмов, языков программирования, баз данных и криптографии. В дальнейшем я планирую подробнее раскрыть темы, затронутые в этой статье. Приятного чтения!
ЧТО ТАКОЕ ДИСКРЕТНАЯ МАТЕМАТИКА?
Это область математики, изучающая объекты, которые могут принимать только уникальные отдельные значения.
Мы рассмотрим пять основных разделов в следующем порядке.
- Логика
- Теория множеств
- Отношения
- Функции
- Комбинаторика
- Графы
ЛОГИКА
Что такое логика?
Это наука о корректных рассуждениях. Мы будем использовать приемы идеализации и формализации. Неформальная логика изучает использование аргументов в естественном языке.
Формальная логика анализирует выводы с чисто формальным содержанием. Примерами формальной логики являются символическая логика и силлогистическая логика (о которой писал Аристотель).
Начнем с азов. Рассмотрим следующее высказывание на естественном языке:
«Если я голоден, я ем».
Пусть «голоден» будет посылкой 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
Свойства бинарных отношений
Числовые множества
ФУНКЦИИ
Функция — это отношение, которое присваивает переменным новые значения. То есть это отношение между множеством А и множеством В.
Свойства
Функциональная композиция
Это точечное использование функции, результатом которого является другая функция.
КОМБИНАТОРИКА
Простыми словами, это наука о счете.
Перестановки
Это упорядочение уникальных объектов, при котором важен порядок следования.
Комбинации
Это упорядочение уникальных объектов, при котором не важен порядок следования.
Блок-схема алгоритма
ГРАФЫ
Что такое граф?
Это коллекция точек, которые называются узлами или вершинами, и линий между этими точками, которые называются ребрами. Ребро соединяет только два узла. Ребро может быть ориентированным, если ему присвоено направление, или неориентированным.
Если вам понравилась эта статья, приглашаю почитать также мой блог: