Язы́к программи́рования — формальный язык, предназначенный для записи компьютерных программ. Язык программирования определяет набор лексических, синтаксических и семантических правил, определяющих внешний вид программы и действия, которые выполнит исполнитель под её управлением.
Пролог — язык и система логического программирования, основанные на языке предикатов математической логики дизъюнктов Хорна, представляющей собой подмножество логики предикатов первого порядка.
Коне́чный автома́т (КА) в теории алгоритмов — математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. Является частным случаем абстрактного дискретного автомата, число возможных внутренних состояний которого конечно.
NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «типовых» задач в классе NP: если для какой-то из них будет найден «полиномиально быстрый» алгоритм решения, то и любую другую задачу из класса NP можно будет решить так же «быстро».
В теории алгоритмов классом NP называют множество задач разрешимости, решение которых возможно проверить на машине Тьюринга за время, не превосходящее значения некоторого многочлена от размера входных данных, при наличии некоторых дополнительных сведений.
Switch-технология — технология разработки систем логического управления на базе конечных автоматов, охватывающая процесс спецификации, проектирования, реализации, отладки, верификации, документирования и сопровождения. Предложена А. А. Шалыто в 1991 году.
Язык спецификаций — формальный язык, предназначенный для декларативного описания структуры, связей, свойств данных и способов их преобразований, без явного упоминания порядка выполняемых действий и использования конкретных значений данных.
Зада́ча выполни́мости бу́левых фо́рмул — важная для теории вычислительной сложности алгоритмическая задача.
Data mining — собирательное название, используемое для обозначения совокупности методов обнаружения в данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности. Термин введён Григорием Пятецким-Шапиро в 1989 году.
Дескрипцио́нная логика — язык представления знаний, позволяющий описывать понятия предметной области в недвусмысленном, формализованном виде, организованный по типу языков математической логики. Дескрипционные логики сочетают, с одной стороны, богатые выразительные возможности, а с другой — хорошие вычислительные свойства, такие как разрешимость и относительно невысокая вычислительная сложность основных логических проблем, что делает возможным их применение на практике, обеспечивая компромисс между выразительностью и разрешимостью. Могут быть рассмотрены как разрешимые фрагменты логики предикатов, синтаксически же они близки к модальным логикам.
Хорновский дизъюнкт — дизъюнктивный одночлен с не более чем одним положительным литералом. Изучены Альфредом Хорном в 1951 году в связи с их важной ролью в теории моделей и универсальной алгебре. Впоследствии стали основой для языка логического программирования Пролог, в котором программа являются непосредственно набором хорновских дизъюнктов, а также нашли важные приложения в конструктивной логике и теории сложности вычислений.
Обуче́ние ранжи́рованию — это класс задач машинного обучения с учителем, заключающихся в автоматическом подборе ранжирующей модели по обучающей выборке, состоящей из множества списков и заданных частичных порядков на элементах внутри каждого списка. Частичный порядок обычно задаётся путём указания оценки для каждого элемента. Цель ранжирующей модели — наилучшим образом приблизить и обобщить способ ранжирования в обучающей выборке на новые данные.
DPLL — полный алгоритм поиска с возвратом для решения задачи CNF-SAT — определения выполнимости булевых формул, записанных в конъюнктивной нормальной форме.
Аппроксимационный алгоритм — в исследовании операций алгоритм, использующийся для поиска приближённого решения оптимизационной задачи.
Формальная верификация криптографических протоколов — проверка криптографических протоколов на обеспечение требуемых свойств безопасности. Одной из составляющих такой проверки является определение стойкости протокола к атакам в предположении о надёжности криптографических примитивов, на которых он основывается. Для решения этой задачи разработан ряд подходов, основанных на различных формальных методах верификации. Общей чертой формальных методов является использование системного подхода к проблеме, позволяющего выполнять более обоснованную, точную и эффективную проверку свойств безопасности протокола.
Алгоритм CDCL — основанный на алгоритме DPLL эффективный решатель (NP-полных) задач выполнимости булевых формул (SAT-решатель). Основная структура данных в CDCL-решателях — импликационный граф, фиксирующий назначения переменным, а другой особенностью является использование нехронологического возврата и запоминание дизъюнктов в ходе анализа конфликта.
Индукция грамматики — процедура машинного обучения, которая восстанавливает формальную грамматику языка на основе набора наблюдений (примеров) с известной принадлежностью этому языку. В результате процедуры строится модель наблюдаемых объектов в виде набора правил вывода или порождающих правил, конечного автомата или автомата другого вида. В более общем смысле, грамматический вывод — это одно из направлений машинного обучения, в котором пространство примеров состоит из дискретных комбинаторных объектов, таких как строки, деревья, графы.
Квантовая теория сложности — часть теории сложности вычислений в теоретической информатике. Изучает классы сложности, определённые с использованием квантовых компьютеров и квантовой информации, а также проблемы, связанные с этими классами сложности, и связи между классами квантовой сложности и классическими (неквантовыми) классами сложности.
Алгори́тм Шёнинга — вероятностный алгоритм для решения задачи выполнимости булевых формул в k-конъюнктивной нормальной форме, предложенный Уве Шёнингом в 1999 году.