Связанные понятия
Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется...
В теории чисел гладким числом называется целое число, все простые делители которого малы.
Подробнее: Гладкое число
Вероятностный алгоритм — алгоритм, предусматривающий обращение на определённых этапах своей работы к генератору случайных чисел с целью получения экономии во времени работы за счёт замены абсолютной достоверности результата достоверностью с некоторой вероятностью.
Целые
числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме ±1.
Система линейных алгебраических уравнений (линейная система, также употребляются аббревиатуры СЛАУ, СЛУ) — система уравнений, каждое уравнение в которой является линейным — алгебраическим уравнением первой степени.
Система уравнений — это условие, состоящее в одновременном выполнении нескольких уравнений относительно нескольких (или одной) переменных.
Псевдопростое число — натуральное число, обладающее некоторыми свойствами простых чисел, являясь тем не менее составным. В зависимости от рассматриваемых свойств существует несколько различных типов псевдопростых чисел.
Вероятностный метод — неконструктивный метод доказательства существования математического объекта с заданными свойствами. В основном используется в комбинаторике, но также и в теории чисел, линейной алгебре и математическом анализе, а также в информатике (например, метод вероятностного округления) и теории информации.
Алгоритм Гельфонда — Шенкса (англ. Baby-step giant-step; также называемый алгоритмом больших и малых шагов) — в теории групп детерминированный алгоритм дискретного логарифмирования в мульпликативной группе кольца вычетов по модулю простого числа. Был предложен советским математиком Александром Гельфондом в 1962 году и Дэниэлем Шенксом в 1972 году.
Детерминированный алгоритм — алгоритмический процесс, который выдаёт уникальный и предопределённый результат для заданных входных данных.
Умноже́ние ма́триц — одна из основных операций над матрицами. Матрица, получаемая в результате операции умножения, называется произведе́нием ма́триц.
Инволюция (от лат. involutio — свёртывание, завиток) — преобразование, которое является обратным самому себе.
Составно́е число ́ (в XIX веке также сложное число) — натуральное число, бо́льшее 1, не являющееся простым. Каждое составное число является произведением двух или более натуральных чисел, бо́льших 1.
Односторонняя функция — математическая функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Здесь «легко» и «трудно» должны пониматься с точки зрения теории сложности вычислений. Разрыв между сложностью прямого и обратного преобразований определяет криптографическую эффективность односторонней функции. Неинъективность функции не является достаточным условием для того, чтобы называть её односторонней. Односторонние функции могут называться...
Схема шифрования GGH (англ. Goldreich–Goldwasser–Halevi) — асимметричная криптографическая система, основанная на решётках. Также существует схема подписи GGH.
Мультимножество в математике — обобщение понятия множества, допускающее включение одного и того же элемента по нескольку раз. Число элементов в мультимножестве, с учётом повторяющихся элементов, называется его размером или мощностью.
Кольцо многочленов — кольцо, образованное многочленами от одной или нескольких переменных с коэффициентами из другого кольца. Изучение свойств колец многочленов оказало большое влияние на многие области современной математики; можно привести примеры теоремы Гильберта о базисе, конструкции поля разложения и изучения свойств линейных операторов.
Дели́мость — одно из основных понятий арифметики и теории чисел, связанное с операцией деления. С точки зрения теории множеств, делимость целых чисел является отношением, определённым на множестве целых чисел.
Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.
Математическая индукция — метод математического доказательства, который используется, чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 — база (базис) индукции, а затем доказывается, что если верно утверждение с номером n, то верно и следующее утверждение с номером n + 1 — шаг индукции, или индукционный переход.
В теории вероятностей случайная величина имеет дискретное равномерное распределение, если она принимает конечное число значений с равными вероятностями.
Подробнее: Дискретное равномерное распределение
Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.
Квантовый алгоритм — это алгоритм, предназначенный для выполнения на квантовом компьютере.
Вычисления с оракулом — вычисление с помощью машины Тьюринга, дополненной оракулом с неизвестным внутренним устройством.
Обучение с ошибками (англ. Learning with errors) — это концепция машинного обучения, суть которой заключается в том, что в простые вычислительные задачи (например, системы линейных уравнений) намеренно вносится ошибка, делая их решение известными методами неосуществимым за приемлемое время.
Бу́лева фу́нкция (или логи́ческая функция, или функция а́лгебры ло́гики) от n аргументов — в дискретной математике — отображение Bn → B, где B = {0,1} — булево множество. Элементы булева множества {1, 0} обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определённого смысла. Неотрицательное целое число n называют арностью или местностью функции, в случае n = 0 булева функция превращается в булеву константу...
Криптосистема Уильямса (Williams System) — система шифрования с открытым ключом, созданная Хью Коуи Уильямсом (Hugh Cowie Williams) в 1984 году.
Скорость сходимости является основной характеристикой численных методов решения уравнений и оптимизации.
«Тогда́ и то́лько тогда ́» — логическая связка эквиваленции между утверждениями, применяемая в логике, математике, философии. Чтобы быть эквиваленцией, связка должна быть идентична стандартному материальному условному высказыванию («только тогда» эквивалентно «если … то»), соединённому со своей противоположностью, откуда и название связки. В результате истинность одного утверждения требует такой же истинности другого, то есть либо оба они истинны, либо оба ложны. Можно спорить о том, передаёт ли выражение...
Обучение с ошибками в кольце (англ. Ring learning with errors, RLWE)— это вычислительная задача, которая была сформулирована как вариант более общей задачи обучения с ошибками (с англ. LWE), с целью использовать преимущество дополнительной алгебраической структуры (т.е. кольца многочленов) из теории решеток, что дало возможность повысить и расширить возможности шифрования тех криптографических приложений, которые ранее основывались на LWE. Задача RLWE стала основой новых криптографических алгоритмов...
Элементарные функции — функции, которые можно получить с помощью конечного числа арифметических действий и композиций из следующих основных элементарных функций...
В линейной алгебре линейная зависимость — это свойство, которое может иметь подмножество линейного пространства. При линейной зависимости существует нетривиальная линейная комбинация элементов этого множества, равная нулевому элементу. При отсутствии такой комбинации, то есть, когда коэффициенты единственной такой линейной комбинации равны нулю, множество называется линейно независимым.
Криптосистема — это завершённая комплексная модель, способная производить двусторонние криптопреобразования над данными произвольного объёма и подтверждать время отправки сообщения, обладающая механизмом преобразования паролей, ключей и системой транспортного кодирования.
Метод итерации — численный метод решения математических задач, приближённый метод решения системы линейных алгебраических уравнений. Суть такого метода заключается в нахождении по приближённому значению величины следующего приближения (являющегося более точным).
Не путать с «симплекс-методом» — методом оптимизации произвольной функции. См. Метод Нелдера — МидаСимплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.
Подробнее: Симплекс-метод
Метод Ньютона , алгоритм Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Модификацией метода является метод хорд и касательных. Также метод Ньютона может быть использован...
Разбие́ние мно́жества — это представление его в виде объединения произвольного количества попарно непересекающихся подмножеств.
Разделяй и властвуй (англ. divide and conquer) в информатике — важная парадигма разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче; разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.
Эллиптическая криптография — раздел криптографии, который изучает асимметричные криптосистемы, основанные на эллиптических кривых над конечными полями. Основное преимущество эллиптической криптографии заключается в том, что на сегодняшний день не известно существование субэкспоненциальных алгоритмов решения задачи дискретного логарифмирования.
В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления. Говоря более узко, классы сложности — это множества предикатов (функций, получающих на вход слово и возвращающих ответ 0 или 1), использующих для вычисления примерно одинаковые количества ресурсов.
Подробнее: Класс сложности
Дискретное преобразование Фурье (в англоязычной литературе DFT, Discrete Fourier Transform) — это одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов (его модификации применяются в сжатии звука в MP3, сжатии изображений в JPEG и др.), а также в других областях, связанных с анализом частот в дискретном (к примеру, оцифрованном аналоговом) сигнале. Дискретное преобразование Фурье требует в качестве входа дискретную функцию. Такие функции часто создаются путём дискретизации...
Евклидово кольцо — общеалгебраическое кольцо, в котором существует аналог алгоритма Евклида.
В информатике временна́я сложность алгоритма определяет время работы, используемое алгоритмом, как функции от длины строки, представляющей входные данные . Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая исключает коэффициенты и члены меньшего порядка. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, т.е. при стремлении размера входа к бесконечности. Например, если время, которое нужно алгоритму для выполнения...
Подробнее: Временная сложность алгоритма
Алгори́тм (лат. algorithmi — от арабского имени математика Аль-Хорезми) — конечная совокупность точно заданных правил решения произвольного класса задач или набор инструкций, описывающих порядок действий исполнителя для решения некоторой задачи. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться...
Целочисленное программирование является NP-трудной задачей. Специальный случай, 0-1 целочисленное линейное программирование, в которой переменные принимают значения 0 или 1, является одной из 21 NP-полных задач Карпа.
Конъюнкти́вная норма́льная фо́рма (КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов. Конъюнктивная нормальная форма удобна для автоматического доказательства теорем. Любая булева формула может быть приведена к КНФ. Для этого можно использовать: закон двойного отрицания, закон де Моргана, дистрибутивность.
Ранцевая криптосистема Меркла-Хеллмана, основанная на «задаче о рюкзаке», была разработана Ральфом Мерклем и Мартином Хеллманом в 1978 году. Это была одна из первых криптосистем с открытым ключом, но она оказалась криптографически нестойкой и, как следствие, не приобрела популярности.
Основная теорема о рекуррентных соотношениях (англ. Master theorem) используется в анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй и властвуй» (divide and conquer), например, при оценке времени их выполнения. Теорема была популяризована в книге Алгоритмы: построение и анализ (Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн), в которой она была введена и доказана.