Вероя́тность — степень возможности наступления некоторого события. Когда основания для того, чтобы какое-нибудь возможное событие произошло в действительности, перевешивают противоположные основания, то это событие называют вероятным, в противном случае — маловероятным или невероятным. Перевес положительных оснований над отрицательными, и наоборот, может быть в различной степени, вследствие чего вероятность бывает большей либо меньшей. Поэтому часто вероятность оценивается на качественном уровне, особенно в тех случаях, когда более или менее точная количественная оценка невозможна или крайне затруднена. Возможны различные градации «уровней» вероятности.
Коне́чный автома́т (КА) в теории алгоритмов — математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. Является частным случаем абстрактного дискретного автомата, число возможных внутренних состояний которого конечно.
Генератор псевдослучайных чисел — алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению.
Запаздывающие генераторы Фибоначчи — генераторы псевдослучайных чисел, также называемые аддитивными генераторами.
Случайный граф — общий термин для обозначения вероятностного распределения графов. Случайные графы можно описать просто распределением вероятности или случайным процессом, создающим эти графы. Теория случайных графов находится на стыке теории графов и теории вероятностей. С математической точки зрения случайные графы необходимы для ответа на вопрос о свойствах типичных графов. Случайные графы нашли практическое применение во всех областях, где нужно смоделировать сложные сети — известно большое число случайных моделей графов, отражающих разнообразные типы сложных сетей в различных областях. В математическом контексте термин случайный граф означает почти всегда модель случайных графов Эрдёша — Реньи. В других контекстах любая модель графов означает случайный граф.
Хеш-функция, или функция свёртки — функция, осуществляющая преобразование массива входных данных произвольной длины в выходную битовую строку установленной длины, выполняемое определённым алгоритмом. Преобразование, производимое хеш-функцией, называется хешированием. Исходные данные называются входным массивом, «ключом» или «сообщением». Результат преобразования называется «хешем», «хеш-кодом», «хеш-суммой», «сводкой сообщения».
Методы Мо́нте-Ка́рло (ММК) — группа численных методов для изучения случайных процессов. Суть метода заключается в следующем: процесс описывается математической моделью с использованием генератора случайных величин, модель многократно обсчитывается, на основе полученных данных вычисляются вероятностные характеристики рассматриваемого процесса. Например, чтобы узнать методом Монте-Карло, какое в среднем будет расстояние между двумя случайными точками в круге, нужно взять координаты большого числа случайных пар точек в границах заданной окружности, для каждой пары вычислить расстояние, а потом для них посчитать среднее арифметическое.
Блочная сортировка — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше, чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения.
Односторонняя функция — математическая функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Здесь «легко» и «трудно» должны пониматься с точки зрения теории сложности вычислений. Разрыв между сложностью прямого и обратного преобразований определяет криптографическую эффективность односторонней функции. Неинъективность функции не является достаточным условием для того, чтобы называть её односторонней. Односторонние функции могут называться также трудно обратимыми или необратимыми.
ECDSA (Elliptic Curve Digital Signature Algorithm) — алгоритм с открытым ключом, использующийся для построения и проверки электронной цифровой подписи при помощи криптографии на эллиптических кривых.
VMPC — это потоковый шифр, применяющийся в некоторых системах защиты информации в компьютерных сетях. Шифр разработан криптографом Бартошем Жултаком в качестве усиленного варианта популярного шифра RC4. Алгоритм VMPC строится как и любой потоковый шифр на основе параметризованного ключом генератора псевдослучайных битов. Основные преимущества шифра, как и RC4 — высокая скорость работы, переменный размер ключа и вектора инициализации, простота реализации.
Тео́рия алгори́тмов — раздел математики, изучающий общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п. Вместе с математической логикой теория алгоритмов образует теоретическую основу вычислительных наук, теории передачи информации, информатики, телекоммуникационных систем и других областей науки и техники.
Тестирование псевдослучайных последовательностей — совокупность методов определения меры близости заданной псевдослучайной последовательности к случайной. В качестве такой меры обычно выступает наличие равномерного распределения, большого периода, равной частоты появления одинаковых подстрок и т. п.
Тасование Фишера — Йетса (названо в честь Рональда Фишера и Фрэнка Йейтса, известно также под именем Тасование Кнута , — это алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества. Вариант тасования Фишера — Йетса, известный как алгоритм Саттоло , может быть использован для генерации случайного цикла перестановок длины n. Правильно реализованный алгоритм тасования Фишера — Йетса несмещённый, так что каждая перестановка генерируется с одинаковой вероятностью. Современная версия алгоритма очень эффективна и требует время, пропорциональное числу элементов множества, и не требует дополнительной памяти.
SWIFFT — набор криптографических хеш-функций с доказанной стойкостью. Они основываются на быстром преобразовании Фурье и используют алгоритм LLL-редуцированных базисов. Криптографическая стойкость функций SWIFFT математически доказана при использовании рекомендуемых параметров. Поиск коллизий в SWIFFT в худшем случае требует не меньше временных затрат, чем нахождение коротких векторов в циклических/идеальных решётках. Практическое применение SWIFFT будет ценно именно в тех случаях, когда стойкость к коллизиям особенно важна. Например, цифровые подписи, которые должны оставаться надёжными длительное время.
Reservoir sampling представляет собой семейство вероятностных алгоритмов произвольного выбора образца, состоящего из k элементов из списка S, содержащего n элементов, где n — это либо очень большое, либо неизвестное число. Обычно, n достаточно велико, чтобы весь список не уместился в основной памяти.
Экстрактор случайности — функция, которая применяется к выходу из слабо случайного источника энтропии, вместе с коротким равномерно распределённым случайным начальным значением и генерирует случайный выход, который выглядит независимым от источника и равномерно распределён. Примерами слабо случайных источников могут быть радиоактивный распад или тепловой шум. Единственное ограничение на возможные источники состоит в том, что не должно быть никакого способа, которым они могут полностью контролироваться, рассчитываться или предсказываться, таким образом, чтобы могла быть установлена нижняя граница для их уровня энтропии. Для данного источника экстрактор случайности может даже считаться истинным генератором случайных чисел, тем не менее нет единственного экстрактора, который, как доказывали, производил бы действительно случайный выход из любого типа слабо случайного источника.
Детерминированный конечный автомат, известный также как детерминированный конечный распознаватель — это конечный автомат, принимающий или отклоняющий заданную строку символов путём прохождения через последовательность состояний, определённых строкой. Имеет единственную последовательность состояний во время работы. Мак-Каллок и Уолтер Питтс были одними из первых исследователей, предложивших концепцию, похожую на конечный автомат в 1943 году.
