Содержание

Есть историческая справка, страница 22

Страницы, где объясняется происхождение формулы или идеи.

1833 формулы

Таблица формул

Показаны 1261-1320 из 1833. Остальные формулы доступны на соседних страницах подборки.

Формула Запись Тема Для чего нужна
Функция Эйлера: произведение по простым делителям $\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right)$ Арифметика и теория чисел Функция Эйлера φ(n) считает положительные целые числа от 1 до n, взаимно простые с n. Для вычисления достаточно знать различные простые делители n: каждый входит в произведение ровно один раз.
Число делителей по разложению на простые множители $n=\prod_{i=1}^{r}p_i^{a_i},\qquad \tau(n)=\prod_{i=1}^{r}(a_i+1)$ Арифметика и теория чисел Число положительных делителей n равно произведению увеличенных на единицу показателей в его простом разложении. Каждый делитель получается независимым выбором допустимой степени каждого простого множителя.
Сумма делителей по простому разложению числа $n=\prod_{i=1}^{r}p_i^{a_i},\qquad \sigma(n)=\prod_{i=1}^{r}(1+p_i+\cdots+p_i^{a_i})$ Арифметика и теория чисел Сумма положительных делителей n получается перемножением сумм степеней каждого простого множителя от нуля до его показателя. В сумму входят единица и само число; для собственных делителей затем вычитают n.
Обратный элемент по модулю через расширенный алгоритм Евклида $au+mv=1\quad\Longrightarrow\quad a^{-1}\equiv u\pmod m$ Арифметика и теория чисел Обратный к a по модулю m — это остаток, произведение которого с a даёт единицу по модулю m. Расширенный алгоритм Евклида находит его как коэффициент при a в целочисленном равенстве Безу.
Китайская теорема об остатках для двух взаимно простых модулей $x\equiv r+m\bigl((s-r)m^{-1}\bmod n\bigr)\pmod{mn}$ Арифметика и теория чисел Китайская теорема об остатках восстанавливает общий класс чисел по остаткам r и s при делении на взаимно простые m и n. Решение существует для любой пары остатков и единственно по модулю произведения mn.
Распределение Пуассона: вероятность числа событий $P(X=k)=e^{-\lambda}\frac{\lambda^k}{k!}$ Вероятность и статистика Распределение Пуассона даёт вероятность ровно k событий на фиксированном интервале, если известно их среднее число λ. Модель применяют к независимому потоку с постоянной интенсивностью.
Геометрическое распределение: номер первого успеха $P(X=k)=(1-p)^{k-1}p$ Вероятность и статистика Геометрическое распределение описывает число независимых попыток до первого успеха включительно. Вероятность успеха p остаётся одинаковой в каждой попытке, а предшествующие попытки заканчиваются неудачей.
Гипергеометрическое распределение: выбор без возвращения $P(X=k)=\frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}$ Вероятность и статистика Гипергеометрическая формула даёт вероятность выбрать ровно k объектов нужного типа среди n предметов, взятых без возвращения из N. В исходной совокупности ровно K объектов относятся к нужному типу.
Равномерное распределение: вероятность попасть в интервал $P(c\le X\le d)=\frac{d-c}{b-a},\qquad a\le c\le d\le b$ Вероятность и статистика Для непрерывного равномерного распределения на отрезке [a,b] вероятность попадания в его часть [c,d] равна отношению длин. Равные по длине части имеют одинаковые вероятности независимо от положения.
Экспоненциальное распределение: вероятность времени ожидания $P(T>t)=e^{-\lambda t}$ Вероятность и статистика Экспоненциальная модель даёт вероятность ждать событие дольше t при постоянной интенсивности λ. В отличие от счёта событий по Пуассону, случайной величиной здесь служит непрерывное время до ближайшего события.
VSTACK в Excel: объединить массивы по строкам $\texttt{=VSTACK(A2:B3,D2:E4)}$ Массивы и преобразование таблиц VSTACK последовательно ставит массивы один под другим и возвращает единый разливающийся диапазон. При разной ширине недостающие позиции получают #N/A.
HSTACK в Excel: объединить массивы по столбцам $\texttt{=HSTACK(A2:A4,C2:D3)}$ Массивы и преобразование таблиц HSTACK ставит массивы рядом и возвращает общий разлившийся диапазон. Высота равна максимуму высот аргументов, а недостающие строки получают #N/A.
EXPAND в Excel: увеличить массив до заданного размера $\texttt{=EXPAND(A2:B3,4,3,"-")}$ Массивы и преобразование таблиц EXPAND увеличивает массив до заданного числа строк и столбцов, заполняя новые ячейки pad_with или #N/A по умолчанию. Уменьшение размера даёт #VALUE!.
REDUCE в Excel: получить один результат из массива $\texttt{=REDUCE(0,A2:A4,LAMBDA(a,v,a+v\char94 2))}$ Массивы и преобразование таблиц REDUCE последовательно применяет LAMBDA к элементам массива и возвращает один финальный аккумулятор. Это удобная основа для сумм, произведений и условных счётчиков.
SCAN в Excel: вывести промежуточные аккумуляторы $\texttt{=SCAN(0,A2:A4,LAMBDA(a,v,a+v))}$ Массивы и преобразование таблиц SCAN применяет LAMBDA к элементам массива и возвращает все промежуточные аккумуляторы. Функция строит нарастающие итоги и помогает увидеть ход вычисления.
Энтропия Шеннона: средняя информация дискретного источника $H(X)=-\sum_{i=1}^{m}p_i\log_2p_i$ Кодирование информации Энтропия Шеннона измеряет среднюю неопределённость исхода по его вероятностям. При двоичном логарифме результат выражают в битах на символ; редкие и частые символы вносят разный вклад.
Средняя длина кода Хаффмана: расход бит на символ $\overline{L}=\sum_{i=1}^{m}p_i\ell_i$ Кодирование информации Средняя длина двоичного кода равна сумме длин кодовых слов с весами вероятностей символов. Для кода Хаффмана этот расход минимален среди двоичных посимвольных префиксных кодов с заданными вероятностями.
Минимальное расстояние кода: сколько ошибок можно исправить $t=\left\lfloor\frac{d_{\min}-1}{2}\right\rfloor$ Кодирование информации Минимальное расстояние между разрешёнными кодовыми словами определяет гарантированное число исправляемых замен битов. Чтобы исправить любые t ошибок, нужно расстояние не меньше 2t+1.
Граница Хэмминга: сколько слов помещается в исправляющий код $M\sum_{j=0}^{t}\binom{n}{j}\le 2^n$ Кодирование информации Граница Хэмминга ограничивает число слов M двоичного блочного кода длины n, исправляющего любые t замен. Области возможных повреждений вокруг разных слов должны помещаться среди всех двоичных строк без пересечений.
Закон Амдала: предел ускорения параллельной программы $S(N)=\frac{1}{(1-p)+p/N}$ Алгоритмы и анализ данных Закон Амдала оценивает ускорение неизменной задачи на N одинаковых исполнителях, если долю p исходного времени можно идеально распараллелить. Последовательная часть ограничивает итоговый выигрыш.
Метод бисекции: корень и гарантированная точность $c=\frac{a+b}{2},\qquad |c-r|\leq\frac{b-a}{2}$ Численный поиск корней Метод бисекции ищет корень непрерывной функции делением отрезка пополам. Разные знаки на концах дают гарантию существования корня, а длина отрезка — оценку ошибки.
Метод Ньютона: приближение корня по касательной $x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}$ Численный поиск корней Метод Ньютона заменяет функцию касательной в текущем приближении и берёт нуль этой прямой как следующий шаг. Вблизи простого корня сходимость может быть квадратичной.
Метод секущих: поиск корня без вычисления производной $x_{k+1}=x_k-f(x_k)\frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}$ Численный поиск корней Метод секущих строит прямую по двум последним точкам графика и использует её пересечение с осью для нового приближения корня. Производная заменяется разностным наклоном.
Составная формула трапеций для вычисления интеграла $T_n=h\left[\frac{f(a)+f(b)}2+\sum_{i=1}^{n-1}f(a+ih)\right],\quad h=\frac{b-a}{n}$ Численное интегрирование Составная формула трапеций приближает определённый интеграл суммой площадей под линейными отрезками между соседними узлами. Концевые значения получают половинный вес.
Формула Симпсона: интеграл по параболическим дугам $S_n=\frac h3\left[f_0+f_n+4\!\sum_{\substack{i=1\\i\text{ нечётное}}}^{n-1}f_i+2\!\sum_{\substack{i=2\\i\text{ чётное}}}^{n-2}f_i\right]$ Численное интегрирование Составная формула Симпсона объединяет соседние промежутки попарно и заменяет функцию параболой через три узла. Для равномерной сетки число промежутков должно быть чётным.
Явный метод Эйлера: решение задачи Коши по шагам $y_{n+1}=y_n+h f(t_n,y_n),\qquad t_{n+1}=t_n+h$ Численные методы ОДУ Явный метод Эйлера приближённо решает уравнение y′ = f(t,y), продолжая решение по наклону в начале каждого шага. При гладком решении глобальная ошибка имеет первый порядок по шагу.
Неявный метод Эйлера: шаг и устойчивость затухания $y_{n+1}=y_n+h f(t_{n+1},y_{n+1})$ Численные методы ОДУ Неявный метод Эйлера использует производную в конце шага. Новое значение входит в обе части равенства, поэтому каждый переход требует решения уравнения, зато схема хорошо подавляет быстро затухающие компоненты.
Явный метод средней точки для задачи Коши $k_1=f(t_n,y_n),\quad k_2=f(t_n+h/2,y_n+hk_1/2),\quad y_{n+1}=y_n+hk_2$ Численные методы ОДУ Явный метод средней точки делает пробный полушаг по Эйлеру, оценивает производную в середине и использует её на полном шаге. Это двухстадийная схема Рунге — Кутты второго порядка.
Метод Хойна: явное усреднение двух наклонов $k_1=f(t_n,y_n),\quad k_2=f(t_n+h,y_n+hk_1),\quad y_{n+1}=y_n+\frac h2(k_1+k_2)$ Численные методы ОДУ В этой двухстадийной схеме сначала делают прогноз Эйлера на полный шаг, затем усредняют начальный и прогнозный конечный наклоны. Метод имеет второй порядок, но названия его вариантов различаются в литературе.
Классический метод Рунге — Кутты четвёртого порядка $\begin{aligned}k_1&=f(t_n,y_n),&k_2&=f(t_n+h/2,y_n+hk_1/2),\\k_3&=f(t_n+h/2,y_n+hk_2/2),&k_4&=f(t_n+h,y_n+hk_3),\\y_{n+1}&=y_n+\frac h6(k_1+2k_2+2k_3+k_4).\end{aligned}$ Численные методы ОДУ Классический RK4 вычисляет четыре наклона за шаг и объединяет их с весами 1:2:2:1. Для гладкой задачи Коши он даёт четвёртый порядок общей ошибки без явного вычисления высших производных.
Поиск в ширину: кратчайший путь по числу рёбер $d(s)=0,\qquad d(v)=d(u)+1\quad\text{при первом открытии }v\text{ из }u$ Алгоритмы и анализ данных Поиск в ширину, или BFS, находит минимальное число переходов от стартовой вершины в невзвешенном графе. Очередь обрабатывает вершины слоями, поэтому первое открытие уже задаёт кратчайшее расстояние.
Алгоритм Дейкстры: релаксация и кратчайшие расстояния $d(v)\leftarrow\min\bigl(d(v),d(u)+w(u,v)\bigr),\qquad w(u,v)\geq0$ Алгоритмы и анализ данных Алгоритм Дейкстры находит кратчайшие пути от одной вершины при неотрицательных весах рёбер. На каждом шаге окончательно выбирается ещё не выбранная вершина с минимальной текущей меткой.
Алгоритм Беллмана — Форда: путь с отрицательными весами $d_k(v)=\min\left(d_{k-1}(v),\min_{(u,v)\in E}\{d_{k-1}(u)+w(u,v)\}\right)$ Алгоритмы и анализ данных Алгоритм Беллмана — Форда уточняет расстояния последовательными проходами по рёбрам. Он допускает отрицательные веса и позволяет обнаружить отрицательный цикл, достижимый из выбранного источника.
Алгоритм Флойда — Уоршелла: пути между всеми парами $d_{ij}^{(k)}=\min\left(d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)}\right)$ Алгоритмы и анализ данных Алгоритм Флойда — Уоршелла находит расстояния между всеми парами вершин, последовательно разрешая новые промежуточные вершины. Его основа — сравнение прямого известного маршрута с маршрутом через очередную вершину.
Алгоритм Краскала: вес минимального остовного дерева $T\in\underset{\text{остовные деревья }S}{\operatorname{arg\,min}}\sum_{e\in S}w(e),\qquad |T|=V-1$ Алгоритмы и анализ данных Алгоритм Краскала строит минимальное остовное дерево неориентированного графа: перебирает рёбра по возрастанию веса и принимает только те, которые соединяют разные текущие компоненты.
Линейная интерполяция: значение между двумя узлами $P(x)=y_0+\frac{y_1-y_0}{x_1-x_0}(x-x_0)=(1-t)y_0+ty_1,\quad t=\frac{x-x_0}{x_1-x_0}$ Интерполяция Линейная интерполяция оценивает значение между двумя заданными точками по соединяющей их прямой. Доля положения внутри интервала задаёт веса концов; оценка учитывает наклон, но не кривизну исходного графика.
Интерполяция Лагранжа: полином через заданные точки $P_n(x)=\sum_{k=0}^{n}y_kL_k(x),\qquad L_k(x)=\prod_{\substack{0\leq j\leq n\\j\ne k}}\frac{x-x_j}{x_k-x_j}$ Интерполяция Формула Лагранжа строит полином степени не выше n по n+1 различным узлам. Каждый базисный множитель выбирает значение своего узла и обращает вклады остальных узлов в ноль.
Интерполяция Ньютона: таблица разделённых разностей $P_n(x)=f[x_0]+\sum_{k=1}^{n}f[x_0,\ldots,x_k]\prod_{j=0}^{k-1}(x-x_j),\quad f[x_i,\ldots,x_j]=\frac{f[x_{i+1},\ldots,x_j]-f[x_i,\ldots,x_{j-1}]}{x_j-x_i}$ Интерполяция Форма Ньютона строит интерполяционный полином по треугольной таблице разделённых разностей. Новый узел добавляет коэффициент при очередном произведении, не требуя переписывать уже найденные нижние порядки.
Кубическая интерполяция Эрмита по значениям и наклонам $H(x)=h_{00}(s)y_0+h_{10}(s)\ell m_0+h_{01}(s)y_1+h_{11}(s)\ell m_1,\quad s=\frac{x-x_0}{\ell},\quad \ell=x_1-x_0$ Интерполяция Кубический полином Эрмита согласует значения и первые производные на двух концах интервала. Четыре заданных условия определяют единственную кубическую или более простую кривую между узлами.
Барицентрическая интерполяция: веса и вычисление полинома $P(x)=\frac{\sum_{k=0}^{n}\dfrac{w_ky_k}{x-x_k}}{\sum_{k=0}^{n}\dfrac{w_k}{x-x_k}},\qquad w_k=\frac{1}{\prod_{j\ne k}(x_k-x_j)},\quad x\ne x_k$ Интерполяция Барицентрическая форма вычисляет полином Лагранжа через заранее рассчитанные веса узлов. Она удобна для множества запросов по одной таблице; при точном совпадении аргумента с узлом нужно сразу вернуть узловое значение.
Число Прандтля: диффузия импульса и тепла $\mathrm{Pr}=\frac{\nu}{\alpha}=\frac{\mu c_p}{k},\qquad \alpha=\frac{k}{\rho c_p}$ Теплопередача Число Прандтля сравнивает кинематическую вязкость с температуропроводностью. Оно показывает соотношение молекулярного переноса импульса и тепла и при заданном состоянии среды не зависит от скорости или длины объекта.
Тепловое число Пекле: перенос потоком и теплопроводность $\mathrm{Pe}_T=\frac{UL}{\alpha}=\mathrm{Re}_L\mathrm{Pr},\qquad \mathrm{Re}_L=\frac{UL}{\nu}$ Теплопередача Тепловое число Пекле сравнивает перенос температуры движущейся средой с тепловой диффузией на длине L. Большое значение указывает на быстрый перенос потоком относительно выравнивания температуры на этом масштабе.
Число Шмидта: вязкость и диффузия компонента $\mathrm{Sc}=\frac{\nu}{D}=\frac{\mu}{\rho D}$ Гидравлика Число Шмидта сравнивает молекулярную диффузию импульса и выбранного компонента смеси. Оно зависит от свойств среды и пары веществ, а не от скорости или длины потока при неизменном состоянии.
Число Фруда: скорость потока и гравитационные волны $\mathrm{Fr}=\frac{U}{\sqrt{gL}},\qquad L=\frac{A}{B}\ \text{для открытого русла}$ Гидравлика Число Фруда сравнивает скорость потока с гравитационным масштабом √(gL). В открытом русле длиной служит гидравлическая глубина, поэтому критерий помогает различать докритическое и сверхкритическое течение.
Число Вебера: инерция и поверхностное натяжение $\mathrm{We}=\frac{\rho U^2L}{\sigma}$ Гидравлика Число Вебера сравнивает инерционный и капиллярный масштабы давления. Оно полезно для капель и струй, но требует явного выбора скорости, плотности, размера и поверхностного натяжения между конкретными фазами.
Правая разность: производная по двум соседним значениям $f'(x)\approx D_h^+f(x)=\frac{f(x+h)-f(x)}{h},\qquad D_h^+f-f'=O(h)$ Численное дифференцирование Правая разность оценивает производную по значениям функции в текущем и следующем узле. Это удобная односторонняя схема у левой границы таблицы, но её ошибка обычно линейна по шагу.
Центральная разность для первой производной $f'(x)\approx D_hf(x)=\frac{f(x+h)-f(x-h)}{2h},\qquad D_hf-f'=O(h^2)$ Численное дифференцирование Центральная разность оценивает первую производную по двум узлам на одинаковом расстоянии слева и справа. Симметрия устраняет линейную по шагу ошибку и обычно даёт второй порядок точности.
Вторая производная по трём равноотстоящим узлам $f''(x)\approx Q_hf(x)=\frac{f(x+h)-2f(x)+f(x-h)}{h^2},\qquad Q_hf-f''=O(h^2)$ Численное дифференцирование Трёхточечная центральная схема оценивает вторую производную по отклонению центрального значения от среднего соседей. Она измеряет изменение наклона, а не сам наклон, и имеет второй порядок по шагу.
Пятиточечная формула первой производной $f'(x)\approx P_hf=\frac{f(x-2h)-8f(x-h)+8f(x+h)-f(x+2h)}{12h},\qquad P_hf-f'=O(h^4)$ Численное дифференцирование Пятиточечная центральная формула оценивает первую производную с четвёртым порядком по шагу. Для неё нужны четыре значения вокруг центра: вес самого центрального значения равен нулю.
Экстраполяция Ричардсона для численной производной $R_h=\frac{4D_{h/2}-D_h}{3},\qquad D_h=\frac{f(x+h)-f(x-h)}{2h},\qquad R_h-f'(x)=O(h^4)$ Численное дифференцирование Экстраполяция Ричардсона объединяет две центральные оценки производной на шагах h и h/2. При гладкой функции она сокращает ведущую ошибку второго порядка и даёт оценку четвёртого порядка.
Поиск в глубину: дерево обхода и времена входа и выхода $u\text{ — предок }v\iff t_{in}(u)<t_{in}(v)<t_{out}(v)<t_{out}(u),\quad u\ne v$ Алгоритмы и анализ данных Поиск в глубину, или DFS, полностью исследует одну ветвь графа перед возвратом к следующей. Времена входа и выхода образуют вложенные интервалы и позволяют проверять родство в дереве обхода.
Топологическая сортировка Кана по входящим степеням $d_{in}(v)\leftarrow d_{in}(v)-1\quad\text{при удалении дуги }u\to v;\qquad |L|=|V|\iff G\text{ ацикличен}$ Алгоритмы и анализ данных Алгоритм Кана упорядочивает вершины ориентированного графа, последовательно выбирая вершину без входящих дуг. Если вывести все вершины не удалось, оставшаяся часть содержит ориентированный цикл.
Сильные компоненты: два обхода алгоритма Косарайю $u\sim v\iff(u\leadsto v)\land(v\leadsto u),\qquad T=O(|V|+|E|)$ Алгоритмы и анализ данных Сильная компонента ориентированного графа объединяет вершины, достижимые друг из друга в обоих направлениях. Алгоритм Косарайю находит такие группы двумя обходами в глубину с разворотом всех дуг.
Мосты графа: критерий через времена входа и low $(v,u)\text{ — мост}\iff low(u)>t_{in}(v),\quad u\text{ — ребёнок }v\text{ в DFS}$ Алгоритмы и анализ данных Мост — ребро неориентированного графа, удаление которого увеличивает число компонент связности. DFS обнаруживает его, если поддерево ребёнка не имеет обходного ребра к родителю или его предкам.
Точки сочленения: критерий low и отдельное правило корня $v\ne root:\quad v\text{ — точка сочленения}\iff\exists u\text{ — ребёнок}:low(u)\ge t_{in}(v)$ Алгоритмы и анализ данных Точка сочленения — вершина, удаление которой вместе с инцидентными рёбрами увеличивает число компонент связности. Для некорневой вершины DFS использует нестрогое сравнение low ребёнка с временем входа.
Быстрое возведение в степень по модулю двоичным методом $a^n\bmod m,\qquad a^{2q}=(a^q)^2,\quad a^{2q+1}=a(a^q)^2$ Арифметика и теория чисел Двоичный метод вычисляет остаток большой степени, многократно возводя основание в квадрат и используя биты показателя. После каждого умножения можно брать остаток, не создавая огромного целого aⁿ.
Малая теорема Ферма: степени по простому модулю $a^{p-1}\equiv1\pmod p,\quad p\text{ простое},\quad p\nmid a$ Арифметика и теория чисел Малая теорема Ферма утверждает, что ненулевой остаток по простому модулю в степени p−1 даёт единицу. Она помогает сокращать большие показатели, если основание не делится на этот простой модуль.
Теорема Эйлера: сокращение степени по составному модулю $a^{\varphi(m)}\equiv1\pmod m,\qquad \gcd(a,m)=1,\quad m>1$ Арифметика и теория чисел Теорема Эйлера даёт единичный остаток для основания, взаимно простого с модулем, в степени φ(m). Она работает и с составным модулем, но не позволяет без проверки сокращать показатель любого основания.
Линейное сравнение: решения через НОД коэффициента и модуля $ax\equiv b\pmod m\text{ разрешимо}\iff d\mid b,\quad d=\gcd(a,m);\quad x=x_0+k\frac md,\ k=0,\ldots,d-1$ Арифметика и теория чисел Сравнение ax ≡ b по модулю m имеет решения тогда и только тогда, когда НОД(a,m) делит b. При выполнении условия получается ровно d разных классов по исходному модулю, где d — этот НОД.
Мультипликативный порядок: минимальный период степеней $\operatorname{ord}_m(a)=\min\{k\ge1:a^k\equiv1\pmod m\},\qquad\operatorname{ord}_m(a)\mid\varphi(m)$ Арифметика и теория чисел Мультипликативный порядок обратимого остатка — наименьшая положительная степень, в которой он возвращается к единице. Этот период делит φ(m) и позволяет сокращать показатели точнее, чем одна теорема Эйлера.