Ответы пользователя по тегу Дискретная математика
  • Теорема Кантора в программировании?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Применяется при поиске корня функции делением отрезка пополам. Для любой последовательности знаков f(x) для середин отрезка мы получаем некоторое число - корень уравнения. Конечно, в действительности мы делаем только конечное число шагов и получаем число из конечного множества, но сам факт, что метод работает, а корень существует, основан, в том числе, на континуальности отрезка. Если бы у нас были только рациональные числа, то уравнение x^2=2 корня бы не имело, и мы не имели бы права сказать, что мы находим его с нужной точностью.
    Ответ написан
  • Дискретная математика в непрерывной жизни?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Такие задачи чаще встречаются на этапе разработки алгоритма. Когда нужно понять эффективность алгоритма, уложить структуру в память, сравнить разные структуры или подходы и выбрать более подходящую. Не всегда удаётся сразу получить оценку O(N^k), бывают и более сложные ситуации. Или такая задача, как организовать перебор с наименьшим числом возвратов, как-то закодировать найденный вариант... тут и число отображений может пригодиться.
    Проблема в этом вопросе - что когда надо применить какое-нибудь комбинаторное понятие, то применяешь его и идёшь дальше. В памяти этот факт не откладывается, в программе иногда тоже. Зато если в программе такие вычисления остаются - это гарантированная невозможность поддержки кода кем-либо ещё :) Даже при наличии комментариев.
    Ответ написан
  • Каков физический смысл модуля при модульном возведении в степень?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Ну, например. Проводите вы какие-нибудь сложные вычисления, например, считаете определитель большой матрицы методом Гаусса. Получилось какое-то маленькое значение, но ошибка при вычислениях могла накопиться большая, и вы не уверены, 0 это или, скажем, 1 (у исходной матрицы коэффициенты целые). Что делать? Посчитать по какому-нибудь модулю. Если повезло и в процессе не пришлось делить на 0, то результат по этому модулю окажется правильным, и если получился не 0 - то значит, и вещественное число было ненулевым. Если же по нескольким разным модулям получились нули, то с большой вероятностью определитель действительно нулевой.
    Модулярная арифметика может пригодиться для перемножения многочленов или больших чисел с помощью быстрого преобразования Фурье. Или для каких-нибудь расчётов, когда вообще неважно, чему равны числа, лишь бы они были ненулевыми и независимыми. В общем, случаи редкие, но когда они встречаются, неплохо бы об этом приёме знать.
    А, да, ещё была "многомодульная геометрия" - когда с помощью модулярной арифметики проверяли, равны ли радиусы двух сфер. Хотя это олимпиадное программирование...
    Ответ написан
  • Как и где в программировании используется математическая логика?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Математическая логика - правила вывода, системы аксиом, теории, логические системы и т.п. - практически не используется. Возможно, какая-то её часть нужна при разработке компиляторов (формализация вывода типов, доказательства допустимости оптимизаций...) и экспертных систем.
    Булева алгебра нужна гораздо чаще. Но если вы выучите и поймёте правила преобразования логических выражений, этого будет достаточно. Даже предполные классы, скорее всего, не понадобятся. Хотя, если судьба забросит в программирование ПЛИС... там всё может быть.
    Проходят ли в дискретной математике графы - не помню. Даже если да, то совсем не на том уровне (и не в том направлении), в котором они нужны в программировании.
    Что могло бы пригодиться - конечные автоматы. Они нужны более, чем в одном месте. Но, опять же, в дискретной математике могут дать, разве что, общие факты про них.
    Так что, в целом - это предмет для расширения кругозора и любителей головоломок разных уровней.
    Ответ написан
  • Как из математика адаптироваться-переквалифицироваться в программиста?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Боюсь, что будет очень трудно. Все эти юнит-тесты, соблюдение стилей программирования, документация, системы поддержки версий через какое-то время заставят забыть, что ты математик. Я сейчас стараюсь держаться от них подальше: попал на такое место, где нужен именно математик-алгоритмист, и, хотя пишу много кода, программистом себя считать не могу. Это опасное положение: если придётся менять работу, будет трудно найти что-нибудь подобное.
    Так что чтобы переквалифицироваться в программиста, надо изучать современное программирование с нуля. А чтобы научиться придумывать и реализовывать алгоритмы - брать книжку по алгоритмам, и разбирать и писать их все подряд. Через какое-то время придумать себе задачу с околоматематической формулировкой, попытаться её решить (пример: построить все неэквивалентые триангуляции многообразий - с краем и без, содержащие данное число треугольников). Потом другую задачу, и т. д.
    Ответ написан
  • Определение кортежа. Теория множеств?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Итак, у вас есть некоторый объект X, который возник, как множество {a,{a,b}}, где a и b - различные или одинаковые множества. Про атомарные объекты я сейчас ничего не скажу, насколько я помню, в классической теории множеств есть только множества.
    Поскольку множество не может быть своим элементом (аксиома регулярности?), объекты a и {a,b} различны. Значит, X состоит ровно из двух элементов p и q. Эти элементы не могут быть элементами друг друга (по той же аксиоме), значит, либо p - элемент q, либо наоборот (третьего не дано по построению X). Того, кто элемент другого, обозначаем a. Тогда другой - либо множество из одного элемента {a} - и в этом случае b=a, либо множество из двух элементов a и b. В обоих случаях получаем упорядоченную пару (a,b). Метод, конечно, варварский (с практической точки зрения)... но верный :)
    Ответ написан