Алгори́тм — совокупность точно заданных правил решения некоторого класса задач или набор инструкций, описывающих порядок действий исполнителя для решения определённой задачи. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться в произвольном порядке, параллельно, если это позволяют используемые исполнители.
Коне́чный автома́т (КА) в теории алгоритмов — математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. Является частным случаем абстрактного дискретного автомата, число возможных внутренних состояний которого конечно.
Абстра́ктный автома́т — математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. На вход этому устройству поступают символы одного алфавита, на выходе оно выдаёт символы другого алфавита.
Маши́на Тью́ринга (Шаблон:Сокр) — абстрактный исполнитель. Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Универсальной машиной Тью́ринга называют машину Тьюринга, которая может заменить собой любую машину Тьюринга. Получив на вход программу и входные данные, она вычисляет ответ, который вычислила бы по входным данным машина Тьюринга, чья программа была дана на вход.
Недетерминированная машина Тьюринга (НМТ) — машина Тьюринга, функция перехода которой представляет собой недетерминированный конечный автомат (НКА).
В теории алгоритмов классом P называют множество задач, для которых существуют «быстрые» алгоритмы решения. Класс P включён в более широкие классы сложности алгоритмов.
В теории алгоритмов классом сложности BPP называется класс предикатов, быстро вычислимых и дающих ответ с высокой вероятностью. Задачи, решаемые вероятностными методами и лежащие в BPP, возникают на практике очень часто.
В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления. Говоря более узко, классы сложности — это множества предикатов, использующих для вычисления примерно одинаковые количества ресурсов.
Теория автоматов — раздел дискретной математики, изучающий абстрактные автоматы — вычислительные машины, представленные в виде математических моделей — и задачи, которые они могут решать.
Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется объёмом памяти или места на носителе данных. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа?». Здесь под размером входа понимается длина описания данных задачи в битах, а под размером выхода — длина описания решения задачи.
В теории автоматов, автомат с магазинной памятью — это конечный автомат, который использует стек для хранения состояний.
Класс сложности PSPACE — набор всех проблем разрешимости в теории сложности вычислений, которые могут быть разрешены машиной Тьюринга с полиномиальным ограничением пространства.
Класс языков L — множество языков, разрешимых на детерминированной машине Тьюринга с использованием 
дополнительной памяти для входа длиной n.
Вероятностный алгоритм — алгоритм, предусматривающий обращение на определённых этапах своей работы к генератору случайных чисел с целью получения экономии во времени работы за счёт замены абсолютной достоверности результата достоверностью с некоторой вероятностью.
В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе. Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, то есть при стремлении размера входа к бесконечности. Например, если существует число 
, такое, что время работы алгоритма для всех входов длины 
не превосходит 
, то временную сложность данного алгоритма можно асимптотически оценить как 
.
Детерминированный алгоритм — алгоритмический процесс, который выдаёт уникальный и предопределённый результат для заданных входных данных.
Теория сложности вычислений — подраздел теоретической информатики, занимающейся исследованием сложности алгоритмов для решения задач на основе формально определённых моделей вычислительных устройств. Сложность алгоритмов измеряется необходимыми ресурсами, в основном это продолжительность вычислений или необходимый объём памяти. В отдельных случаях исследуются другие степени сложности, такие как размер микросхем, или количество процессоров, необходимая для работы параллельных алгоритмов.
Машина вероятности – математическая модель вычислительного устройства, в работе которого участвует некоторый случайный процесс. Различные варианты понятия «Машины вероятности» являются обобщениями понятий «автомата детерминированного», «Тьюринга машина», «автомата бесконечного». Рассматривались, например, такие понятия «машины вероятности», как: 1)Машина Тьюринга с входом, к которому присоединен бернуллиевский датчик, выдающий символ 1 и 0 с вероятностью p и 1 – p соответственно. 2) Машина вероятности, которая получается из машин Тьюринга, если для данного обозреваемого символа и внутреннего состояния задается не единственная комбинация символ, состояние, сдвиг», а таблица вероятностей осуществления машиной каждой такой комбинации. Бесконечный автомат со счетным множеством состояний, для каждой пары состояний которого указывается вероятность того, что автомат, находясь в 1-м состоянии, перейдет во 2-е. Различные понятия Машина вероятности выражают различные уровни и цели абстракции.
