Связанные понятия
Двои́чное де́рево — иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. Двоичное дерево не является упорядоченным ориентированным деревом.Для практических целей обычно используют два подвида двоичных деревьев — двоичное дерево поиска и двоичная куча.
Распределением
регистров в процессе компиляции называется отображение множества большого числа переменных фрагмента компьютерной программы (виртуальных регистров промежуточного представления) на, как правило, небольшое множество физических регистров микропроцессора. Распределение регистров может выполняться в отдельно взятом базовом блоке (локальное распределение регистров) или во всей процедуре (глобальное распределение регистров).
Свя́зный спи́сок — базовая динамическая структура данных в информатике, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка. Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.
Дерево — одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связным графом, не содержащим циклы. Большинство источников также добавляют условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указывается, что рёбра графа не должны быть взвешенными.
Очередь с приоритетом (англ. priority queue) — абстрактный тип данных в программировании, поддерживающий две обязательные операции — добавить элемент и извлечь максимум(минимум). Предполагается, что для каждого элемента можно вычислить его приоритет — действительное число или в общем случае элемент линейно упорядоченного множества.
Префиксное дерево (также бор, луч, нагруженное дерево, англ. trie) — структура данных, позволяющая хранить ассоциативный массив, ключами которого являются строки. Представляет собой корневое дерево, каждое ребро которого помечено каким-то символом так, что для любого узла все рёбра, соединяющие этот узел с его сыновьями, помечены разными символами. Некоторые узлы префиксного дерева выделены (на рисунке они подписаны цифрами) и считается, что префиксное дерево содержит данную строку-ключ тогда и только...
Псевдоко́д — компактный (зачастую неформальный) язык описания алгоритмов, использующий ключевые слова императивных языков программирования, но опускающий несущественные подробности и специфический синтаксис. Псевдокод обычно опускает детали, несущественные для понимания алгоритма человеком. Такими несущественными деталями могут быть описания переменных, системно-зависимый код и подпрограммы. Главная цель использования псевдокода — обеспечить понимание алгоритма человеком, сделать описание более воспринимаемым...
Обход дерева (известный также как поиск по дереву) — вид обхода графа, обусловливающий процесс посещения (проверки и/или обновления) каждого узла структуры дерева данных ровно один раз. Такие обходы классифицируются по порядку, в котором узлы посещаются. Алгоритмы в статье относятся к двоичным деревьям, но могут быть обобщены и для других деревьев.
О́чередь — абстрактный тип данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, англ. first in, first out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.
Хеш-табли́ца — это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.
В математическом анализе и информатике кривая Мортона, Z-последовательность,Z-порядок, кривая Лебега, порядок Мортона или код Мортона — это функция, которая отображает многомерные данные в одномерные, сохраняя локальность точек данных. Функция была введена в 1966 Гаем Макдональдом Мортоном. Z-значение точки в многомерном пространстве легко вычисляется чередованием двоичных цифр его координатных значений. Когда данные запоминаются в этом порядке, могут быть использованы любые одномерные структуры...
Подробнее: Кривая Мортона
Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.
Дерево квадрантов (также квадродерево, 4-дерево, англ. quadtree) — дерево, в котором у каждого внутреннего узла ровно 4 потомка. Деревья квадрантов часто используются для рекурсивного разбиения двухмерного пространства по 4 квадранта (области). Области представляют собой квадраты, прямоугольники или имеют произвольную форму. Англоязычный термин quadtree был придуман Рафаэлем Финкелем и Джоном Бентли в 1974 году. Аналогичное разбиение пространства известно как Q-дерево. Общие черты разных видов деревьев...
Массив (в некоторых языках программирования также таблица, ряд, матрица) — структура данных, хранящая набор значений (элементов массива), идентифицируемых по индексу или набору индексов, принимающих целые (или приводимые к целым) значения из некоторого заданного непрерывного диапазона. Одномерный массив можно рассматривать как реализацию абстрактного типа данных вектор.
Алгоритм Гельфонда — Шенкса (англ. Baby-step giant-step; также называемый алгоритмом больших и малых шагов) — в теории групп детерминированный алгоритм дискретного логарифмирования в мульпликативной группе кольца вычетов по модулю простого числа. Был предложен советским математиком Александром Гельфондом в 1962 году и Дэниэлем Шенксом в 1972 году.
Граф потока управления (англ. control flow graph, CFG) — в теории компиляции — множество всех возможных путей исполнения программы, представленное в виде графa.
Таблица поиска (англ. lookup table) — это структура данных, обычно массив или ассоциативный массив, используемая с целью заменить вычисления на операцию простого поиска. Увеличение скорости может быть значительным, так как получить данные из памяти зачастую быстрее, чем выполнить трудоёмкие вычисления.
Конкатена́ция (лат. concatenatio «присоединение цепями; сцепле́ние») — операция склеивания объектов линейной структуры, обычно строк. Например, конкатенация слов «микро» и «мир» даст слово «микромир».
Основная теорема о рекуррентных соотношениях (англ. Master theorem) используется в анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй и властвуй» (divide and conquer), например, при оценке времени их выполнения. Теорема была популяризована в книге Алгоритмы: построение и анализ (Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн), в которой она была введена и доказана.
Свёртка списка (англ. folding, также известна как reduce, accumulate) в программировании — функция высшего порядка, которая производит преобразование структуры данных к единственному атомарному значению при помощи заданной функции. Операция свёртки часто используется в функциональном программировании при обработке списков. Свёртка может быть обобщена на произвольный алгебраический тип данных при помощи понятия катаморфизма из теории категорий.
Переписывание — широкий спектр техник, методов и теоретических результатов, связанных с процедурами последовательной замены частей формул или термов формального языка по заданной схеме — системе переписывающих правил.
Алгоритм сортировки — это алгоритм для упорядочивания элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
Разделяй и властвуй (англ. divide and conquer) в информатике — важная парадигма разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче; разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.
В компьютерных науках ку́ча — это специализированная структура данных типа дерево, которая удовлетворяет свойству кучи: если B является узлом-потомком узла A, то ключ(A) ≥ ключ(B). Из этого следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами). Не существует никаких ограничений относительно того...
Подробнее: Куча (структура данных)
Символьный тип (Сhar) — тип данных, предназначенный для хранения одного символа (управляющего или печатного) в определённой кодировке. Может являться как однобайтовым (для стандартной таблицы символов), так и многобайтовым (к примеру, для Юникода). Основным применением является обращение к отдельным знакам строки.
Универса́льное хеши́рование (англ. Universal hashing) — это вид хеширования, при котором используется не одна конкретная хеш-функция, а происходит выбор из заданного семейства по случайному алгоритму. Такой подход обеспечивает равномерное хеширование: для очередного ключа вероятности помещения его в любую ячейку совпадают. Известно несколько семейств универсальных хеш-функций, которые имеют многочисленные применения в информатике, в частности в хеш-таблицах, вероятностных алгоритмах и криптографии...
Поиск в ширину (англ. breadth-first search, BFS) — метод обхода графа и поиска пути в графе. Поиск в ширину является одним из неинформированных алгоритмов поиска.
Терна́рная усло́вная опера́ция (от лат. ternarius — «тройной») (обычно записывается как ?:) — во многих языках программирования операция, возвращающая свой второй или третий операнд в зависимости от значения логического выражения, заданного первым операндом. Как можно судить из названия, тернарная операция принимает всего три указанных операнда. Аналогом тернарной условной операции в математической логике и булевой алгебре является условная дизъюнкция, которая записывается в виде и реализует алгоритм...
Поиск с возвратом , бэктрекинг (англ. backtracking) — общий метод нахождения решений задачи, в которой требуется полный перебор всех возможных вариантов в некотором множестве М. Как правило позволяет решать задачи, в которых ставятся вопросы типа: «Перечислите все возможные варианты …», «Сколько существует способов …», «Есть ли способ …», «Существует ли объект…» и т. п.
Коллекция в программировании — программный объект, содержащий в себе, тем или иным образом, набор значений одного или различных типов, и позволяющий обращаться к этим значениям.
В информатике, спи́сок (англ. list) — это абстрактный тип данных, представляющий собой упорядоченный набор значений, в котором некоторое значение может встречаться более одного раза. Экземпляр списка является компьютерной реализацией математического понятия конечной последовательности.
Подробнее: Список (информатика)
Таблица — это совокупность связанных данных, хранящихся в структурированном виде в базе данных. Она состоит из столбцов и строк.
Итеративное сжатие — это алгоритмическая техника разработки фиксированно-параметрически разрешимых алгоритмов, в которой один элемент (такой как вершина графа) добавляется в задачу на каждом шаге и используется небольшое решение задачи перед добавлением элемента, чтобы найти небольшое решение задачи после добавления.
Алгоритм Берлекэмпа — Мэсси — алгоритм поиска кратчайшего регистра сдвига с линейной обратной связью для поданной на вход бинарной последовательности. Также алгоритм позволяет найти минимальный многочлен поданной на вход линейной рекуррентной последовательности над произвольным полем.
Алгоритм распространения доверия (англ. belief propagation, также алгоритм «sum-product») — алгоритм маргинализации с помощью двунаправленной передачи сообщений на графе, применяемый для вывода на графических вероятностных моделях (таких как байесовские и марковские сети). Предложен Дж. Перлом в 1982 году.
Опера́ция — конструкция в языках программирования, аналогичная по записи математическим операциям, то есть специальный способ записи некоторых действий.
Би́товая ка́рта (англ. bitmap, bitset, bit array) — набор последовательно записанных двоичных разрядов, то есть последовательность (массив) битов.
Сравне́ние в программировании — общее название ряда операций над па́рами значений одного типа, реализующих математические отношения равенства и порядка. В языках высокого уровня такие операции, чаще всего, возвращают булево значение («истина» или «ложь»).
Логи́ческий тип да́нных, или булев тип, или булевый тип (от англ. Boolean или logical data type) — примитивный тип данных в информатике, принимающий два возможных значения, иногда называемых истиной (true) и ложью (false). Присутствует в подавляющем большинстве языков программирования как самостоятельная сущность или реализуется через численный тип данных. В некоторых языках программирования за значение истина полагается 1, за значение ложь — 0.
АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
Хвостовая рекурсия — частный случай рекурсии, при котором любой рекурсивный вызов является последней операцией перед возвратом из функции. Подобный вид рекурсии примечателен тем, что может быть легко заменён на итерацию путём формальной и гарантированно корректной перестройки кода функции. Оптимизация хвостовой рекурсии путём преобразования её в плоскую итерацию реализована во многих оптимизирующих компиляторах. В некоторых функциональных языках программирования спецификация гарантирует обязательную...
Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей») — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за Θ(n log n) операций при сортировке n элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).
Структура данных (англ. data structure) — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.
Компромисс времени и памяти (англ. Space-time trade-off, «выбор оптимального соотношения „место-время“» (англ. space-time trade-off), или, иначе, «выбор оптимального соотношения „время-память“» (англ. time-memory trade-off)) — компромиссный подход к решению ряда задач в информатике, при котором используется обратное соотношение требуемого объёма памяти и скорости выполнения программы: время вычислений может быть увеличено за счёт уменьшения используемой памяти или, наоборот, снижено за счёт увеличения...
Псевдослуча́йная после́довательность (ПСП) — последовательность чисел, которая была вычислена по некоторому определённому арифметическому правилу, но имеет все свойства случайной последовательности чисел в рамках решаемой задачи.
Реку́рсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя. Термин «рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее широкое применение находит в математике и информатике.
Обучение дерева решений использует дерево решений (как предиктивную модель), чтобы перейти от наблюдений над объектами (представленными в ветвях) к заключениям о целевых значениях объектов (представленных в листьях). Это обучение является одним из подходов моделирования предсказаний, используемых в статистике, интеллектуальном анализе данных и обучении машин. Модели деревьев, в которых целевая переменная может принимать дискретный набор значений, называются деревьями классификации. В этих структурах...
Прошитое двоичное дерево — это вариант двоичного дерева, который позволяет быстрый обход — если дан указатель на узел в прошитом дереве, можно легко найти следующий по порядку узел (и/или предыдущий).
Вычисления с оракулом — вычисление с помощью машины Тьюринга, дополненной оракулом с неизвестным внутренним устройством.