Связанные понятия
Двоичное дерево поиска (англ. binary search tree, BST) — это двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска)...
Красно-чёрное дерево (англ. Red-black tree, RB-Tree) — это одно из самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и быстро выполняющее основные операции дерева поиска: добавление, удаление и поиск узла. Сбалансированность достигается за счёт введения дополнительного атрибута узла дерева — «цвета». Этот атрибут может принимать одно из двух возможных значений — «чёрный» или «красный».
Основная теорема о рекуррентных соотношениях (англ. Master theorem) используется в анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй и властвуй» (divide and conquer), например, при оценке времени их выполнения. Теорема была популяризована в книге Алгоритмы: построение и анализ (Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн), в которой она была введена и доказана.
Итеративное сжатие — это алгоритмическая техника разработки фиксированно-параметрически разрешимых алгоритмов, в которой один элемент (такой как вершина графа) добавляется в задачу на каждом шаге и используется небольшое решение задачи перед добавлением элемента, чтобы найти небольшое решение задачи после добавления.
Дерево Фенвика (двоичное индексированное дерево, англ. Fenwick tree, binary indexed tree, BIT) — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Впервые описано Питером Фенвиком в 1994 году. Дерево Фенвика напоминает дерево отрезков, однако проще в реализации.
Алгоритм Эдмондса или алгоритм Чу — Лью/Эдмондса — это алгоритм поиска остовного ориентированного корневого дерева минимального веса (иногда называемого оптимальным ветвлением).
В математическом анализе и информатике кривая Мортона, Z-последовательность,Z-порядок, кривая Лебега, порядок Мортона или код Мортона — это функция, которая отображает многомерные данные в одномерные, сохраняя локальность точек данных. Функция была введена в 1966 Гаем Макдональдом Мортоном. Z-значение точки в многомерном пространстве легко вычисляется чередованием двоичных цифр его координатных значений. Когда данные запоминаются в этом порядке, могут быть использованы любые одномерные структуры...
Подробнее: Кривая Мортона
Обход дерева (известный также как поиск по дереву) — вид обхода графа, обусловливающий процесс посещения (проверки и/или обновления) каждого узла структуры дерева данных ровно один раз. Такие обходы классифицируются по порядку, в котором узлы посещаются. Алгоритмы в статье относятся к двоичным деревьям, но могут быть обобщены и для других деревьев.
Алгоритм Гельфонда — Шенкса (англ. Baby-step giant-step; также называемый алгоритмом больших и малых шагов) — в теории групп детерминированный алгоритм дискретного логарифмирования в мульпликативной группе кольца вычетов по модулю простого числа. Был предложен советским математиком Александром Гельфондом в 1962 году и Дэниэлем Шенксом в 1972 году.
Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения...
Префиксное дерево (также бор, луч, нагруженное дерево, англ. trie) — структура данных, позволяющая хранить ассоциативный массив, ключами которого являются строки. Представляет собой корневое дерево, каждое ребро которого помечено каким-то символом так, что для любого узла все рёбра, соединяющие этот узел с его сыновьями, помечены разными символами. Некоторые узлы префиксного дерева выделены (на рисунке они подписаны цифрами) и считается, что префиксное дерево содержит данную строку-ключ тогда и только...
Задача о самом широком пути — это задача нахождения пути между двумя выбранными вершинами во взвешенном графе, максимизирующего вес минимального по весу ребра графа (если рассматривать вес ребра как ширину дороги, то задача стоит в выборе самой широкой дороги, связывающей две вершины). Задача о самом широком пути известна также как задача об узком месте или задача о пути с максимальной пропускной способностью. Можно приспособить алгоритмы кратчайшего пути для вычисления пропускной способности путём...
Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей») — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за Θ(n log n) операций при сортировке n элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).
Двои́чное де́рево — иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. Двоичное дерево не является упорядоченным ориентированным деревом.Для практических целей обычно используют два подвида двоичных деревьев — двоичное дерево поиска и двоичная куча.
Алгоритм Флойда — Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом. При этом алгоритм впервые разработал и опубликовал Бернард Рой (англ. Bernard Roy) в 1959 году.
Блочная сортировка (Карманная сортировка, корзинная сортировка, англ. Bucket sort) — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем...
Универса́льное хеши́рование (англ. Universal hashing) — это вид хеширования, при котором используется не одна конкретная хеш-функция, а происходит выбор из заданного семейства по случайному алгоритму. Такой подход обеспечивает равномерное хеширование: для очередного ключа вероятности помещения его в любую ячейку совпадают. Известно несколько семейств универсальных хеш-функций, которые имеют многочисленные применения в информатике, в частности в хеш-таблицах, вероятностных алгоритмах и криптографии...
Очередь с приоритетом (англ. priority queue) — абстрактный тип данных в программировании, поддерживающий две обязательные операции — добавить элемент и извлечь максимум(минимум). Предполагается, что для каждого элемента можно вычислить его приоритет — действительное число или в общем случае элемент линейно упорядоченного множества.
Компромисс времени и памяти (англ. Space-time trade-off, «выбор оптимального соотношения „место-время“» (англ. space-time trade-off), или, иначе, «выбор оптимального соотношения „время-память“» (англ. time-memory trade-off)) — компромиссный подход к решению ряда задач в информатике, при котором используется обратное соотношение требуемого объёма памяти и скорости выполнения программы: время вычислений может быть увеличено за счёт уменьшения используемой памяти или, наоборот, снижено за счёт увеличения...
Алгоритм сжатия цветков (англ. Blossom algorithm) — это алгоритм в теории графов для построения наибольших паросочетаний на графах. Алгоритм разработал Джек Эдмондс в 1961 году и опубликовал в 1965 году. Если дан граф G=(V, E) общего вида, алгоритм находит паросочетание M такое, что каждая вершина из V инцидентна не более чем одному ребру из M и M максимально. Паросочетание строится путём итеративного улучшения начального пустого паросочетания вдоль увеличивающих путей графа. В отличие от двудольного...
Прошитое двоичное дерево — это вариант двоичного дерева, который позволяет быстрый обход — если дан указатель на узел в прошитом дереве, можно легко найти следующий по порядку узел (и/или предыдущий).
Распределением
регистров в процессе компиляции называется отображение множества большого числа переменных фрагмента компьютерной программы (виртуальных регистров промежуточного представления) на, как правило, небольшое множество физических регистров микропроцессора. Распределение регистров может выполняться в отдельно взятом базовом блоке (локальное распределение регистров) или во всей процедуре (глобальное распределение регистров).
Дерево квадрантов (также квадродерево, 4-дерево, англ. quadtree) — дерево, в котором у каждого внутреннего узла ровно 4 потомка. Деревья квадрантов часто используются для рекурсивного разбиения двухмерного пространства по 4 квадранта (области). Области представляют собой квадраты, прямоугольники или имеют произвольную форму. Англоязычный термин quadtree был придуман Рафаэлем Финкелем и Джоном Бентли в 1974 году. Аналогичное разбиение пространства известно как Q-дерево. Общие черты разных видов деревьев...
Удаление общих подвыражений (англ. Common subexpression elimination или CSE) — оптимизация компилятора, которая ищет в программе вычисления, выполняемые более одного раза на рассматриваемом участке, и удаляет вторую и последующие одинаковые операции, если это возможно и эффективно. Данная оптимизация требует проведения анализа потока данных для нахождения избыточных вычислений и практически всегда улучшает время выполнения программы в случае применения.
В комбинаторной оптимизации под линейной задачей о назначениях на узкие места (linear bottleneck assignment problem, LBAP) понимается задача, похожая на задачу о назначениях.
Подробнее: Линейная задача о назначениях в узких местах
В компьютерных науках ку́ча — это специализированная структура данных типа дерево, которая удовлетворяет свойству кучи: если B является узлом-потомком узла A, то ключ(A) ≥ ключ(B). Из этого следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами). Не существует никаких ограничений относительно того...
Подробнее: Куча (структура данных)
Алгоритм Брезенхе́ма (англ. Bresenham's line algorithm) — это алгоритм, определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками. Это один из старейших алгоритмов в машинной графике — он был разработан Джеком Элтоном Брезенхэмом (англ. Jack Elton Bresenham) в компании IBM в 1962 году. Алгоритм широко используется, в частности, для рисования линий на экране компьютера. Существует обобщение алгоритма Брезенхэма для построения...
Куб Фибоначчи можно определить в терминах кодов Фибоначчи и расстояния Хэмминга, независимых множеств вершин в путях, или через дистрибутивные решётки.
В теории информации
теорема Шеннона об источнике шифрования (или теорема бесшумного шифрования) устанавливает предел максимального сжатия данных и числовое значение энтропии Шеннона.
Топологическая сортировка — упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин.
Криптосистема Уильямса (Williams System) — система шифрования с открытым ключом, созданная Хью Коуи Уильямсом (Hugh Cowie Williams) в 1984 году.
Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.
Разделяй и властвуй (англ. divide and conquer) в информатике — важная парадигма разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче; разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.
Поиск с возвратом , бэктрекинг (англ. backtracking) — общий метод нахождения решений задачи, в которой требуется полный перебор всех возможных вариантов в некотором множестве М. Как правило позволяет решать задачи, в которых ставятся вопросы типа: «Перечислите все возможные варианты …», «Сколько существует способов …», «Есть ли способ …», «Существует ли объект…» и т. п.
Алгоритм Берлекэмпа — Мэсси — алгоритм поиска кратчайшего регистра сдвига с линейной обратной связью для поданной на вход бинарной последовательности. Также алгоритм позволяет найти минимальный многочлен поданной на вход линейной рекуррентной последовательности над произвольным полем.
Таблица поиска (англ. lookup table) — это структура данных, обычно массив или ассоциативный массив, используемая с целью заменить вычисления на операцию простого поиска. Увеличение скорости может быть значительным, так как получить данные из памяти зачастую быстрее, чем выполнить трудоёмкие вычисления.
Свёртка последовательностей — это результат перемножения элементов двух заданных числовых последовательностей таким образом, что члены одной последовательности берутся с возрастанием индексов, а члены другой — с убыванием (что и служит основанием для принятого названия данной операции).
Предобуславливание (также предобусловливание) — процесс преобразования условий задачи для её более корректного численного решения. Предобуславливание обычно связано с уменьшением числа обусловленности задачи. Предобуславливаемая задача обычно затем решается итерационным методом.
Тасование Фишера — Йетса (названо в честь Рональда Фишера и Франка Йетса (Frank Yates)), известное также под именем Тасование Кнута (в честь Дональда Кнута), — это алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества. Вариант тасования Фишера-Йетса, известный как алгоритм Саттоло (Sattolo), может быть использован для генерации случайного цикла перестановок длины n. Правильно реализованный алгоритм тасования Фишера-Йетса несмещённый, так...
Генерация столбцов или отложенная генерация столбцов — это эффективный подход к решению больших задач линейного программирования.
Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь (путь в неориентированном или ориентированном графе, который проходит все вершины графа ровно один раз) или гамильтонов цикл в заданном графе (ориентированном или неориентированном). Обе задачи NP-полны.
Задача о наименьшей окружности или задача о минимальном покрывающем круге — задача о вычислении наименьшей окружности, содержащей все заданные точки из множества на евклидовой плоскости.
Алгоритм для дерева сочленений — это метод, используемый в машинном обучении для извлечения маргинализации в графах общего вида. В сущности, алгоритм осуществляет распространение доверия на модифицированном графе, называемом деревом сочленений. Основная посылка алгоритма — исключить циклы путём кластеризации их в узлы.
Алгоритм «прямого-обратного» хода — алгоритм для вычисления апостериорных вероятностей последовательности состояний при наличии последовательности наблюдений. Иначе говоря, алгоритм, вычисляющий вероятность специфической последовательности наблюдений. Алгоритм применяется в трёх алгоритмах скрытых Марковских моделей.
Поиск в ширину (англ. breadth-first search, BFS) — метод обхода графа и поиска пути в графе. Поиск в ширину является одним из неинформированных алгоритмов поиска.
Двоичный алгоритм поиска подстроки (также bitap algorithm, shift-or algorithm) — алгоритм поиска подстроки, использующий тот факт, что в современных компьютерах битовый сдвиг и побитовое ИЛИ являются атомарными операциями. По сути, это примитивный алгоритм поиска с небольшой оптимизацией, благодаря которой за одну операцию производится до 32 сравнений одновременно (или до 64, в зависимости от разрядности машины). Легко переделывается на приблизительный поиск.