Алгори́тм — совокупность точно заданных правил решения некоторого класса задач или набор инструкций, описывающих порядок действий исполнителя для решения определённой задачи. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться в произвольном порядке, параллельно, если это позволяют используемые исполнители.
Коне́чный автома́т (КА) в теории алгоритмов — математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. Является частным случаем абстрактного дискретного автомата, число возможных внутренних состояний которого конечно.
Маши́на Тью́ринга (Шаблон:Сокр) — абстрактный исполнитель. Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Недетерминированная машина Тьюринга (НМТ) — машина Тьюринга, функция перехода которой представляет собой недетерминированный конечный автомат (НКА).
В теории алгоритмов классом P называют множество задач, для которых существуют «быстрые» алгоритмы решения. Класс P включён в более широкие классы сложности алгоритмов.
В теории алгоритмов классом сложности BPP называется класс предикатов, быстро вычислимых и дающих ответ с высокой вероятностью. Задачи, решаемые вероятностными методами и лежащие в BPP, возникают на практике очень часто.
В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления. Говоря более узко, классы сложности — это множества предикатов, использующих для вычисления примерно одинаковые количества ресурсов.
Будем считать, что язык L принадлежит классу RP, если он допускается вероятностной машиной Тьюринга M, для которой выполнены следующие условия:
- Если w не принадлежит L, то вероятность того, что M допускает w, равна 0.
- Если w принадлежит L, то вероятность того, что M допускает w, не меньше ½.
- Существует полином p(n), для которого, если w имеет длину n, то вычисления M останавливаются после не более p(n) шагов.
В теории вычислительной сложности ZPP — это класс задач с ответом «Да» либо «Нет», для которых существует вероятностная машина Тьюринга, удовлетворяющая следующим свойствам:
- Она всегда правильно отвечает «Да» либо «Нет».
- Математическое ожидание времени работы данной машины Тьюринга полиномиально.
В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе. Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, то есть при стремлении размера входа к бесконечности. Например, если существует число 
, такое, что время работы алгоритма для всех входов длины 
не превосходит 
, то временную сложность данного алгоритма можно асимптотически оценить как 
.
В математике, приближенная схема полиномиального времени или polynomial-time approximation scheme (PTAS) обозначает класс приближенных полиномиальных по времени выполнения алгоритмов для решения, как правило, NP-трудных оптимизационных задач. Если P = NP, то введение этого понятия теряет смысл. Поэтому далее будем предполагать, что Р не совпадает с NР. И без ограничения общности определим понятие для задачи минимизации.
Аппроксимационный алгоритм — в исследовании операций алгоритм, использующийся для поиска приближённого решения оптимизационной задачи.
В теории вычислительной сложности сложность алгоритма в среднем — это количество неких вычислительных ресурсов, требуемое для работы алгоритма, усреднённое по всем возможным входным данным. Понятие часто противопоставляется сложности в худшем случае, где рассматривается максимальная сложность алгоритма по всем входным данным.
Дифференциальная приватность — совокупность методов, которые обеспечивают максимально точные запросы в статистическую базу данных при одновременной минимизации возможности идентификации отдельных записей в ней.
Машина вероятности – математическая модель вычислительного устройства, в работе которого участвует некоторый случайный процесс. Различные варианты понятия «Машины вероятности» являются обобщениями понятий «автомата детерминированного», «Тьюринга машина», «автомата бесконечного». Рассматривались, например, такие понятия «машины вероятности», как: 1)Машина Тьюринга с входом, к которому присоединен бернуллиевский датчик, выдающий символ 1 и 0 с вероятностью p и 1 – p соответственно. 2) Машина вероятности, которая получается из машин Тьюринга, если для данного обозреваемого символа и внутреннего состояния задается не единственная комбинация символ, состояние, сдвиг», а таблица вероятностей осуществления машиной каждой такой комбинации. Бесконечный автомат со счетным множеством состояний, для каждой пары состояний которого указывается вероятность того, что автомат, находясь в 1-м состоянии, перейдет во 2-е. Различные понятия Машина вероятности выражают различные уровни и цели абстракции.
Оккамово обучение в теории вычислительного обучения является моделью алгоритмического обучения, где целью обучения является получение сжатого представления имеющихся тренировочных данных. Метод тесно связан с почти корректным обучением, где учитель оценивает прогнозирующую способность тестового набора.
Вероятно приближённо корректное обучение — схема машинного обучения, использующая понятия асимптотической достоверности и вычислительной сложности. Предложена в 1984 году Лесли Вэлиантом.
Детерминированный конечный автомат, известный также как детерминированный конечный распознаватель — это конечный автомат, принимающий или отклоняющий заданную строку символов путём прохождения через последовательность состояний, определённых строкой. Имеет единственную последовательность состояний во время работы. Мак-Каллок и Уолтер Питтс были одними из первых исследователей, предложивших концепцию, похожую на конечный автомат в 1943 году.
Недетерминированный конечный автомат — это детерминированный конечный автомат, который не выполняет следующие условия:
- любой его переход единственным образом определяется по текущему состоянию и входному символу
- чтение входного символа требуется для каждого изменения состояния.
