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

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Нет, эти рассуждения не нужны, вы перемудрили немного. Вы предположили, что во множестве есть минимальный элемент, но получили, что во множестве есть меньший этого минимума элемент. Противоречие. Ибо все остальные элементы множества больше минимального (по определению минимума). Все. Отсюда следуюет что во множестве нет минимального элемента.

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

    Есть еще тонкий момент: рассуждения получающие меньший элемент заданного иногда нельзя применить ко всем числам. Например, если вы работаете с целыми положительными, а предположенный минимальный у вас 1, то из 1 вы меньшее число никак не получите. Поэтому надо сначала проверить, принадлежит ли 1 к множеству и потом предполагать существование минимального элемента > 1.
    Ответ написан
    1 комментарий
  • Как найти или показать существование цикла в ориентированном графе быстрее, чем за O(IVI+IEI)?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Никак.

    Это можно доказать. Вам так или иначе придется посмотреть на все ребра. Допустим, есть алгоритм, который всегда может проверить цикл, смотря не все ребра. Рассморим какой-то граф без циклов. Алгоритм там какие-то ребра посмотрел и сказал, что циклов нет. А мы возьмем и скормим этому алгоритму почти такой же граф, только одно из ребер, которые он вообще не трогал, сделаем обратным какому-то другому ребру в графе, сделав таким образом цикл. Но алгоритм посмотрит на те же самые ребра, увидет все то же самое и сделает точно такой же вывод, что циклов нет, и ошибется. Все потому что мы допустили алгоритм, который всегда смотрит не все ребра. Значит таких алгоритмов нет и там всегда будет хотя бы O(|E|).
    Ответ написан
    2 комментария
  • Возможно ли обнаружить сортировкой Кана изолированные узлы, сортировать сразу рёбра и не использовать степень?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Зачем в алгоритме сортировки Кана вначале требуется степень или просчёт всех соединений, вроде и без неё всё работает?


    Без нее работает медленно. Смотрите алгоритм. В алгоритме надо брать вершину в которую не входит ни одно ребро, а также удалять вершины. Кончено, можно наивно брать все вершины, потом брать все ребра, смотреть, не удалено ли ребро и не ведет ли оно в эту вершину. Но это будет O(VE) для поиска одной вершины, а суммарно алгоритм будет O(V^2E). Когда как реализация с подсчетом степеней и очередью будет O(V+E).

    Есть ли возможность сортировать не узлы, а рёбра сразу?

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

    Можно ли таким образом обнаружить, что этот граф содержит изолированные узлы, которые могут быть соединены между собой?


    Можно. Изолированные узлы - это те в которые ни одно ребро не входит. В алгоритме Кана это те, которые можно вывести до удаления любой вершины.
    Ответ написан
  • Как записать DAG для прохода по ациклическому ориентированному графу, используя C#?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Раз вам надо обойти врешины в топлолгическом порядке, вам нужна топологическая сортировка. Если у вас только одна корневая вершина, то можно и проще - тут сработает любой обход: в ширину или в глубину из корневой вершины. Если корневых вершин несколько, то надо будет использовать какой-либо алгоритм топологической сортировки. Гуглите его. Есть алгоритм основанный на двух обходах в глубину, или нечто основанное на обходе в ширину.

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

    Но все перечисленные тут алгоритмы являются примерно одинаково эффективными. Без бенчмарков нельзя сказать какой из них лучше, и на разных формах графов одни могут быть лучше других и наоборот.
    Ответ написан
    33 комментария
  • Какой смысл использовать функцию эйлера в rsa?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Потому что теорема Эйлера. А в процессе шифрования значение для текста вовзводится в степень по модулю n. А для дешифровки возводится в еще одну степень. Поэтому показатель степени ищется по модулю Ф(n).
    Ответ написан
    Комментировать
  • Почему функция непрерывная?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Функция задана кусочно, да. Но все куски в точках на границах совпадают и разрывов там нет. Функция не гладкая, но все еще непрерывная.
    Ответ написан
    Комментировать
  • Как из критерия унимодальности следует унимодальность функции?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    В унимодальной функции разности соседних элементов сначала неотрицательные а потом неположительные. И наоборот, если разности такие, то, очевидно, сначала функция возрастает (возможно, ступенчато) а потом убывает.

    Вы доказали, что частичные разницы не возрастают. Тут могут быть 3 варианта:
    1) они все неотрицательные. Функция унимодальна (монтонность с максимумом в конце - частный случай унимодальности).
    2) они все неположительные. Монотонно убывающая функция.
    3) есть и положительные и отрицательные. Но раз разности не могут возрастать, после первого 0 могут идти только нули а после отрицательного только отрицательные. А заначит разности выглядят ровно так, как у унимодальной функции.
    Ответ написан
    Комментировать
  • Как доказать коэффициенты Фурье?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Подумайте, что происходит с функцией, если ее умножить на синус и просуммировать?
    Функция раскладывается в ряд фурье ( с пока не известными вам коэффициентами). Надо будет доказать, что можно поменять местами умножение на синус и суммирование. В итоге у вас получится ряд и сумм и вот все суммы кроме одной из-за ортогональности станут 0. А в одной искомый коэффициент можно вынести за скобки и подсчитать сумму.
    Ответ написан
    Комментировать
  • Как узнать какое будет следующее число?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Выглядит случайно. Так что надо или постигнуть запретную черную магию, чтобы видеть будущее, или изобрести машину времени.
    Ответ написан
    Комментировать
  • Как определить в какую сторону повернуты нормали в треугольнке, Внутрь или снаружу?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Возьмите вектор любой из двух оставшихся сторон и ориентируйте его от вершины на проверяемой стороне. Потом посмотрите на знак векторного произведения. Оно отрицательно для нормалей наружу.
    Ответ написан
    Комментировать
  • Как записать это выражение?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Да, нижние индексы - это обозначение системы счисления. Так, 110 в двочиной - это 6 в десятичной, или вот то разложение по степеням двойки.
    Ответ написан
  • Какая будет единая формула для ячейки?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Разница по горизонтали всегда +2. Значит число из строки 2 будет входить с коэффициентом 2.
    По вертикали разница на -1. Значит число из столбца B будет с коэффициентом -1.

    Итак, формула -1*$B3+2*C$2 - 1 . -1 в конце подбираем так, чтобы в самой первой ячейке оказался 0.
    Ответ написан
    Комментировать
  • Как решать задачи на разбиение фигуры на сектора по цветам?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Лемма бернсайда. Гуглите. Но суть в том, что надо подсчитать количество раскрасок, которые не меняются при повороте на какой-то угол. Для всех углов сложить и поделить на количество поворотов.

    Поворот на 1<=i<=42 секторов создает gcd(i,42) циклов, каждый из которых должен быть окрашен целиком в один из 6 цветов. Т.е. получается 6^gcd(i,42) раскрасок, инвариантных для поаорота на i секторов.

    Отсюда ответ к задаче: sum i=1..42 6^gcd(i,42)/42.
    Ответ написан
    2 комментария
  • Как соединить рандомные точки на координатной плоскости в многоугольник?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Выпуклая оболочка, предложенная Vindicar, может соеденить не все точки. Какие-то будут просто внутри. Как в примере с картинки в вопросе, оболочка будет теругольником, а точка по центру будет не соединена ни с чем.

    Надо точки как-то отсортировать. Например, берете самую нижнюю, из всех таких самую левую. Сортируете все оставшиеся точки по углу, относительно этой (по значению atan2(yi-y0, xi-x0)), при равенсве угла по расстоянию (не важно по возрастанию или убыванию). Потом в таком порядке их соединяйте, пересечений не будет.

    В примере из вопроса оно как раз отсортирует их как на картинке.

    Edit, а еще, можно вместо atan сравнивать углы через векторное произведение. Если входные данные - целые точки, то вообще все вычисления будут в целых переменных.
    Ответ написан
    3 комментария
  • Как доказать, что группы неизоморфны?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Надо найти какое-то противоречие в структурах групп.
    Например, в C есть элементы {1, i, -1, -i}. Это 4 различных элемента которые при умножении сами на себя дают 1. Если группы изоморфны, то должны быть 4 соответствующих им элемента в R, все - квадратные корни из 1. Но в R таких только 2: {1, -1}.

    Во втором примере можно привязаться к 0. в Q есть 0, умножив на который всегда получится 0. Но нет элемента, прибавив которой всегда получится одно и то же число.

    Опять же, 0 в {Q, *} не имеет аналога в {R, +}
    Ответ написан
    Комментировать
  • Поможете сделать код лучше, чем у меня сейчас, a³+b³=c³?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    2. Этот код не для Windows;


    Там нет ничего платформо-зависимого. Если установите какой-нибудь mingw на windows, то оно makefile съест.

    В крайнем случае, установите любой C компилятор и введите команду вручную (последняя строчка тут)

    3. Если я в формуле a³+b³+c³=3 поменяю 3, на 0 будет ли программа правильно считать?

    Там в описании написано "cubefree k = +/- 3 mod 9 at most 1000", т.е. для k=0 не сработает.

    Поможете сделать код лучше?


    Выкиньте цикл по c. Вам не надо его перебирать, а вам надо решить уравнение c³=3-a³+b³.
    Для чего просто вычислите значение справа, потом возьмите кубический корень: int((3-a**3-b**3)**(1/3.0)). Не забудьте только проверить, что это значение c подходит, ибо тут корень округляется до целого. И не факт, что уравнение выполняется.
    Ответ написан
  • Как решить эту задачу?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    У вас 7 неизвестных и 3 уравнения. Так что однозначно вы найти значения переменных никак не сможете. Но и найти вам надо какую-то сумму. Есть шанс, что как-то комбинируя, складывая, вычитая и домножая левые части этих уравнений можно получить искомую сумму. Иными словами, вам надо вектор (16, 25..100) представить в виде линейной комбинации векторов (1, 2..49), (4, 9..64) и (9, 16..81). Обратите внимание, что там везде получаются суммы трех квадратов равны следующему.

    Вам надо подобрать такие 3 коэффициента, что x*n^2 + y(n+1)^2+z(n+2)^2 = (n+3)^2. Для n=1..7. У вас тут квадратные многочлены от n получаются, равны они в 7 точках, так что они должны быть равны вообще при любых n. Значит, вам надо раскрыть скобки, сгрупировать степени n и приравнять к 0 все коэффициенты.

    Так вы получите 3 уравнения на 3 переменные x, y, z.
    x+y+z=1
    2y+4z=6
    y+4z=9

    Отсюда получается x=1 y=-3 z=3

    В итоге получаете 1*1-3*12+3*123 - это ваш ответ.
    Ответ написан
    2 комментария
  • Не работает math.pow, что я делаю не так?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Скобки в делителе в переменной numerator пропустили.
    Еще, у вас имена переменных кривые. Зачем-то назвали два множителя "числитель" и "делитель". Причем дробь целиком считается в первой.
    Ответ написан
  • Чем отличается оператор от матрицы в линейной алгебре?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Оператор - вообще любая штука, которая как-то действует на объекты. Она ставит каждому входному элементу некий рузультирующий элемент. Функция, короче. Квадратный корень среди чисел, логарифм там же, поворот объектов на плоскости на 30 градусов по часовой стрелке, отражение относительно прямой - это все операторы.

    Линейное преобразование - это конкретный тип операторов, который действует на элементы R^n и характирезуются тем, что они обладают свойством линейности (F(x+y) = F(x)+F(y), F(kx) = kF(x)).

    Матрица - это математический объект.
    Между матрицами и линейными операторами есть взаимнооднозначное соответствие. Домножение на матрицу - это линейное преобразование. Любому линейному преобразованию можно поставить в соответствие матрицу (посмотрев, как оно преобразует базисные вектора). Поэтому часто можно в литературе встретить, что матрицу называют оператором и наоборот.
    Ответ написан
    2 комментария
  • Как сгенерировать случайные величины с заданной функцией распределения и коэффициентом корреляции??

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    В общем случае все сложно и тут как с интегрированием надо подходить с воображением и изобретательностью.

    Вообще, не для любых функций распределения можно получить любую корреляцию. Например, вы никак не сможете добиться полной (corr=1) корреляции равномерно распределенной величины и нормально распределенной величины.

    Но, если функция для обеих величин одинаковая, то есть, например, такой способ:
    1) Сгенерируйте случайную величину a согласно функции распределения.
    2) C вероятностью k выдайте это же значение как и вторую переменную (b=a).
    3) C вероятностью 1-k сгенерируйте случайную величину b согласно той же функции распределения.

    Этот способ выдаст коэффициент корреляции k. Если нужна отрицательная корреляция, то можно выдать b=2Ea-a во втором шаге (отражение относительно матожидания). Но тогда в третьем шаге плотность распределения будет уже не такая же как у a. Если заданная функия распределения f(x), то там надо использовать g(x)=(f(x) -kf(2Ea-x))/(1-k). Суть в том, чтобы g(x)*(1-k)+k*f(2Ea-x) = f(x) - и итоговая плотность распределения будет одинаковая.

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

    Другой вариант, сгенерировать случайную величину a ~ f(x), потом взять b = k*a+c, где c - это какая-то независимая случайная величина, распределенная как-то хитро (об этом ниже). Регулируя k можно получать разный уровень корреляции. Удобно работать уже с центрированными случайными величинами. Пусть Ea = Eb = Ec= 0.

    Тогда коэффициент корреляции будет E((ka+c)a)/D(a) = (kEa^2+Eac)/D(a) = kE(a^2)/D(a) = k. Потому что a и c независимые случайные величины и Eac = Ea*Ec = 0*0. А D(a) = E(a^2)-Ea*Ea = E(a^2)-0*0.

    Пусть функция распределения a и b - F(x) (плотность f(x)). Искомая функция для c - G(x) (плотность g(x)).

    Надо будет решить интегральное уравнение:
    Int -int..inf g(t)f((x-t)/k)/k dt = f(t)

    Лучше всего это через преобразование лапласа это решать. Теоремму о свертке и свойство умножения на число примените.
    Ответ написан
    Комментировать