Связанные понятия
Итеративное сжатие — это алгоритмическая техника разработки фиксированно-параметрически разрешимых алгоритмов, в которой один элемент (такой как вершина графа) добавляется в задачу на каждом шаге и используется небольшое решение задачи перед добавлением элемента, чтобы найти небольшое решение задачи после добавления.
Свёртка последовательностей — это результат перемножения элементов двух заданных числовых последовательностей таким образом, что члены одной последовательности берутся с возрастанием индексов, а члены другой — с убыванием (что и служит основанием для принятого названия данной операции).
Однородные координаты ―
система координат , используемая в проективной геометрии, подобно тому, как декартовы координаты используются в евклидовой геометрии.
Параметрическое представление — используемая в математическом анализе разновидность представления переменных, когда их зависимость выражается через дополнительную величину — параметр.
Основная теорема о рекуррентных соотношениях (англ. Master theorem) используется в анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй и властвуй» (divide and conquer), например, при оценке времени их выполнения. Теорема была популяризована в книге Алгоритмы: построение и анализ (Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн), в которой она была введена и доказана.
Диаграмма Вороного конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу множества.
Предобуславливание (также предобусловливание) — процесс преобразования условий задачи для её более корректного численного решения. Предобуславливание обычно связано с уменьшением числа обусловленности задачи. Предобуславливаемая задача обычно затем решается итерационным методом.
Бесконечная группа — группа с бесконечным числом элементов, в противоположность конечным группам.
Два-граф ы не являются графами, и их не следует путать с другими объектами, которые называются 2-графами в теории графов, в частности, с 2-регулярными графами. Для их различения используется слово «два», а не цифра «2».
Кососимметрический граф — это ориентированный граф, который изоморфен своему собственному транспонированному графу, графу, образованному путём обращения всех дуг, с изоморфизмом, который является инволюцией без неподвижных точек. Кососимметрические графы идентичны двойным покрытиям двунаправленных графов.
Инверсия кривой — результат применения операции инверсии к заданной кривой C. По отношению к фиксированной окружности с центром O и радиусом k инверсия точки Q — это точка P, лежащая на луче OQ, и OP•OQ = k2. Инверсия кривой C — это множество всех точек P, являющихся инверсиями точек Q, принадлежащих кривой C. Точка O в этом построении называется центром инверсии, окружность называется окружностью инверсии, а k — радиусом инверсии.
Алгоритм Баума — Велша используется в информатике и статистике для нахождения неизвестных параметров скрытой марковской модели (HMM). Он использует алгоритм прямого-обратного хода и является частным случаем обобщённого EM-алгоритма.
Матрица жёсткости (матрица Дирихле) — матрица особого вида, использующаяся в методе конечных элементов для решения дифференциальных уравнений в частных производных. Она применяется при решениях задач электродинамики и механики.
Задача о змее в коробке в теории графов и информатике имеет дело с поиском определённого вида пути вдоль рёбер гиперкуба. Этот путь начинается с одного угла и проходит вдоль рёбер столько углов, сколько он может достичь. После того как достигается новый угол, предыдущий угол и все его соседи делаются недопустимыми для использования. Путь никогда не должен проходить через угол после того, как он помечен как недопустимый.
Алгоритм Эдмондса или алгоритм Чу — Лью/Эдмондса — это алгоритм поиска остовного ориентированного корневого дерева минимального веса (иногда называемого оптимальным ветвлением).
В прикладной статистике метод наименьших полных квадратов (МНПК, TLS — англ. Total Least Squares) — это вид регрессии с ошибками в переменных, техника моделирования данных с помощью метода наименьших квадратов, в которой принимаются во внимание ошибки как в зависимых, так и в независимых переменных. Метод является обобщением регрессии Деминга и ортогональной регрессии и может быть применён как к линейным, так и нелинейным моделям.
Весовая функция — математическая конструкция, используемая при проведении суммирования, интегрирования или усреднения с целью придания некоторым элементам большего веса в результирующем значении по сравнению с другими элементами. Задача часто возникает в статистике и математическом анализе, тесно связана с теорией меры. Весовые функции могут быть использованы как для дискретных, так и для непрерывных величин.
Сглаживающие операторы — это гладкие функции со специальными свойствами, используемые в теории распределений для построения последовательности гладких функций, приближающей негладкую (обобщённую) функцию с помощью свёртки. Интуитивно, имея функцию с особенностями и осуществляя её свёртку со сглаживающей функцией, получаем «сглаженную функцию», в которой особенности исходной функции сглажены, хотя функция остаётся близкой к исходной функции. Операторы известны также как сглаживающие операторы Фридрихса...
Подробнее: Сглаживающий оператор
Задача о самом широком пути — это задача нахождения пути между двумя выбранными вершинами во взвешенном графе, максимизирующего вес минимального по весу ребра графа (если рассматривать вес ребра как ширину дороги, то задача стоит в выборе самой широкой дороги, связывающей две вершины). Задача о самом широком пути известна также как задача об узком месте или задача о пути с максимальной пропускной способностью. Можно приспособить алгоритмы кратчайшего пути для вычисления пропускной способности путём...
Интегра́л Пуассо́на — общее название математических формул, выражающих решение краевой задачи или начальной задачи для уравнений с частными производными некоторых типов.
В теории информации
теорема Шеннона об источнике шифрования (или теорема бесшумного шифрования) устанавливает предел максимального сжатия данных и числовое значение энтропии Шеннона.
Обра́тные гиперболи́ческие фу́нкции (известные также как а̀реафу́нкции или ареа-функции) — семейство элементарных функций, определяющихся как обратные функции к гиперболическим функциям. Эти функции определяют площадь сектора единичной гиперболы x2 − y2 = 1 аналогично тому, как обратные тригонометрические функции определяют длину дуги единичной окружности x2 + y2 = 1. Для этих функций часто используются обозначения arcsinh, arcsh, arccosh, arcch и т.д., хотя такие обозначения являются, строго говоря...
Гистогра́мма в математической статистике — это функция, приближающая плотность вероятности некоторого распределения, построенная на основе выборки из него.
В теории групп циклическая перестановка — это перестановка элементов некоторого множества X, которая переставляет элементы некоторого подмножества S множества X циклическим образом, сохраняя на месте остальные элементы X (т.е. отображая их в себя). Например, перестановка {1, 2, 3, 4}, переводящая 1 в 3, 3 в 2, 2 в 4 и 4 в 1 является циклической, в то время как перестановка, переводящая 1 в 3, 3 в 1, 2 в 4 и 4 в 2 циклической не является.
Многоме́рное норма́льное распределе́ние (или многоме́рное га́уссовское распределе́ние) в теории вероятностей — это обобщение одномерного нормального распределения. Случайный вектор, имеющий многомерное нормальное распределение, называется гауссовским вектором.
Алгоритм Брезенхе́ма (англ. Bresenham's line algorithm) — это алгоритм, определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками. Это один из старейших алгоритмов в машинной графике — он был разработан Джеком Элтоном Брезенхэмом (англ. Jack Elton Bresenham) в компании IBM в 1962 году. Алгоритм широко используется, в частности, для рисования линий на экране компьютера. Существует обобщение алгоритма Брезенхэма для построения...
Точка перегиба — точка плоской кривой, в которой её ориентированная кривизна меняет знак. Если кривая является графиком функции, то в этой точке выпуклая часть функции отделяется от вогнутой (то есть вторая производная функции меняет знак).
У определённых функторов можно взять производные функторы чтобы получить другие функторы, тесно связанные с исходными. Данная операция является довольно абстрактной, но объединяет большое количество конструкций в математике.
Подробнее: Производный функтор
Дифференциальная геометрия кривых — раздел дифференциальной геометрии, который занимается исследованием гладких пространственных и плоских кривых в евклидовом пространстве аналитическими методами.
Алгоритм Гельфонда — Шенкса (англ. Baby-step giant-step; также называемый алгоритмом больших и малых шагов) — в теории групп детерминированный алгоритм дискретного логарифмирования в мульпликативной группе кольца вычетов по модулю простого числа. Был предложен советским математиком Александром Гельфондом в 1962 году и Дэниэлем Шенксом в 1972 году.
Скорость сходимости является основной характеристикой численных методов решения уравнений и оптимизации.
Координаты Борна в специальной теории относительности — система координат, применяемая для описания вращающейся окружности или (в более общем смысле) диска.
О дискретном эквиваленте преобразования Лапласа см. Z-преобразование.В математике дискретный оператор Лапласа — аналог непрерывного оператора Лапласа, определяемого как отношения на графе или дискретной сетке. В случае конечномерного графа (имеющего конечное число вершин и рёбер) дискретный оператор Лапласа имеет более общее название: матрица Лапласа.
Подробнее: Дискретный оператор Лапласа
Геометрический остов (англ. geometric spanner) или t-остовной граф, или t-остов первоначально был введён как взвешенный граф на множестве точек в качестве вершин, для которого существует t-путь между любой парой вершин для фиксированного параметра t. t-Путь определяется как путь в графе с весом, не превосходящим в t раз пространственное расстояние между конечными точками. Параметр t называется коэффициентом растяжения остова.
Сдвиг среднего значения — это непараметрическая техника анализа пространства признаков для определения местоположения максимума плотности вероятности, так называемый алгоритм поиска моды. Область применения техники — кластерный анализ в компьютерном зрении и обработке изображений.
Магма (группоид) в общей алгебре — алгебра, состоящая из множества М с одной бинарной операцией M × M → M. Помимо требования замкнутости множества относительно заданной на нём операции, других требований к операции и множеству не предъявляется.
Кусочно-линейная функция — функция, определённая на множестве вещественных чисел, линейная на каждом из интервалов, составляющих область определения.
Аффи́нное преобразование , иногда Афинное преобразование (от лат. affinis «соприкасающийся, близкий, смежный») — отображение плоскости или пространства в себя, при котором параллельные прямые переходят в параллельные прямые, пересекающиеся — в пересекающиеся, скрещивающиеся — в скрещивающиеся.
Триангуля́ция Делоне ́ — триангуляция для заданного множества точек S на плоскости, при которой для любого треугольника все точки из S за исключением точек, являющихся его вершинами, лежат вне окружности, описанной вокруг треугольника. Обозначается DT(S). Впервые описана в 1934 году советским математиком Борисом Делоне.
Касательное пространство Зарисского — конструкция в алгебраической геометрии, позволяющая построить касательное пространство в точке алгебраического многообразия. Эта конструкция использует не методы дифференциальной геометрии, а только методы общей, и, в более конкретных ситуациях, линейной алгебры.
Полукольцо — общеалгебраическая структура, похожая на кольцо, но без требования существования противоположного по сложению элемента.
Алгоритм распространения доверия (англ. belief propagation, также алгоритм «sum-product») — алгоритм маргинализации с помощью двунаправленной передачи сообщений на графе, применяемый для вывода на графических вероятностных моделях (таких как байесовские и марковские сети). Предложен Дж. Перлом в 1982 году.
Особая точка кривой — точка, в окрестности которой не существует гладкой параметризации. Точное определение зависит от типа изучаемой кривой.
Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.