Ищу примеры, где полезно знание дискретной математики [закрыто]

Question

Вдохновленный просмотром выступления Майкла Фезера в SCNA "Самообразование и Ремесленник", Мне интересно услышать о практических примерах в разработке программного обеспечения, где дискретная математика оказалась полезной.

Answer 1

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

http://en.wikipedia.org/wiki/Discrete_math

Прочтите эту ссылку.Вы увидите, что существует множество практических применений, хотя в этой статье в Википедии говорится в основном в теоретических терминах.

Answer 2

Методы, которым я научился на курсе дискретной математики в университете, очень помогли мне в играх профессора Лейтона.

Это считается полезным...верно?

Существует множество реальных примеров, когда алгоритмы раскрашивания карт полезны не только для раскрашивания карт.Вопрос на моем выпускном экзамене касался программирования светофора на перекрестке с шестью полосами движения.

Answer 3

Как указывает Сан-Хасинто, основы программирования очень сильно связаны с дискретной математикой.Более того, "дискретная математика" - это очень широкий термин.Эти вещи, возможно, затрудняют выбор конкретных примеров.Я могу назвать лишь горстку, но есть много-много других.

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

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

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

Answer 4

Я посещал курс по тестированию программного обеспечения, и 3 лекции были посвящены обзору дискретной математики в связи с тестированием.Размышления о планах тестирования в этих терминах, по-видимому, действительно помогают сделать тестирование более эффективным.

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

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

Answer 5

Просто пример одного из многих-многих...

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

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

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

Answer 6

Я полагаю, что само тестирование должным образом вытекает из modus tollens, концепции логики высказываний (и, следовательно, дискретной математики), modus tollens которой:

P=>Q.!Q, следовательно !P.

Если вы подключаете "Если функция работает должным образом, тест пройдет" для P=> Q, а затем принимаете !Q как указано ("тест не прошел"), тогда, если все эти утверждения фактически верны, у вас есть действительная, надежная основа для возврата функции для исправления.Напротив, многие, может быть, большинство тестировщиков действуют по принципу:

"Если программа работает должным образом, тест пройдет успешно.Тест пройден, следовательно, программа работает должным образом".

Это может быть записано как:P=>Q.Q, следовательно, P.

Но это ошибочное "подтверждение следствия", и оно не показывает того, что, по мнению тестировщика, оно показывает.То есть они ошибочно полагают, что функция была "проверена" и может быть отправлена.Когда задано Q, P на самом деле может быть либо истинным, либо неверным для P=> Q, и это может быть показано с помощью таблицы истинности.

Modus tollens лежит в основе концепции Карла Поппера о науке как фальсификации, и тестирование должно проходить во многом таким же образом.Мы пытаемся опровергнуть утверждение о том, что функция всегда работает при любых явных и неявных обстоятельствах, вместо того чтобы пытаться проверить, что она работает в узком смысле, что она может работать каким-то запрещенным способом.