Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому. Название алгоритма говорит о принципе его работы: алгоритм осуществляет фильтрацию списка чисел от 2 до n. По мере прохождения списка составные числа исключаются, а простые остаются.
Scheme [] — функциональный язык программирования, один из трёх наиболее популярных диалектов Лиспа. Создан в середине 1970-х годов исследователями Массачусетского технологического института Гаем Стилом и Джеральдом Сассменом.
Ассоциативный массив — абстрактный тип данных, позволяющий хранить пары вида «(ключ, значение)» и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу:
- INSERT(ключ, значение)
- FIND(ключ)
- REMOVE(ключ)
Быстрая сортировка, сортировка Хоара, часто называемая qsort — алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.
Список с пропусками — вероятностная структура данных, основанная на нескольких параллельных отсортированных связных списках с эффективностью, сравнимой с двоичным деревом.
«Разделяй и властвуй» в информатике — схема разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче; разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.
Дерево хешей — полное двоичное дерево, в листовые вершины которого помещены хеши от блоков данных, а внутренние вершины содержат хеши от сложения значений в дочерних вершинах. Корневой узел дерева содержит хеш от всего набора данных, то есть хеш-дерево является однонаправленной хеш-функцией. Применяется для эффективного хранения транзакций в блокчейне криптовалют. Оно позволяет получить «отпечаток» всех транзакций в блоке, а также эффективно верифицировать транзакции. Названо по имени Ральфа Меркла, предложившего в 1979 году соответствующую технику хеширования криптографических функций.
Устойчивая (стабильная) сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи, по которым происходит сортировка.
Сортировка Шелла — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расчёской.
В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе. Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, то есть при стремлении размера входа к бесконечности. Например, если существует число 
, такое, что время работы алгоритма для всех входов длины 
не превосходит 
, то временную сложность данного алгоритма можно асимптотически оценить как 
.
В информатике алгоритм выбора — это алгоритм для нахождения k-го по величине элемента в массиве (такой элемент называется k-й порядковой статистикой). Частными случаями этого алгоритма являются нахождение минимального элемента, максимального элемента и медианы. Существует алгоритм, который гарантированно решает задачу выбора k-го по величине элемента за O(n).
Разре́женная/разрежённая матрица — матрица с преимущественно нулевыми элементами. В противном случае, если бо́льшая часть элементов матрицы ненулевая, матрица считается плотной или заполненной.
Тест Аграва́ла — Кая́ла — Саксе́ны — единственный известный на данный момент универсальный полиномиальный, детерминированный и безусловный тест простоты чисел, основанный на обобщении малой теоремы Ферма на многочлены.
k-d-дерево — это структура данных с разбиением пространства для упорядочивания точек в k-мерном пространстве. k-d-деревья используются для некоторых приложений, таких как поиск в многомерном пространстве ключей. k-d-деревья — особый вид двоичных деревьев поиска.
Racket — мультипарадигменный язык программирования общего назначения, принадлежащий семейству Lisp/Scheme. Предоставляет среду языково-ориентированное программирование — одно из предназначений racket — создание, разработка и реализация языков программирования. Язык используется в различных контекстах: как скриптовый язык, как язык общего назначения, в обучении информатике, в научных исследованиях.
SWIFFT — набор криптографических хеш-функций с доказанной стойкостью. Они основываются на быстром преобразовании Фурье и используют алгоритм LLL-редуцированных базисов. Криптографическая стойкость функций SWIFFT математически доказана при использовании рекомендуемых параметров. Поиск коллизий в SWIFFT в худшем случае требует не меньше временных затрат, чем нахождение коротких векторов в циклических/идеальных решётках. Практическое применение SWIFFT будет ценно именно в тех случаях, когда стойкость к коллизиям особенно важна. Например, цифровые подписи, которые должны оставаться надёжными длительное время.
ECIES — это схема шифрования на открытых ключах, основанная на эллиптических кривых. Эта схема была предложена Виктором Шоупом в 2001 году. ECIES используется в различных стандартах, например, ANSI X9.63, IEEE 1363a, ISO 18033-2 и SECG SEC 1.
Кукушкин фильтр — это эффективная по памяти вероятностная структура данных, которая используется для проверки, принадлежит ли элемент множеству, подобно фильтру Блума. Возможны ложноположительные результаты, но не ложноотрицательные — другими словами, запрос возвращает либо «возможно, принадлежит множеству» или «точно не принадлежит». Кукушкин фильтр также позволяет удалять существующие элементы, что не умеет фильтр Блума. В дополнение к этому для приложений, которые хранят много элементов и нацелены на умеренно низкую долю ложноположительных результатов, кукушкин фильтр позволяет добиться меньших затрат по памяти, чем оптимизированный по памяти фильтр Блума.
Falcon — постквантовый алгоритм криптографической подписи поверх решёток NTRU.
