Можно по-прежнему считать, что дискриминант минимальный. Просто sizeof::<(u8, u32, u32)> = 12, из-за выравнивания. Получается, что мы храним дискриминант (1 байт), паддинг (3 байта) и 2 u32 (по 4 байта).
Так всё логично. u64 должен быть выровненным по 8 байт. Поэтому размер второй структуры должен делиться на 8, содержать u64 (8 байт) и дискриминант - минимальный размер 16 байт. u32 требует выравнивания до 4 байт. Размер первой структуры должен делиться на 4 и содержать два u32 (8 байт на пару). Минимальное число, удовлетворяющее такому свойству - 12 байт.
В худшем случае, деление 2 к 1 приводит не к логарифму по основанию 3, а к логарифму только по основанию 3/2. В среднем случае всё тоже плохо: с вероятностью 1/3 Вы уменьшаете массив в 3 раза, а с вероятностью 2/3 только 1.5 раза. В итоге ожидание двоичного логарифма длинны массива уменьшается за шаг примерно на 1/3 log_2 (3) + 2/3 log_2 (3/2) = log_2 (3) - 2/3 ~= 0.91, а было бы обычное деление пополам - было бы ровно 1.
Нельзя. Поиск бинарный потому что у операции сравнения (в случае поиска элемента в массиве) есть только два исхода (равенств быть практически не может).
Только алгоритм выглядит как n*n, а не n log n. В принципе, он может отбирать фиксированное количество, а не фиксированную долю за каждый проход туда-обратно.
Сохранить сильную ссылку в локальной переменной или поле класса клиента (зависит от его реализации). В этом случае сервер не будет потушен, пока есть хоть один живой клиент.
Так же получится много сильных ссылок на сервер?
И может ли у сервера быть сильная ссылка на клиент в таком сетапе?
Можно даже не уходить в деревья. Пусть у нас связанный список, у которого сильные ссылки только вперёд.
Операция "сконкатинируй два списка (т.е. имея одну ноду у которой нет prev и одну ноду у которой нет next пропиши соответствующие ссылки)" допустимая или нет?
А вот всего путей может быть аж (sqrt(n)!)^sqrt(n), что примерно (n/c)^(n/2) (и гораздо больше чем n^3 * 2^n): если граф распадается на почти полные компоненты по sqrt(n) вершин, где у каждой компоненты есть "первая" и "последняя", при этом "последняя" очередной компоненты связанна с "первой" следующей. По каждой компоненте будет sqrt(n)! путей, компонент sqrt(n), что даёт оценку вначале.
У многочленов (x-a)^(2n) + b и (x-a)^(2n) - b совпадают и все производные, и знаки значений почти всюду (кроме очень маленького интервала a +- b^{1/(2n)} ). В итоге, любому численному методу нужно попасть в этот интервал (который может быть гораздо меньше eps), чтобы отличить эти два случая.
А метод Штурма даёт точку из этого интервала (собственно a) когда делит многочлен на производную, там как раз (x-a) выносится.
Будут, конечно. Попробуйте свой алгоритм для многочлена (x - 1/3)^2 начиная с отрезка 0,1 и используя просто середину отрезка как функцию.
У Вас получится отрезок (1 - eps)/3, (1 + 2*eps)/3 , значения в обоих концах положительные. А значит по алгоритму
Как и ранее, итерационный процесс прекращается, если становится меньше заранее заданного . Далее ступень считается относящейся к вещественному корню полинома, если на границах интервала значение полинома имеет разные знаки, или если разность значений индекса точки на границах интервала нечетна.
И в оригинале, и в переводе что-то не так со сниппетом про сравнение времени ( one/two) - выглядит так, что либо должна быть разная таймзона в разных строчках, либо как-то ещё указано, что в two время наступило второй раз.
Технически, метод бинарного поиска последовательно по производным (как и метод, предложенный автором) плохо работает с многочленами вида (x-a)^(2n) + b, где b очень мало по модулю (по сравнению с a). И это, в общем-то понятно - очень малое изменение свободного члена (с a^2n - b до a^2n + b) сильно влияет на корни (либо они есть, либо их нет). Собственно, никакой численный метод, кажется, за заранее фиксированное число шагов не может ответить на вопрос, есть ли корень, или нет (и это то, зачем нужен метод Штурма).
По окончании процесса рекурсивного деления считается, что все корни найдены.
Противоречит требованию
КРИТЕРИЙ 1: Алгоритм должен быть абсолютно надежен, тоесть для любых коеффициентов, являющихся вещественными числами, все корни полинома гарантированно должны быть найдены. Исключение могут составлять случаи, когда корни настолько велики, что значение полинома в них не может быть вычислено по тем или иным причинам.
А именно, корни кратности два всегда будут пропущены.
Ну, вообще говоря, есть целая область theoretical computer science, посвященная оптимальным вычислимым сжатиям, искать можно по ключевому слову "Колмогоровская сложность".
Запутанные и имеющие суммарно нулевой спин - это разные свойства. Например, можно запутать три частицы так, чтобы суммарный спин в направлении 0 был равен ровно единице (из трёх возможных результатов). Вообще не возможно запутать три частицы так, чтобы даже по одному направлению была нулевая сумма - можно получить только нечётный суммарный спин (а ноль - чётное число).
Извините, но алфавит (греческий, арабский или латинский) не влияет на функции. Можно использовать латинский алфавит для обозначения функций, просто так обычно не делают. И для двух частиц функция вполне записывается.
Что вкладывается в формулировку "три запутанных частицы"? Вроде бы, наличие измерения на стороне Б не меняет распределение исходов на стороне А (хотя какие-то совместные исходы А и Б становятся запрещёнными).
Можно по-прежнему считать, что дискриминант минимальный.
Просто sizeof::<(u8, u32, u32)> = 12, из-за выравнивания.
Получается, что мы храним дискриминант (1 байт), паддинг (3 байта) и 2 u32 (по 4 байта).
Так всё логично. u64 должен быть выровненным по 8 байт. Поэтому размер второй структуры должен делиться на 8, содержать u64 (8 байт) и дискриминант - минимальный размер 16 байт.
u32 требует выравнивания до 4 байт. Размер первой структуры должен делиться на 4 и содержать два u32 (8 байт на пару). Минимальное число, удовлетворяющее такому свойству - 12 байт.
Вы не правы.
В худшем случае, деление 2 к 1 приводит не к логарифму по основанию 3, а к логарифму только по основанию 3/2.
В среднем случае всё тоже плохо: с вероятностью 1/3 Вы уменьшаете массив в 3 раза, а с вероятностью 2/3 только 1.5 раза. В итоге ожидание двоичного логарифма длинны массива уменьшается за шаг примерно на 1/3 log_2 (3) + 2/3 log_2 (3/2) = log_2 (3) - 2/3 ~= 0.91, а было бы обычное деление пополам - было бы ровно 1.
Нельзя.
Поиск бинарный потому что у операции сравнения (в случае поиска элемента в массиве) есть только два исхода (равенств быть практически не может).
Только алгоритм выглядит как n*n, а не n log n. В принципе, он может отбирать фиксированное количество, а не фиксированную долю за каждый проход туда-обратно.
Более того, свойство "создаётся гарантированно позже" может быть не определено на переменных:
var *a = ...;
var *b = ...;
var *c = ...;
var *d = if(rand < 0.5) a else c
И всё - переменные b и d могут быть созданы в любом порядке.
Так же получится много сильных ссылок на сервер?
И может ли у сервера быть сильная ссылка на клиент в таком сетапе?
Можно даже не уходить в деревья.
Пусть у нас связанный список, у которого сильные ссылки только вперёд.
Операция "сконкатинируй два списка (т.е. имея одну ноду у которой нет prev и одну ноду у которой нет next пропиши соответствующие ссылки)" допустимая или нет?
Так для циклических ссылок не нужен один и тот же объект: достаточно в next одного и prev другого сделать сильную ссылку. И всё, вот утечка памяти.
Вроде, с решения о его производстве (когда нашлись заказчики) до производства прошло 5 лет, которые сдвинули на год.
За такое время, кажется, можно найти один путь.
А вот всего путей может быть аж (sqrt(n)!)^sqrt(n), что примерно (n/c)^(n/2) (и гораздо больше чем n^3 * 2^n): если граф распадается на почти полные компоненты по sqrt(n) вершин, где у каждой компоненты есть "первая" и "последняя", при этом "последняя" очередной компоненты связанна с "первой" следующей. По каждой компоненте будет sqrt(n)! путей, компонент sqrt(n), что даёт оценку вначале.
У многочленов (x-a)^(2n) + b и (x-a)^(2n) - b совпадают и все производные, и знаки значений почти всюду (кроме очень маленького интервала a +- b^{1/(2n)} ).
В итоге, любому численному методу нужно попасть в этот интервал (который может быть гораздо меньше eps), чтобы отличить эти два случая.
А метод Штурма даёт точку из этого интервала (собственно a) когда делит многочлен на производную, там как раз (x-a) выносится.
Будут, конечно. Попробуйте свой алгоритм для многочлена (x - 1/3)^2 начиная с отрезка 0,1 и используя просто середину отрезка как функцию.
У Вас получится отрезок (1 - eps)/3, (1 + 2*eps)/3 , значения в обоих концах положительные. А значит по алгоритму
он будет выкинут.
И в оригинале, и в переводе что-то не так со сниппетом про сравнение времени ( one/two) - выглядит так, что либо должна быть разная таймзона в разных строчках, либо как-то ещё указано, что в two время наступило второй раз.
Технически, метод бинарного поиска последовательно по производным (как и метод, предложенный автором) плохо работает с многочленами вида (x-a)^(2n) + b, где b очень мало по модулю (по сравнению с a). И это, в общем-то понятно - очень малое изменение свободного члена (с a^2n - b до a^2n + b) сильно влияет на корни (либо они есть, либо их нет). Собственно, никакой численный метод, кажется, за заранее фиксированное число шагов не может ответить на вопрос, есть ли корень, или нет (и это то, зачем нужен метод Штурма).
Противоречит требованию
А именно, корни кратности два всегда будут пропущены.
Ну, вообще говоря, есть целая область theoretical computer science, посвященная оптимальным вычислимым сжатиям, искать можно по ключевому слову "Колмогоровская сложность".
Запутанные и имеющие суммарно нулевой спин - это разные свойства.
Например, можно запутать три частицы так, чтобы суммарный спин в направлении 0 был равен ровно единице (из трёх возможных результатов).
Вообще не возможно запутать три частицы так, чтобы даже по одному направлению была нулевая сумма - можно получить только нечётный суммарный спин (а ноль - чётное число).
Извините, но алфавит (греческий, арабский или латинский) не влияет на функции. Можно использовать латинский алфавит для обозначения функций, просто так обычно не делают. И для двух частиц функция вполне записывается.
Что вкладывается в формулировку "три запутанных частицы"? Вроде бы, наличие измерения на стороне Б не меняет распределение исходов на стороне А (хотя какие-то совместные исходы А и Б становятся запрещёнными).