Понятия со словом «решатель»
Универсальный решатель задач (англ. General Problem Solver, GPS) — компьютерная программа, созданная в 1959 году Гербертом Саймоном, Клиффордом Шоу (англ. Cliff Show) и Алленом Ньюэллом, предназначенная для работы в качестве универсальной машины для решения задач, сформулированных на языке хорновских дизъюнктов. В качестве примеров использования приводились доказательства теорем евклидовой геометрии и логики предикатов, решение шахматных задач.
Геометрический решатель (англ. Geometric Constraint Solver), решатель геометрических ограничений, геометрический решатель задач в ограничениях — это программная компонента, которая встраивается в САПР и позволяет инженеру точно позиционировать геометрические элементы друг относительно друга.
Связанные понятия
Комбинаторная оптимизация — область теории оптимизации в прикладной математике, связанная с исследованием операций, теорией алгоритмов и теорией вычислительной сложности.
Стохастическая оптимизация — класс алгоритмов оптимизации, использующая случайность в процессе поиска оптимума. Случайность может проявляться в разных вещах.
Комбинаторное
программирование (также программирование, свободное от указателей и Бесточечное программирование) — парадигма программирования, в которой при объявлении функций не используются промежуточные переменные, но составляются цепочки из функций.
Задача выполнимости формул в теориях (англ. satisfiability modulo theories, SMT) — это задача разрешимости для логических формул с учётом лежащих в их основе теорий. Примерами таких теорий для SMT-формул являются: теории целых и вещественных чисел, теории списков, массивов, битовых векторов и т. п.
Алгоритмика — раздел информатики, дисциплина, изучающая алгоритмы и их применение к решению задач.
Вычислительная топология или алгоритмическая топология — дисциплина, находящаяся на пересечении топологии, вычислительной геометрии и теории вычислительной сложности. Её основными задачами являются создание эффективных алгоритмов для решения топологических проблем и применение топологических методов для решения алгоритмических проблем, возникающих в других областях науки.
Последовательное квадратичное программирование (англ. Sequential quadratic programming (SQP)) — один из наиболее распространённых и эффективных оптимизационных алгоритмов общего назначения, основной идеей которого является последовательное решение задач квадратичного программирования, аппроксимирующих данную задачу оптимизации. Для оптимизационных задач без ограничений алгоритм SQP преобразуется в метод Ньютона поиска точки, в которой градиент целевой функции обращается в ноль. Для решения исходной...
Вычисления с оракулом — вычисление с помощью машины Тьюринга, дополненной оракулом с неизвестным внутренним устройством.
В теории вычислимости
алгоритмически неразрешимой задачей называется задача, имеющая ответ да или нет для каждого объекта из некоторого множества входных данных, для которой (принципиально) не существует алгоритма, который бы, получив любой возможный в качестве входных данных объект, останавливался и давал правильный ответ после конечного числа шагов.
Символьные вычисления — это преобразования и работа с математическими равенствами и формулами как с последовательностью символов. Они отличаются от численных расчётов, которые оперируют приближёнными численными значениями, стоящими за математическими выражениями. Системы символьных вычислений (их так же называют системами компьютерной алгебры) могут быть использованы для символьного интегрирования и дифференцирования, подстановки одних выражений в другие, упрощения формул и т. д.
Метод секущих плоскостей позволяет находить решение задачи целочисленного программирования как задачи линейного программирования путём добавления дополнительных ограничений. Главная идея метода — добавление ограничений, которые нарушаются для оптимума задачи линейного программирования, но остаются верными для оптимума исходной задачи.
Скалярный процессор — это простейший класс микропроцессоров. Скалярный процессор обрабатывает один элемент данных за одну инструкцию (SISD, Single Instruction Single Data), типичными элементами данных могут быть целые или числа с плавающей запятой. В векторных процессорах (SIMD, Single Instruction Multiple Data), в отличие от скалярных, одна инструкция работает с несколькими элементами данных.
Иные значения см. разделе в Компьютерное моделирование.Теория вычислимости и теория сложности вычислений трактует модель вычисления (англ. model of computation) не только как определение множества допустимых операций, использованных для вычисления, но также и относительных издержек их применения. Охарактеризовать необходимые вычислительные ресурсы — время выполнения, объём памяти, а также ограничения алгоритмов или компьютера — можно только в том случае, если выбрана определённая модель вычислений...
Подробнее: Модель вычислений
Инве́рсия абстра́кции (англ. abstraction inversion) — ошибка проектирования программного модуля, когда в сложном модуле для пользователя закрыты некоторые простые, но необходимые функции. В результате пользователь модуля вынужден реализовывать простую функциональность на основе интерфейса модуля, иногда с использованием недокументированных возможностей и побочных эффектов, в то время когда она уже реализована внутри модуля. То есть, реализовывать более низкоуровневые функции на основе высокоуровневых...
Языки квантового программирования — языки программирования, позволяющие выражать квантовые алгоритмы с использованием высокоуровневых конструкций. Их цель не столько создание инструмента для программистов, сколько предоставление средств для исследователей для облегчения понимания работы квантовых вычислений.
Подробнее: Квантовое программирование
В вычислительной математике, безматричный метод это алгоритм для решения СЛАУ или решения задачи нахождения собственных значений, который не использует отдельное хранение матрицы коэффициентов, но обращается к матрице через произведения матриц-векторов. Безматричные методы предпочтительнее, когда матрица слишком большая для хранения и работа с ней требует больших объемов памяти и вычислительного времени, даже если матрица разреженная.
Подробнее: Безматричные методы
Целевая функция — вещественная или целочисленная функция нескольких переменных, подлежащая оптимизации (минимизации или максимизации) в целях решения некоторой оптимизационной задачи. Термин используется в математическом программировании, исследовании операций, линейном программировании, теории статистических решений и других областях математики в первую очередь прикладного характера, хотя целью оптимизации может быть и решение собственно математической задачи. Помимо целевой функции в задаче оптимизации...
Квантовый алгоритм — это алгоритм, предназначенный для выполнения на квантовом компьютере.
Полнота по Тьюрингу — характеристика исполнителя (множества вычисляющих элементов) в теории вычислимости, означающая возможность реализовать на нём любую вычислимую функцию. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, машина Тьюринга) или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями (возможно, при некотором кодировании входных и выходных данных).
Быстрые алгоритмы — это область вычислительной математики, которая изучает алгоритмы вычисления заданной функции с заданной точностью с использованием как можно меньшего числа битовых операций.
Рациональный тип данных — способ представления рациональных чисел используемый в программировании. Рациональные числа в ЭВМ представляются таким образом, чтобы отдельно хранить числитель числа, а отдельно знаменателя числа, что позволяет избежать проблему округления чисел при выполнении математических операций, как это бывает при использовании переменных хранимых в форме с плавающей запятой или фиксированной запятой. Математические операции над рациональными числами моделируются программно. В некоторых...
Алгоритм Риша — алгоритм для аналитического вычисления неопределённых интегралов, использующий методы дифференциальной алгебры. Он базируется на типе интегрируемой функции и на методах интегрирования рациональных функций, корней, логарифмов, и экспоненциальных функций.
Алгоритм Блюма — Микали (англ. Blum-Micali algorithm) — это криптографически стойкий алогоритм генерации псевдослучайных последовательностей, с использованием зерна (Random seed). Идеи алгоритма были изложены Блюмом и Микали в 1984 году. Алгоритм был разработан на основе алгоритма генератора Шамира, предложенного Ади Шамиром годом ранее. Алгоритм отличается от предшественника более сильными требованиями к сложности вычисления выходной последовательности. В отличие от генератора Шамира выходом данного...
Линейно-квадратичный регулятор (англ. Linear quadratic regulator, LQR) — в теории управления один из видов оптимальных регуляторов, использующий квадратичный функционал качества. Задача, в которой динамическая система описывается линейными дифференциальными уравнениями, а показатель качества представляет собой квадратичный функционал, называется задачей линейно-квадратичного управления. Широкое распространение получили линейно-квадратичные регуляторы (LQR) и линейно-квадратичные гауссовы регуляторы...
Вычисле́ние — математическое преобразование, позволяющее преобразовывать входящий поток информации в выходной, с отличной от первого структурой. Если смотреть с точки зрения теории информации, вычисление — это получение из входных данных нового знания.
Абстра́ктный тип да́нных (АТД) — это математическая модель для типов данных, где тип данных определяется поведением (семантикой) с точки зрения пользователя данных, а именно в терминах возможных значений, возможных операций над данными этого типа и поведения этих операций.
Факторизация целых чисел для больших чисел является задачей большой сложности. Не существует никакого известного способа, чтобы решить эту задачу быстро. Её сложность лежит в основе некоторых алгоритмов шифрования с открытым ключом, таких как RSA.
Псевдослучайный алгоритм шифрования — такой алгоритм шифрования, что каждый блок (символ) исходного текста шифруется своим собственным ключом, причём каждый следующий ключ является следующим членом псевдослучайной последовательности, а основной (базовый) ключ — первым элементом этой последовательности.
Криптосистема Нидеррайтера — криптосистема с открытыми ключами, основанная на теории алгебраического кодирования, разработанная в 1986 году Харальдом Нидеррайтером. В отличие от криптосистемы McEliece, в криптосистеме Нидеррайтера используется проверочная матрица кода. Криптосистема Нидеррайтера позволяет создавать цифровые подписи и является кандидатом для постквантовой криптографии, поскольку устойчива к атаке с использованием алгоритма Шора.
Процеду́рное программи́рование — программирование на императивном языке, при котором последовательно выполняемые операторы можно собрать в подпрограммы, то есть более крупные целостные единицы кода, с помощью механизмов самого языка.
Квантова́ние — процедура построения чего-либо с помощью дискретного набора величин, например, целых чисел, в отличие от построения с помощью непрерывного набора величин, например, вещественных чисел.
Булевы операции над многоугольниками — это набор булевых операций (AND, OR, NOT, XOR, ...) с одним или несколькими наборами многоугольников в компьютерной графике. Эти наборы операций широко используются в компьютерной графике, САПР и в проектировании электронных схем (физическое расположение элементов интегральных схем и программы проверки).
Детерминированный алгоритм — алгоритмический процесс, который выдаёт уникальный и предопределённый результат для заданных входных данных.
Ленивые вычисления (англ. lazy evaluation, также отложенные вычисления) — применяемая в некоторых языках программирования стратегия вычисления, согласно которой вычисления следует откладывать до тех пор, пока не понадобится их результат. Ленивые вычисления относятся к нестрогим вычислениям. Усовершенствованная модель ленивых вычислений — оптимистичные вычисления — переходит в разряд недетерминированных стратегий вычисления.
Метод рекурсивного спуска (англ. Recursive descent parser) — алгоритм нисходящего синтаксического анализа, реализуемый путём взаимного вызова процедур, где каждая процедура соответствует одному из правил контекстно-свободной грамматики или БНФ. Применения правил последовательно, слева-направо поглощают токены, полученные от лексического анализатора. Это один из самых простых алгоритмов синтаксического анализа, подходящий для полностью ручной реализации.
Односторонняя функция — математическая функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Здесь «легко» и «трудно» должны пониматься с точки зрения теории сложности вычислений. Разрыв между сложностью прямого и обратного преобразований определяет криптографическую эффективность односторонней функции. Неинъективность функции не является достаточным условием для того, чтобы называть её односторонней. Односторонние функции могут называться...
Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.
Термин
рекурсивная функция в теории вычислимости используется для обозначения трёх классов функций...
Коне́чный автома́т с па́мятью — математическая модель устройства, поведение которого зависит как от входных условий, так и от предыдущего состояния.
Коиндукция в информатике — метод для определения и доказательства свойств систем параллельно взаимодействующих объектов (обобщённо). С математической точки зрения является дуальной к структурной индукции.
Квадрати́чная зада́ча о назначе́ниях (КЗН, англ. Quadratic assignment problem, QAP) — одна из фундаментальных задач комбинаторной оптимизации в области оптимизации или исследования операций, принадлежащая категории задач размещения объектов.
Предобуславливание (также предобусловливание) — процесс преобразования условий задачи для её более корректного численного решения. Предобуславливание обычно связано с уменьшением числа обусловленности задачи. Предобуславливаемая задача обычно затем решается итерационным методом.