Как и где можно применить дискретную математику в программировании?

Question

[StepanZharychev]

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

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

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

Заранее спасибо.

Answer 1

[Виталий Витренко]

Есть такая книга Дискретная математика для программистов. Там по моему в конце каждой главы применение выбранной темы в программировании.

Answer 2

[AVKor]

if (c == ' ' || c == '\n' || c == '\t')
(из классики: K-R).

Comments

[Mercury13]

А по-моему, это хороший пример для единорога с радугой.

[AVKor]

Mercury13: Если напоминает единорога-педераста, то я в этом не виноват. Идите дискретку учить.

[Mercury13]

Имеется в виду PVS-Studio.
Код, возможно, с ошибкой, и разработчики PVS нашли закон: если в размноженном коде ошибка, вероятность 50%, что в последней строке.

[AVKor]

Mercury13: Не знаю, что такое этот PVS-Studio (виндовое что-то?).

А код этот из классической книги, которую вы, похоже, не читали.

[Mercury13]

Не читал.
Программа статического анализа кода на Си.
Действительно в конце знак присваивания, а не равенства?

[AVKor]

Mercury13: Ну так советую прочесть. Классика не только языка C, но вообще же культовая книга CS.

Конечно, равенство. Не заметил опечатку в источнике, откуда скопировал. Исправлено.

Answer 3

[Андрей]

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

Answer 4

[Владимир Мартьянов]

Криптография, например.

Comments

[StepanZharychev]

Если не затруднит можете привести какой-нибудь простенький пример?

[Владимир Мартьянов]

StepanZharychev: Если ВАС не затруднит поищите описание простейших шифров и попробуйте там найти элементы дискретной математики. Очень, знаете, помогает пытаться искать ответ самому, после того как дали наводку.

Answer 5

[Mercury13]

В программу дискретной математики моего факультета входили…
• теория множеств
• теория графов
• комбинаторика
• алгебра логики, исчисление высказываний
• теория автоматов

Теория множеств — это основа ВСЕЙ университетской математики. Не зря её повторяли ещё и на муть-анализе.
К тому же в теории множеств есть два классных понятия — отношение эквивалентности и отношение порядка. Операции == и <= перегружать приходилось?
Соответствие везде определённое, функциональное, сюръективное, инъективное, биективное. Теория баз данных. Допустим у нас есть сотрудник и телефон, как они соотносятся? У всех ли сотрудников есть телефоны? Бывает ли у сотрудника два телефона? У всех ли телефонов есть сотрудники? Бывает ли у телефона два сотрудника? Ну а биективное — это соответствие «1:1».

Теория графов — понятное дело, в алгоритмах на сетях. Создание, уничтожение, обход, поиск пути…

Комбинаторика — это а) количество элементов в том или ином конечном множестве; б) способы перебрать их все. Например, мне реально приходилось перебирать комбинации из N элементов не более чем по M. Нерекурсивно.

Алгебра логики — это основа работы компьютеров. Когда булевское условие многоэтажное — как записать его в понятном виде и как его упростить?

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

Comments

[AVKor]

Видимо, плохо учили, на двойку.