Ответы пользователя по тегу Дискретная математика
  • Тема: Операции над нечеткими множествами. Кто может объяснить задачу?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Перечитайте теорию. Повторите определение нечеткого множества, функии его принадлежности и операции над нечеткими множествами. Что значит НЕ B? Раз вероятность принадлежать B - это f(x), то вероятность не принадлежать, очевидно - 1-f(x). Вот и на рисунке 2 показана функция 1-f(x), где f(x) показана на графике для b.

    С пересечениями, наверно, функции перемножаются, а при объединении берется 1-(1-f(x))(1-g(x)).
    Ответ написан
  • В каком месте программисту реально понадобиться знания дискретной математике?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Если пишите что-то посложнее формочек, то может и пригодится.

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

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

    Конечные автоматы - это очень удобный инструмент для организации нетривиальной логики, а поиск кратчайшего пути - довольно частая задача в игростроении. Вообще, игродел требует математики.

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

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

    А уж если вы разработчик компилятора или какого-нибудь медиа кодека, то там дискретка лезет из всех щелей (теория языков, формальные парсеры, дискретное преобразование Фурье).
    Ответ написан
    Комментировать