Ответы пользователя по тегу Математика
  • Знаете ли вы хороший сервис по изучению математики?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Игра в Евклида почему-то закрылась. Есть вот такой задачник: sciencevsmagic.net/geo/# но он, судя по всему, не о том. Но если поискать "interactive geometry problems", то много чего выдаёт, можно покопаться в результатах.
    Ответ написан
  • Как использовать метод Гаусса для итерационного метода Ньютона?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Итак, у вас есть система: F(X)=0. В точке X=(x1,x2,...,xn) её матрица Якоби равна J, а значение F(X)=Y. Шаг метода Ньютона с обратной матрицей выглядел бы как
    X'=X-J-1Y.
    Обозначим dX=J-1Y. Тогда J*dX=Y. А это - линейная система из n уравнений. Её действительно проще решить методом Гаусса, чем искать обратную матрицу и умножать на вектор. Так что находите dX и вычитаете из X.
    Ответ написан
  • Какие есть алгоритмы численной минимизации функции одной переменной, заданной на всем пространстве?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Для непрерывной функции есть простой алгоритм поиска локальных минимумов.
    Допустим, что уже найдены точки a < b < c такие, что f(a) > f(b) < f(c).
    Добавляем точки d=(a+b)/2, e=(b+c)/2, и выбираем точку из b,d,e, значение на которой минимально. Она даст тройку (d,b,e), (a,d,b) или (b,e,c) соответственно, обладающую теми же свойствами, что и исходная тройка, но в 2 раза уже.
    Для поиска исходных точек надо просмотреть прямую с достаточно мелким шагом, чтобы впадина не могла спрятаться между точками. Шаг не обязан быть равномерным, поэтому даже для бесконечной прямой может хватить конечного числа точек.
    Ответ написан
  • Как найти матрицу перехода по векторам?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Судя по названию View, вы работаете в терминах компьютерной графики, когда векторы - строки и умножаются на матрицу слева: v1' = v1*View.
    Берёте 4 линейно независимых вектора v1,v2,v3,v4, составляете из них матрицу M, в которой они записаны по строкам. Из соответствующих векторов v1',v2',v3',v4' строите матрицу M'. Тогда M' = M*View (это довольно очевидно - достаточно вспомнить, как перемножаются матрицы). Отсюда, View = Inverse(M)*M' (умножаем предыдущую формулу на Inverse(M) слева).
    Если пар больше 4, и соответствия только приближённые, то ситуация сложнее - придётся звать на помощь метод наименьших квадратов. Если на матрицу View есть какие-то ограничения, то тоже придётся ещё повозиться (потому что матрица, вычисленная по первым 4 векторам, может быть, например, не совсем ортогональной).
    Ответ написан
  • Как сформировать рёбра на основе списка вершин объекта?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Сначала найдите выпуклую оболочку. Она даст и рёбра, и грани. Провести плоскость через три точки одной грани - дело техники, а вот если граней нет, то задача вообще некорректна. По одному и тому же набору вершин можно построить много разных тел.
    Ответ написан
  • Как оценить статистическую погрешность соц. опроса в пределах одного города?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    От размера города погрешность не зависит, она определяется исключительно размером выборки (1 сигма не превосходит 1/(2*sqrt(n)) ). Так что для 200 человек пишите "ошибка (2*сигма) не превышает 7%".
    Но проблема будет с тем, кто же заходит в паблик и с какой вероятностью. Ведь, как известно, интернет-опросы показывают, что интернетом пользуется 100% населения... А если опрос добровольный - то с какой вероятностью представитель того или иного варианта захочет участвовать в опросе: возможно, что обладатели самых старых и самых новых версий будут хвастаться охотнее, чем "середняки".
    Ответ написан
  • Как найти количество вариантов получения числа из последовательности чисел?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Да, задача не имеет вообще ничего общего с тем, что вы написали вначале. Надо найти число подотрезков - то есть, фрагментов последовательности без пропусков. Ограничения "нельзя удлинять отрезок, если сумма достигла M+1" у них нет - они говорят только, что можно и не удлинять. То, что "воспользуемся модулем", не означает, что надо брать сумму модулей - иначе ответ был бы около 50. Вероятно, имеется в виду, что модуль суммы должен быть больше M (из примера этого понять нельзя, в нём нет отрезка с суммой меньше -8).
    Могу сказать, что задача совсем непростая. Грубой силой она не решается (требуется N^2/2 сравнений, в секунду не уложитесь).
    Я бы делал так. Взять массив частичных сумм (0, a0, a0+a1, ...). Потом сделать log_2(N) копий этого массива (занумерованных индексом k от 1 до log_2(N)), и в каждом из них отсортировать отрезки длиной 2^k. Для массива из задачи это будет выглядеть так:
    S0=S[0]=[0,-2,7,10,16,19,27,26,36,30,37]
    S[1]=[-2,0, 7,10, 16,19, 26,27, 30,36, 37]
    S[2]=[-2,0,7,10, 16,19,26,27, 30,36,37]
    S[3]=[-2,0,7,10,16,19,26,27, 30,36,37]
    К сожалению, массивы S[1],S[2],S[3] оказались одинаковыми - это потому, что в примере мало отрицательных чисел.
    Имея такие массивы, вы легко ответите на вопрос "сколько чисел в фрагменте массива S0[k+1]..S0[N] не принадлежат диапазону S0[k]-M .. S0[k]+M" (время - log(M)^2). Сумма таких ответов для всех k от 0 до M-1 и даст ответ на задачу. Полное время - M*log(M)^2.
    UPD. Лучше бы они писали условие по-английски. Было бы не так стыдно за формулировку.
    Ответ написан
  • Найти неизвестную вторую точку?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Если расстояние равно d, то вторая точка имеет координаты x=10+d*cos(t), y=10+d*sin(t), где t - какое-то число. Если на вторую точку есть дополнительные условия, то координаты иногда можно найти точнее.
    Ответ написан
  • Как составить алгоритм решения задачи на ДП или Рекурсию (Задача на лесенку)?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Решить задачу легко - заводите массив A[N,N], в каждой клетке [K,M] которого будет записано число лесенок из K кубиков, нижний слой которых состоит из M кубиков. Число будет ненулевым, когда M <= K <= M*(M+1)/2.
    Массив заполняется начиная со строчки K=1 по формуле A[K,M]=sum(A[K-M,r],r=1..M-1). Сумма элементов в строчке K=N будет искомым числом.

    В решении, ссылку на которое вы дали, последовательно вычисляется число лестниц из j кубиков, нижний ряд которых не длиннее, чем i кубиков. Чтобы найти это число, надо к уже найденным лестницам, нижний ряд которых не длиннее, чем i-1 кубик (их мы оставляем без изменения), прибавить лестницы из j-i кубиков с нижним рядом не длиннее, чем i-1 кубик (к ним мы добавим ряд из i кубиков). Что и делается во внутреннем цикле.
    Ответ написан
  • Полезен ли алгоритм определения НЕпростоты числа с 3 операций?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Надеюсь, что остаток берётся всё-таки от деления на 390, а не на 389 - иначе смысла в коде вообще не видно.
    Итак, у нас есть 77 простых чисел, меньших 390. Четыре из них - 2,3,5,13 - не более, чем мусор, дающий лишние срабатывания алгоритма. В самом деле, если x%390==3, то x делится на 3, а значит, оно составное. Остальные 73 числа годятся.
    Получается такая картина. Для простого x величина x%390 - некоторое число, взаимно простое с 390. Причём распределены эти остатки более-менее равномерно (на картинке они выглядят как красные столбики). Всего этих остатков 96.
    Если x - простое число, то с вероятностью 73/96 остаток будет простым числом, и алгоритм честно скажет "скорее, простое". С вероятностью 23/96 - те самые 25% - остаток окажется составным, и алгоритм ошибётся.
    Если x - составное, то вероятность того, что число объявят "скорее, простым" будет равна 77/390-1/ln(x) (первое слагаемое - вероятность того, что остаток оказался простым, а второе - доля простых чисел в окрестности x).
    Можно легко избавиться от ошибки первого вида: для этого надо в массив charr положить не простые числа, а числа, взаимно простые с 390. Тогда если алгоритм скажет "составное", то так и есть.
    Можно было вместо 390 взять N=30030=2*3*5*7*11*13. Если массив будет заполнен числами, взаимно простыми с N, то отсеиваться, как составные, будет 4 числа из 5, а ложных отсеиваний простых чисел не будет вообще.
    Ответ написан
  • Равномерно распределяющая хеш-функция. Как задействовать все биты хеш-кода?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Простой модуль придумали в те времена (и для тех ситуаций), когда в качестве хэш-кода брался просто адрес объекта. Поскольку адрес часто делится на 4 (или на 8, или имеет вид 16*k+4, как в Borland-C на 8086), то чётная длина массива приводила бы к очень неравномерному распределению.
    Вторая (не менее важная) причина - что часто используется внутреннее разрешение коллизий: в каждой "корзине" при этом лежит 0 или 1 элемент множества (никаких списков!). Если ячейка M, куда нужно положить элемент, уже занята, то вычисляют некоторый шаг K=f(M), и проверяют ячейки (M+K)%L, (M+2*K)%L, ..., пока не найдут свободную. Чтобы эта последовательность прошла через весь массив, нужно, чтобы K и L были взаимно простыми. Функцию f приходится вычислять часто, поэтому взаимная простота гарантируется тем, что L берётся простым числом.
    Ответ написан
  • Как сгенерировать загадку эйнштейна?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Математика здесь не нужна, достаточно программирования.
    Посмотрите на игрушку Sherlock: www.kaser.com/sherwin.html
    Там алгоритм решения полностью открыт: есть трёхмерный битовый массив "может ли в доме A признак B иметь значение C", и в каждый момент решения найдётся подсказка, исключающая один из вариантов. Так что вам нужно сначала сгенерировать любой набор подсказок, приводящий к решению по этому алгоритму ("если зашли в тупик - добавим ещё подсказку"), а потом исключать из полученного набора те подсказки, без которых задачу можно решить (исключаете по одной и пытаетесь решить). Учтите, что подсказки есть разной силы, и чтобы не получилось огромного набора из "A не сосед B", надо соблюдать баланс, добавив (лучше, сначала, но не обязательно) несколько более сильных подсказок.
    Лучше сгенерировать сотню-другую наборов заранее, а потом применять их, перемешивая признаки и значения в случайном порядке.
    Ответ написан
  • Возможно ли определить за умеренное время (часы\дни) является ли заданное число, с числом знаков более 1000, простым?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Скорость работы вероятностного алгоритма - примерно C*L^2*log(L), где L - длина проверяемого числа, C - количество тестов (вероятность false positive будет не больше 4^(-C)). Это если использовать сверхбыстрые алгоритмы умножения. Для миллиона знаков время получится несколько триллионов - и там всё зависит от константы. Будут это часы, или дни - сказать трудно.
    Если тестируемое число равно произведению нескольких известных простых чисел + 1, то проверка может дать гарантированный результат, но в этом случае C равно количеству чисел, входящих в произведение.
    Ответ написан
  • Где взять миллион простых чисел?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Миллион чисел ищется с помощью решета Эратосфена быстрее, чем за 0.1 сек, и пишется за 10 минут. Это быстрее, чем их найти в сети, и потом читать из файла.
    Ответ написан
  • Зачем нужны однородные координаты?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    По большому счёту, однородные координаты нужны с единственной целью - чтобы при получении экранных координат точки не нужно было различать ортогональную и перспективную проекции. В остальных ситуациях их полная поддержка была бы только лишней тратой ресурсов.
    Сразу надо сказать, что матрицей 3*3 вы не обойдётесь. Такие матрицы описывают только поворот, а в перемещениях объекта и камеры в 3D есть ещё сдвиги. Поэтому нужна матрица, по меньшей мере, 3*4 (в конвенции компьютерной графики, когда вектор это строка а не столбец).
    В терминах линейной алгебры пользоваться такими матрицами неудобно, поэтому к ним добавляют столбец (0,0,0,1), а к координатам точки - четвёртую координату 1. Де-факто мы при этом получаем проективное пространство, представленное однородными координатами. Но при любых операциях над матрицами и точками у нас последний столбец всегда будет (0,0,0,1), а последняя координата точки - 1.
    Если знать это, то можно хорошо сэкономить: для хранения матрицы хватит 12 чисел вместо 16, для перемножения двух матриц - 36 умножений вместо 64, а для умножения матрицы на точку - 9 умножений вместо 16. Надеюсь, что в реальных проектах так и делают.
    Но есть одно место, где последний столбец не равен (0,0,0,1), и четвёртая координата точки может отличаться от 1 - это перспективная матрица для вывода на экран (ссылку вам уже дали). Для вывода точки (x,y,z) результат её применения может быть, условно, (x,y,z,1) - тогда имеет место ортогональная проекция, и выведется точка (x,y), а может - (x,y,-1,z) - тогда координаты точки окажутся (x/z,y/z), и проекция будет перспективной. Хватило бы одного бита - как интерпретировать точку, делить ли на z. Но разработчики компьютерной графики решили, что матрица 4*4 и однородные координаты - это более эффективно. Им виднее.
    Ответ написан
  • Какие дисциплины математики нужны для изучения квантовой физики?

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

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Расположить как угодно, лишь бы каждая цифра встречалась ровно на двух гранях. Считается, что у правильного многогранника вероятность выпадения каждой грани одинакова.
    Если боитесь, что цифры будут разного веса и более тяжелая будет оказываться внизу чаще - расположите одинаковые цифры на противоположных гранях. Тогда они друг друга уравновесят.
    Ответ написан
  • Где применяется комбинаторика в информатике?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Мало применяется. В информатике она, скорее всего, понадобится в анализе сложности различных алгоритмов, выборе оптимальной стратегии перебора. В олимпиадном программировании встречается постоянно. В реальной жизни - в основном, когда комбинаторные формулы требуются для расчётов вероятностей, а те, в свою очередь, для проверки статистических гипотез.
    Ещё комбинаторика может пригодиться в задачах, связанных со статистической физикой, когда через число состояний оценивается энтропия системы, а через неё - дальнейшее поведение или устойчивость. Возможно, она нужна для алгоритмов вроде сверхбыстрого умножения чисел. Но всё это очень далёкий уровень, при взгляде с которого элементарная комбинаторика уже неотличима от таблицы умножения.

    UPD. Можно вспомнить одно место, где комбинаторика требуется в обычных задачах. Это когда у нас есть множество каких-нибудь подмножеств, перестановок, слов над алфавитом, или ещё чего-нибудь, что обычно считает комбинаторика. И мы хотим по элементу этого множества найти его индекс. И наоборот.
    Задача возникает не часто, но если возникла, то без комбинаторных формул не обойтись никак.
    Ответ написан