Изоморфи́зм — соотношение между математическими объектами, выражающее общность их строения; используется в разных разделах математики и в каждом из них определяется в зависимости от структурных свойств изучаемых объектов. Обычно изоморфизм определяется для множеств, наделённых некоторой структурой, например, для групп, колец, линейных пространств; в этом случае он определяется как обратимое отображение (биекция) между двумя множествами со структурой, сохраняющее эту структуру, то есть показывающее, что объекты «одинаково устроены» в смысле этой структуры. Если между объектами существует изоморфизм, то они называются изоморфными. Изоморфизм всегда задаёт отношение эквивалентности на классе таких структур.
Коне́чный автома́т (КА) в теории алгоритмов — математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. Является частным случаем абстрактного дискретного автомата, число возможных внутренних состояний которого конечно.
Маши́на Тью́ринга (Шаблон:Сокр) — абстрактный исполнитель. Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:
- как и геометрия, обладает наглядностью;
- как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
- не имеет громоздкого математического аппарата ;
- имеет выраженный прикладной характер.
В теории графов теорема Кёнига , доказанная Денешем Кёнигом в 1931, утверждает эквивалентность задач нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольных графах. Независимо была открыта, в том же 1931, Йенё Эгервари в несколько более общем виде для случая взвешенных графов.
Недетерминированная машина Тьюринга (НМТ) — машина Тьюринга, функция перехода которой представляет собой недетерминированный конечный автомат (НКА).
Теория автоматов — раздел дискретной математики, изучающий абстрактные автоматы — вычислительные машины, представленные в виде математических моделей, и задачи, которые они могут решать.
В теории автоматов, автомат с магазинной памятью — это конечный автомат, который использует стек для хранения состояний.
Регуля́рный язык в теории формальных языков — множество слов, которое распознает некоторый конечный автомат. Класс регулярных множеств удобно изучать в целом, а полученные результаты оказываются применимы для достаточно широкого спектра формальных языков.
Алгоритм Флойда — Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом. При этом алгоритм впервые разработал и опубликовал Бернард Рой в 1959 году.
Модель Крипке — это один из вариантов недетерминированного конечного автомата, который был предложен Солом Крипке. Этот вид НКА применяется при проверке моделей для представления поведения системы.
В теории формальных языков теорема Майхилла — Нероуда определяет необходимое и достаточное условия регулярности языка.
В теории графов графом без клешней называется граф, который не содержит порождённых подграфов, изоморфных K1,3 (клешней).
В теоретической информатике, точнее, в теории формальных языков, высота итерации — это мера структурной сложности регулярных выражений — высота итерации регулярного выражения равна максимальной глубине вложенности звёздочек, присутствующих в регулярном выражении. Понятие высоты итерации первым ввёл и изучал Эгган (1963).
Параметрическая редукция — это техника для разработки эффективных алгоритмов, которые достигают своей эффективности путём препроцессорного шага, в котором вход алгоритма заменяется на меньший вход, называемый «ядром». Результат решения задачи на ядре должен быть либо тем же самым, что и при исходных данных, либо выход решения для ядра должен легко преобразовываться в желаемый выход исходной задачи.
Циклический ранг ориентированного графа — мера связности орграфа, предложенная Эгганом и Бучи. Это понятие интуитивно отражает, насколько близок орграф к направленному ациклическому графу, когда циклический ранг НАГ равен нулю, в то время как ориентированный орграф порядка n с петлями в каждой вершине имеет циклический ранг n. Циклический ранг ориентированного графа тесно связан с глубиной дерева неориентированного графа и высотой итерации регулярных языков. Циклический ранг нашёл применение также в вычислениях с разреженными матрицами и логике.
Су́ффиксный автома́т — структура данных, позволяющая хранить в сжатом виде и обрабатывать информацию, связанную с подстроками данной строки. Представляет собой детерминированный конечный автомат, принимающий все суффиксы слова и только их, и обладающий наименьшим возможным числом состояний среди всех таких автоматов. Менее формально, суффиксный автомат — это ориентированный ациклический граф с выделенной начальной вершиной и набором «финальных» вершин, дуги которого помечены символами, такой что у любой вершины символы на исходящих из неё дугах попарно различны и для любого суффикса слова существует путь из начальной вершины в некоторую финальную вершину, символы на котором при конкатенации образуют данный суффикс. Из всех графов, удовлетворяющих данному описанию, суффиксным автоматом называется тот, который обладает наименьшим возможным числом вершин.
Детерминированный конечный автомат, известный также как детерминированный конечный распознаватель — это конечный автомат, принимающий или отклоняющий заданную строку символов путём прохождения через последовательность состояний, определённых строкой. Имеет единственную последовательность состояний во время работы. Мак-Каллок и Уолтер Питтс были одними из первых исследователей, предложивших концепцию, похожую на конечный автомат в 1943 году.
Недетерминированный конечный автомат — это детерминированный конечный автомат, который не выполняет следующие условия:
- любой его переход единственным образом определяется по текущему состоянию и входному символу
- чтение входного символа требуется для каждого изменения состояния.