Связанные понятия
В теории информации
теорема Шеннона об источнике шифрования (или теорема бесшумного шифрования) устанавливает предел максимального сжатия данных и числовое значение энтропии Шеннона.
Рациональное решето — это алгоритм общего вида для разложения целых чисел на простые множители. Алгоритм является частным случаем общего метода решета числового поля. Хотя он менее эффективен, чем общий алгоритм, концептуально он проще. Алгоритм может помочь понять, как работает общий метод решета числового поля.
Алгоритм «прямого-обратного» хода — алгоритм для вычисления апостериорных вероятностей последовательности состояний при наличии последовательности наблюдений. Иначе говоря, алгоритм, вычисляющий вероятность специфической последовательности наблюдений. Алгоритм применяется в трёх алгоритмах скрытых Марковских моделей.
Основная теорема о рекуррентных соотношениях (англ. Master theorem) используется в анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй и властвуй» (divide and conquer), например, при оценке времени их выполнения. Теорема была популяризована в книге Алгоритмы: построение и анализ (Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн), в которой она была введена и доказана.
Свёртка последовательностей — это результат перемножения элементов двух заданных числовых последовательностей таким образом, что члены одной последовательности берутся с возрастанием индексов, а члены другой — с убыванием (что и служит основанием для принятого названия данной операции).
Предобуславливание (также предобусловливание) — процесс преобразования условий задачи для её более корректного численного решения. Предобуславливание обычно связано с уменьшением числа обусловленности задачи. Предобуславливаемая задача обычно затем решается итерационным методом.
Алгоритм Гельфонда — Шенкса (англ. Baby-step giant-step; также называемый алгоритмом больших и малых шагов) — в теории групп детерминированный алгоритм дискретного логарифмирования в мульпликативной группе кольца вычетов по модулю простого числа. Был предложен советским математиком Александром Гельфондом в 1962 году и Дэниэлем Шенксом в 1972 году.
Праймориал (англ. Primorial, иногда именуется также «примориал») — в теории чисел функция над рядом натуральных чисел, схожая с функцией факториала, с разницей в том, что праймориал является последовательным произведением простых чисел, меньших или равных данному, в то время как факториал является последовательным произведением всех натуральных чисел, меньших или равных данному.
В гомологической алгебре и алгебраической топологии спектральная последовательность — это средство вычисления групп гомологий путём последовательных приближений. С момента их введения Жаном Лере они стали важным вычислительным средством, особенно в алгебраической топологии, алгебраической геометрии и гомологической алгебре.
Подробнее: Спектральная последовательность
Множество больших тригонометрических сумм — понятие теории чисел — множество индексов, в которых преобразование Фурье характеристической функции заданного подмножества группы принимает достаточно большие значения.
Проблема остановки (или проблема останова) — это одна из центральных проблем в теории алгоритмов, которая может неформально быть поставлена в виде...
Скорость сходимости является основной характеристикой численных методов решения уравнений и оптимизации.
В прикладной статистике метод наименьших полных квадратов (МНПК, TLS — англ. Total Least Squares) — это вид регрессии с ошибками в переменных, техника моделирования данных с помощью метода наименьших квадратов, в которой принимаются во внимание ошибки как в зависимых, так и в независимых переменных. Метод является обобщением регрессии Деминга и ортогональной регрессии и может быть применён как к линейным, так и нелинейным моделям.
Сглаживающие операторы — это гладкие функции со специальными свойствами, используемые в теории распределений для построения последовательности гладких функций, приближающей негладкую (обобщённую) функцию с помощью свёртки. Интуитивно, имея функцию с особенностями и осуществляя её свёртку со сглаживающей функцией, получаем «сглаженную функцию», в которой особенности исходной функции сглажены, хотя функция остаётся близкой к исходной функции. Операторы известны также как сглаживающие операторы Фридрихса...
Подробнее: Сглаживающий оператор
Задача о наименьшей окружности или задача о минимальном покрывающем круге — задача о вычислении наименьшей окружности, содержащей все заданные точки из множества на евклидовой плоскости.
Лемма разветвления (англ. Forking lemma) — лемма в области криптографических исследований.
Криптосистема Уильямса (Williams System) — система шифрования с открытым ключом, созданная Хью Коуи Уильямсом (Hugh Cowie Williams) в 1984 году.
Обратимый клеточный автомат — клеточный автомат, в котором каждое состояние имеет единственного предшественника. Таким образом, это регулярная решётка из ячеек, состояние каждой из которых берётся из конечного множества состояний, и правило для одновременного обновления состояний ячеек, исходя из состояний её соседей. Условие обратимости заключается в том, что предыдущее состояние любой ячейки может быть определено, зная обновлённые состояния всех ячеек решётки. После обращения времени получается...
Дифференциальная приватность — совокупность методов, которые обеспечивают максимально точные запросы в статистическую базу данных при одновременной минимизации возможности идентификации отдельных записей в ней.
Безопасное простое число — это простое число вида 2p + 1, где p также простое (и наоборот, p есть простое число Софи Жермен). Несколько первых безопасных простых чисел...
Мультииндекс (или мульти-индекс) — обобщение понятия целочисленного индекса до векторного индекса, которое нашло применение в различных областях математики, связанных с функциями многих переменных. Использование мультииндекса помогает упростить (записать более кратко) математические формулы.
Метод неопределённых коэффициентов ― метод, используемый в математике для нахождения искомой функции в виде точной или приближённой линейной комбинации конечного или бесконечного набора базовых функций.
Вероятностное округление — это широко используемый подход для разработки и анализа таких аппроксимационных алгоритмов. Базовая идея — использование вероятностного метода для преобразования соответствующей оптимального решения задачи линейного программирования (ЛП) в приближённое к оптимальному решению исходной задачи.
Геометрический центр дискретного множества точек евклидова пространства (говоря статистическим языком — выборки) — это точка, в которой минимизируется сумма расстояний до точек множества. Геометрический центр обобщает медиану в математической статистике, которая минимизирует расстояния в одномерной выборке данных. Таким образом, геометрический центр отражает центральную тенденцию в пространствах высокой размерности. Понятие известно также по названиям 1-медиана , пространственная медиана, или точка...
Многоме́рное норма́льное распределе́ние (или многоме́рное га́уссовское распределе́ние) в теории вероятностей — это обобщение одномерного нормального распределения. Случайный вектор, имеющий многомерное нормальное распределение, называется гауссовским вектором.
В комбинаторной оптимизации под линейной задачей о назначениях на узкие места (linear bottleneck assignment problem, LBAP) понимается задача, похожая на задачу о назначениях.
Подробнее: Линейная задача о назначениях в узких местах
Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.
Нера́венство Ма́ркова в теории вероятностей даёт оценку вероятности, что случайная величина превзойдёт по модулю фиксированную положительную константу, в терминах её математического ожидания. Хотя получаемая оценка обычно груба, она позволяет получить определённое представление о распределении, когда последнее не известно явным образом.
Циклическое число — целое число, циклические перестановки цифр которого являются произведениями этого числа на последовательные числа. Наиболее известный пример такого числа — 142857...
Задача разбиения множества чисел — это задача определения, можно ли данное мультимножество S положительных целых чисел разбить на два подмножества S1 и S2, таких, что сумма чисел из S1 равна сумме чисел из S2. Хотя задача разбиения чисел является NP-полной, существует решение псевдополиномиального времени методом динамического программирования существуют эвристические алгоритмы решения для многих конкрентных задач либо оптимально, либо приближённо. По этой причине задачу называют "простейшей NP-трудной...
Проклятие размерности (ПР) — термин, используемый в отношении ряда свойств многомерных пространств и комбинаторных задач. В первую очередь это касается экспоненциального роста необходимых экспериментальных данных в зависимости от размерности пространства при решении задач вероятностно-статистического распознавания образов, машинного обучения, классификации и дискриминантного анализа. Также это касается экспоненциального роста числа вариантов в комбинаторных задачах в зависимости от размера исходных...
Алгоритм Баума — Велша используется в информатике и статистике для нахождения неизвестных параметров скрытой марковской модели (HMM). Он использует алгоритм прямого-обратного хода и является частным случаем обобщённого EM-алгоритма.
В настоящее время отсутствует единое определение точно решаемой задачи для всех разделов математики. Это обусловлено особенностями самих задач и методов поиска их решения. Вместе с тем базовые теоремы, определяющие наличие и единственность решений, строятся на общих принципах, что будет показано ниже.
Подробнее: Точнорешаемая задача
Универса́льное хеши́рование (англ. Universal hashing) — это вид хеширования, при котором используется не одна конкретная хеш-функция, а происходит выбор из заданного семейства по случайному алгоритму. Такой подход обеспечивает равномерное хеширование: для очередного ключа вероятности помещения его в любую ячейку совпадают. Известно несколько семейств универсальных хеш-функций, которые имеют многочисленные применения в информатике, в частности в хеш-таблицах, вероятностных алгоритмах и криптографии...
Строковое ядро — это ядерная функция, определённая на строках, т.е. конечных последовательностях символов, которые не обязательно имеют одну и ту же длину. Строковые ядра можно интуитивно понимать как функции, измеряющие похожесть пар строк — чем больше похожи две строки a и b, тем больше значение строкового ядра K(a, b).
Семплирование по Гиббсу — алгоритм для генерации выборки совместного распределения множества случайных величин. Он используется для оценки совместного распределения и для вычисления интегралов методом Монте-Карло. Этот алгоритм является частным случаем алгоритма Метрополиса-Гастингса и назван в честь физика Джозайи Гиббса.
Параметрическая редукция — это техника для разработки эффективных алгоритмов, которые достигают своей эффективности путём препроцессорного шага, в котором вход алгоритма заменяется на меньший вход, называемый «ядром». Результат решения задачи на ядре должен быть либо тем же самым, что и при исходных данных, либо выход решения для ядра должен легко преобразовываться в желаемый выход исходной задачи.
Совершенное множество — замкнутое множество, не имеющее изолированных точек, то есть совпадающее с множеством всех своих предельных точек.
Формальное дифференцирование — операция над элементами кольца многочленов или кольцом формальных степенных рядов, повторяющая форму производных из математического анализа. Алгебраическое преимущество формального дифференцирования состоит в том, что оно не опирается на понятие предела, которое в общем случае невозможно определить для кольца. Многие свойства производной верны для формального дифференцирования, но некоторые, особенно касающиеся утверждений, содержащих числа, не верны. В основном формальное...
В теории вероятностей случайная величина имеет дискретное равномерное распределение, если она принимает конечное число значений с равными вероятностями.
Подробнее: Дискретное равномерное распределение
Оккамово обучение в теории вычислительного обучения является моделью алгоритмического обучения, где целью обучения является получение сжатого представления имеющихся тренировочных данных. Метод тесно связан с почти корректным обучением (ПК обучение, англ. Probably Approximately Correct learning, PAC learning), где учитель оценивает прогнозирующую способность тестового набора.
Усло́вное распределе́ние в теории вероятностей — это распределение случайной величины при условии, что другая случайная величина принимает определённое значение.
Ме́тоды Ру́нге — Ку́тты (в литературе встречаются названия: ме́тоды Ру́нге — Ку́тта или же ме́тоды Ру́нге — Кутта́) — большой класс численных методов решения задачи Коши для обыкновенных дифференциальных уравнений и их систем. Первые методы данного класса были предложены около 1900 года немецкими математиками К. Рунге и М. В. Куттой.