Ответы пользователя по тегу Математика
  • Как рассчитать длины сторон фигуры?

    @Mercury13
    Программист на «си с крестами» и не только
    Чтобы перейти от пикселей к метрам, надо вычислить площадь фигуры в квадратных пикселях. Проще всего это делать по формуле трапеций.

    Для каждой стороны надо вычислить площадь трапеции OX — x=xA — AB — x=xB, с плюсом или минусом. Насколько я помню, она равна 0,5(yA + yB)·(xA − xB). Если все сложить и взять абсолютную величину, получится площадь.

    Тогда масштабный коэффициент будет sqrt(Spx / Sм).
    Ответ написан
  • Как и где можно применить дискретную математику в программировании?

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

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

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

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

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

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

    @Mercury13
    Программист на «си с крестами» и не только
    Алгоритмы. Немного олимпиадного программирования ОЧЕНЬ не помешает. Алгоритмы там предлагают несложные, но очень нетривиальные, надо чувствовать, как решить задачу. Элементы сложности алгоритмов. Две задачи из восьми гарантированно будут.

    Алгебра и дискретная математика. Первый курс, всё скопом, без доказательств. Линейные уравнения, квадратичные формы, матрицы, собственные векторы, жорданова форма, перестановки, графы, теория множеств, комбинаторика, алгебра логики…

    Интегралы (не слишком «злые», но приёмы «подстановка», «по частям» и «тригонометрический интеграл» всё же освоить стоит). Интеграл средней сложности — постоянный гость в ШАДý. Может быть и ещё одна задача из мутьанализа — но это как повезёт и задача будет гарантированно нетривиальная, но решающаяся на «том, что помнишь с института» — дифференцирование, ряды Тейлора, основы топологии, простейшие пределы, правило Лопиталя. Вспомни, как берутся простейшие двойные интегралы, может попасться, например, на теории вероятностей.

    ФКП. Самое начало. Аналитических функций и рядов Лорана точно не будет. А вот то, что в комплексном поле многочлен n-й степени имеет n корней, знать надо.

    Теория вероятностей. Непрерывные и дискретные вероятности. Нечто несложное, почти что на уровне кубиков и карт, но одна-две из восьми будет. Хотя статистика — важная часть ШАДа, на экзамене не требуют. И пекла типа белых шумов и интегралов Ито не будет. Хотя что-то типа дискретной марковской цепи — а вдруг, хотя знакомые мне три экзамена не было.

    Школьные олимпиадные задачи. Возможна одна.

    Итого.
    Две — алгоритмы.
    Одна-две — вероятность.
    Одна — интеграл.
    Две-три — что угодно из школьной математики, дискретной математики, матанализа, алгебры, ФКП…

    P.S. Очень хороший приём, который мне помог. Конечно, вам придётся держать скан какого-нибудь справочника или распечатку Википедии (это не возбраняется, но электроника запрещена — впрочем, калькулятора задачи не требуют). Печатайте на одной стороне, вторую — на черновик!
    Ответ написан
    4 комментария
  • Векторная алгебра может ли полностью заменить тригонометрию?

    @Mercury13
    Программист на «си с крестами» и не только
    Скажу по-другому: в тех местах, где не нужны углы в явном виде, тригонометрия, скорее всего, излишня, и действительно вопрос очень часто можно решить средствами векторной алгебры. В большинстве задач геймдева и трёхмерной графики — так точно.

    Ну буду настолько категоричным, чтобы сказать «полностью». Была как-то задача: есть шарнирный четырёхугольник, по диагонали натянута пружина. Может ли эта конструкция (в первом приближении) сымитировать педаль сцепления автомобиля? А то даже у Logitech G27 педаль сцепления не слишком убедительная. Решал численно и тригонометрией, хотя можно аналитически и векторной алгеброй попробовать.

    ЗЫ. Основные аргументы против — простота и накопление погрешностей. Но и накопление иногда можно обойти, не прибегая к тригонометрии — например, использовать кватернионы вместо матриц поворота в 3D или нормировать вектор в 2D.
    Ответ написан
    Комментировать
  • Как доказать выводимость формул в исчислении высказываний?

    @Mercury13
    Программист на «си с крестами» и не только
    Любая тождественно истинная формула выводима. Любая выводимая формула тождественно истинна.
    Первый курс университета.
    Так что — либо вывести из десятка аксиом, либо доказать тождественную истинность.
    Ответ написан
  • Возможно ли реализовать двухфакторная аутенфикация в голове?

    @Mercury13
    Программист на «си с крестами» и не только
    Не имеет смысла по двум причинам.
    1. Легко вскрывается.
    2. Даже при незнании PIN слишком велика вероятность подбора.

    Второе связано с тем, что цифры у нас от 0 до 9 — а значит, сумма из трёх будет в пределах от 0 до 27. Что же с первым? Если у нас N цифр — код восстанавливается за N линейно независимых линейных комбинаций. Например, мы не знаем c и d, но комбинации 2a+b, a+2b и a+b линейно зависимы, и если раскрыты любые две комбинации, раскроется и третья. Для этого надо решить систему линейных алгебраических уравнений:
    { 2a + b = 10
    { a + 2b = 11
    Отсюда a = 3, b = 4, и a + b = 7.
    Ответ написан
    Комментировать
  • Сети Петри, разрешён ли такой переход?

    @Mercury13
    Программист на «си с крестами» и не только
    Переходы t1 и t2 создают в позиции по одной фишке. Переход t3 просто убирает одну фишку. Возможен. И после двух исполнений перехода t3 ни одной фишки не останется.
    Ответ написан
    1 комментарий
  • Тригонометрическая регрессия?

    @Mercury13
    Программист на «си с крестами» и не только
    Совершенно верно. Вообще регрессия методом наименьших квадратов крайне легко выводится для любой формулы вида

    y = A1·f1(x) + A2·f2(x) + … + Am·fm(x)

    при условии, что заданы m пар (x1, y1) ... (xm, ym). Неизвестные — A1…Am.

    Чуть посложнее, надо вспоминать теорию матриц — для N > m пар.
    Ответ написан
    5 комментариев
  • Как математически определить уникальное число для любых двух in64?

    @Mercury13
    Программист на «си с крестами» и не только
    Нельзя, простая комбинаторика.
    Одно число — 264 варианта, два числа — 2128 вариантов.
    Принцип Дирихле говорит, что в одной из клеток будут даже не два кролика, а как минимум ceil(2128/264) = 264 кролика — то есть для какого-то ответа будут как минимум 264 пары аргументов, которые его дают.
    Ответ написан
    3 комментария
  • Как рассчитать глубину полигона (метод z-буфера)?

    @Mercury13
    Программист на «си с крестами» и не только
    Это уже не z-буферизация, а алгоритм художника. Возьмите, например, z-координату центра.
    Ответ написан
    Комментировать
  • Зачем нужны однородные координаты?

    @Mercury13
    Программист на «си с крестами» и не только
    Все распространённые преобразования (сдвиги, повороты, проецирование) можно реализовать матрицей 4×4.
    Ответ написан
    Комментировать
  • Как написать алгоритм спирали?

    @Mercury13
    Программист на «си с крестами» и не только
    688b4461d0a145be8f07116dcdad6612.png
    Ответ написан
    Комментировать
  • Как написать алгоритм спирали?

    @Mercury13
    Программист на «си с крестами» и не только
    И ещё одна штука. Две-семь точек надо располагать по-другому (одна в центре, остальные по кругу на расстоянии dSafe от неё; ну или на худой конец подобрать коэффициент a, чтобы спираль расходилась лишь чуть-чуть). Для восьми-одиннадцати точек надо подбирать индивидуальные a. И только для двенадцати и более подходит a = −0,3·dSafe.
    Ответ написан
    Комментировать
  • Как написать алгоритм спирали?

    @Mercury13
    Программист на «си с крестами» и не только
    Думаю, проще всего делать не спираль Архимеда, а её приближение методом Эйлера. Пусть у нас есть некое расстояние dSafe, на котором должны быть кружочки друг от друга.

    Чтобы поставить второй кружочек, отойдём от центрального на вектор (dSafe, 0). Для третьего и дальше поступим так.

    Найдём угол касательной к спирали Архимеда. Касательный вектор будет a единиц по радиус-вектору (a — коэффициент спирали r=aф) и r единиц по нормали. Таким образом, если мы в точке (x, y), у нас получается касательный вектор вот такой.
    t = (a·x + r·y; a·y − r·x), r = sqrt(x² + y²)

    Нормируем этот вектор до длины dSafe и добавляем к (x, y).
    Штука номер один. Параметр спирали прямо пропорционален безопасному расстоянию (вы это увидите ниже в коде). И штука номер два — только «бесконечно малые» шаги (при нулевом a, т. е. окружность) будут держать нас на окружности, шаги побольше будут выносить нас наружу, для компенсации сделаем a отрицательным.

    Вот действующий код (на C++ Builder’е)

    namespace {
    
    const double dSafe = 30;
    const int rSafe = dSafe / 2;
    const double a = -0.3 * dSafe;
    
    int toPixel(double x)
    {
        return floor(x + 0.5) + 200;
    }
    
    }
    
    void TfmMain::drawPoint(double x, double y)
    {
        int xx = toPixel(x);
        int yy = toPixel(y);
        Canvas->Ellipse(xx - rSafe, yy - rSafe, xx + rSafe, yy + rSafe);
    }
    
    void __fastcall TfmMain::FormPaint(TObject *Sender)
    {
        Canvas->Brush->Style = bsClear;
        Canvas->Pen->Color = clBlack;
    
        double x = 0, y = 0;
        drawPoint(x, y);
        x += dSafe;
        drawPoint(x, y);
    
        for (int i = 0; i < 120; ++i) {
            double r = sqrt(x*x + y*y);
            double tx = a*x + r*y;
            double ty = a*y - r*x;
            double tLen = sqrt(tx*tx + ty*ty);
            double k = dSafe / tLen;
            x += tx * k;
            y += ty * k;
            drawPoint(x, y);
        }
    }
    Ответ написан
    Комментировать