Связанные понятия
Эллиптическая криптография — раздел криптографии, который изучает асимметричные криптосистемы, основанные на эллиптических кривых над конечными полями. Основное преимущество эллиптической криптографии заключается в том, что на сегодняшний день не известно существование субэкспоненциальных алгоритмов решения задачи дискретного логарифмирования.
Алгоритм Гельфонда — Шенкса (англ. Baby-step giant-step; также называемый алгоритмом больших и малых шагов) — в теории групп детерминированный алгоритм дискретного логарифмирования в мульпликативной группе кольца вычетов по модулю простого числа. Был предложен советским математиком Александром Гельфондом в 1962 году и Дэниэлем Шенксом в 1972 году.
Обучение с ошибками в кольце (англ. Ring learning with errors, RLWE)— это вычислительная задача, которая была сформулирована как вариант более общей задачи обучения с ошибками (с англ. LWE), с целью использовать преимущество дополнительной алгебраической структуры (т.е. кольца многочленов) из теории решеток, что дало возможность повысить и расширить возможности шифрования тех криптографических приложений, которые ранее основывались на LWE. Задача RLWE стала основой новых криптографических алгоритмов...
Криптосистема Уильямса (Williams System) — система шифрования с открытым ключом, созданная Хью Коуи Уильямсом (Hugh Cowie Williams) в 1984 году.
В информатике временна́я сложность алгоритма определяет время работы, используемое алгоритмом, как функции от длины строки, представляющей входные данные . Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая исключает коэффициенты и члены меньшего порядка. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, т.е. при стремлении размера входа к бесконечности. Например, если время, которое нужно алгоритму для выполнения...
Подробнее: Временная сложность алгоритма
Ме́тоды Ру́нге — Ку́тты (в литературе встречаются названия: ме́тоды Ру́нге — Ку́тта или же ме́тоды Ру́нге — Кутта́) — большой класс численных методов решения задачи Коши для обыкновенных дифференциальных уравнений и их систем. Первые методы данного класса были предложены около 1900 года немецкими математиками К. Рунге и М. В. Куттой.
Универса́льное хеши́рование (англ. Universal hashing) — это вид хеширования, при котором используется не одна конкретная хеш-функция, а происходит выбор из заданного семейства по случайному алгоритму. Такой подход обеспечивает равномерное хеширование: для очередного ключа вероятности помещения его в любую ячейку совпадают. Известно несколько семейств универсальных хеш-функций, которые имеют многочисленные применения в информатике, в частности в хеш-таблицах, вероятностных алгоритмах и криптографии...
Обучение с ошибками (англ. Learning with errors) — это концепция машинного обучения, суть которой заключается в том, что в простые вычислительные задачи (например, системы линейных уравнений) намеренно вносится ошибка, делая их решение известными методами неосуществимым за приемлемое время.
В теории вычислительной сложности сложность алгоритма в среднем — это количество неких вычислительных ресурсов (обычно — время), требуемое для работы алгоритма, усреднённое по всем возможным входным данным. Понятие часто противопоставляется сложности в худшем случае, где рассматривается максимальная сложность алгоритма по всем входным данным.
Принцип минимальной длины описания (англ. minimum description length, MDL) — это формализация бритвы Оккама, в которой лучшая гипотеза (модель и её параметры) для данного набора данных это та, которая ведёт к лучшему сжиманию даных. Принцип MDL предложил Йорма Риссанен в 1978. Принцип является важной концепцией в теории информации и теории вычислительного обучения.
Поточный алгоритм (англ. streaming algorithm) — алгоритм для обработки последовательности данных в один или малое число проходов.
Вероятностное округление — это широко используемый подход для разработки и анализа таких аппроксимационных алгоритмов. Базовая идея — использование вероятностного метода для преобразования соответствующей оптимального решения задачи линейного программирования (ЛП) в приближённое к оптимальному решению исходной задачи.
Целочисленное программирование является NP-трудной задачей. Специальный случай, 0-1 целочисленное линейное программирование, в которой переменные принимают значения 0 или 1, является одной из 21 NP-полных задач Карпа.
Рациональное решето — это алгоритм общего вида для разложения целых чисел на простые множители. Алгоритм является частным случаем общего метода решета числового поля. Хотя он менее эффективен, чем общий алгоритм, концептуально он проще. Алгоритм может помочь понять, как работает общий метод решета числового поля.
Матема́тика ку́бика Ру́бика — совокупность математических методов для изучения свойств кубика Рубика с абстрактно-математической точки зрения. Эта математика изучает алгоритмы сборки кубика и оценивает их. Основана на теории графов, теории групп, теории вычислимости и комбинаторике.
Тасование Фишера — Йетса (названо в честь Рональда Фишера и Франка Йетса (Frank Yates)), известное также под именем Тасование Кнута (в честь Дональда Кнута), — это алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества. Вариант тасования Фишера-Йетса, известный как алгоритм Саттоло (Sattolo), может быть использован для генерации случайного цикла перестановок длины n. Правильно реализованный алгоритм тасования Фишера-Йетса несмещённый, так...
Алгори́тм (лат. algorithmi — от арабского имени математика Аль-Хорезми) — конечная совокупность точно заданных правил решения произвольного класса задач или набор инструкций, описывающих порядок действий исполнителя для решения некоторой задачи. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться...
Обучение дерева решений использует дерево решений (как предиктивную модель), чтобы перейти от наблюдений над объектами (представленными в ветвях) к заключениям о целевых значениях объектов (представленных в листьях). Это обучение является одним из подходов моделирования предсказаний, используемых в статистике, интеллектуальном анализе данных и обучении машин. Модели деревьев, в которых целевая переменная может принимать дискретный набор значений, называются деревьями классификации. В этих структурах...
Задача разбиения множества чисел — это задача определения, можно ли данное мультимножество S положительных целых чисел разбить на два подмножества S1 и S2, таких, что сумма чисел из S1 равна сумме чисел из S2. Хотя задача разбиения чисел является NP-полной, существует решение псевдополиномиального времени методом динамического программирования существуют эвристические алгоритмы решения для многих конкрентных задач либо оптимально, либо приближённо. По этой причине задачу называют "простейшей NP-трудной...
Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется...
В комбинаторной оптимизации под линейной задачей о назначениях на узкие места (linear bottleneck assignment problem, LBAP) понимается задача, похожая на задачу о назначениях.
Подробнее: Линейная задача о назначениях в узких местах
Двенадцатикратный путь или двенадцать сценариев — это систематическая классификация 12 связанных перечислительных задач, касающихся двух конечных множеств, которые включают классические задачи подсчёта перестановок, сочетаний, мультимножеств и разбиений либо множества, либо числа. Идею классификации приписывают Джиану-Карло Роту, а название двенадцатикратный путь предложил Джоэл Спенсер. Название намекает, что используя те же подходы в 12 случаях, но с небольшими изменениями в условиях, мы получаем...
Задача коммивояжёра (англ. Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что...
Алгоритм исчисления порядка (index-calculus algorithm) — вероятностный алгоритм вычисления дискретного логарифма в кольце вычетов по модулю простого числа. На сложности нахождения дискретного логарифма основано множество алгоритмов связанных с криптографией. Так как для решения данной задачи с использованием больших чисел требуется большое количество ресурсов, предоставить которые не может ни один современный компьютер. Примером такого алгоритма является ГОСТ Р 34.10-2012.
Разделение секрета (англ. Secret sharing) — термин в криптографии, под которым понимают любой из способов распределения секрета среди группы участников, каждому из которых достаётся своя некая доля. Секрет может воссоздать только коалиция участников из первоначальной группы, причём входить в коалицию должно не менее некоторого изначально известного их числа.
Неотрицательное матричное разложение (НМР), а также неотрицательное приближение матрицы, это группа алгоритмов в мультивариантном анализе и линейной алгебре, в которых матрица V разлагается на (обычно) две матрицы W и H, со свойством, что все три матрицы имеют неотрицательные элементы. Эта неотрицательность делает получившиеся матрицы более простыми для исследования. В приложениях, таких как обработка спектрограмм аудиосигнала или данных мускульной активности, неотрицательность свойственна рассматриваемым...
Задача о рюкзаке (или Задача о ранце) в криптографии (англ. Knapsack problem) — это задача, на основе которой американские криптографы Ральф Меркл и Мартин Хеллман разработали первый алгоритм шифрования с открытым ключом. Он носит название криптосистема Меркла-Хеллмана. Для шифрования сообщений использовалось решение задачи о рюкзаке, как известно, являющейся NP-сложной. Потому, как считалось, она могла обеспечивать криптостойкость системы. На данный момент создано множество рюкзачных криптосистем...
Длинная арифметика — выполняемые с помощью вычислительной машины арифметические операции (сложение, вычитание, умножение, деление, возведение в степень, элементарные функции) над числами, разрядность которых превышает длину машинного слова данной вычислительной машины. Эти операции реализуются не аппаратно, а программно, с использованием базовых аппаратных средств работы с числами меньших порядков. Частный случай — арифметика произвольной точности — относится к арифметике, в которой длина чисел ограничена...
Байесовское программирование — это формальная система и методология определения вероятностных моделей и решения задач, когда не вся необходимая информация является доступной.
Предобуславливание (также предобусловливание) — процесс преобразования условий задачи для её более корректного численного решения. Предобуславливание обычно связано с уменьшением числа обусловленности задачи. Предобуславливаемая задача обычно затем решается итерационным методом.
Метод обратного распространения ошибки (англ. backpropagation) — метод вычисления градиента, который используется при обновлении весов многослойного перцептрона. Впервые метод был описан в 1974 г. А. И. Галушкиным, а также независимо и одновременно Полом Дж. Вербосом. Далее существенно развит в 1986 г. Дэвидом И. Румельхартом, Дж. Е. Хинтоном и Рональдом Дж. Вильямсом и независимо и одновременно С.И. Барцевым и В.А. Охониным (Красноярская группа). Это итеративный градиентный алгоритм, который используется...
Интегральный криптоанализ — метод криптоанализа, объединяющий ряд атак на симметричные блочные криптографические алгоритмы. В отличие от дифференциального криптоанализа, который рассматривает воздействие алгоритма на пару открытых текстов, интегральный криптоанализ подразумевает исследование отображения в шифротекст множества открытых текстов. Впервые применен в 1997 Ларсом Кнудсеном.
Задача проверки планарности — это алгоритмическая задача проверки, является ли данный граф планарным (то есть, может ли он быть нарисован на плоскости без пересечения рёбер). Задача хорошо изучена в информатике и для неё было придумано много практических алгоритмов, многие из которых используют современные структуры данных. Большинство этих методов работают за время O(n) (линейное время), где n — число рёбер (или вершин) графа, что является асимптотически оптимальным алгоритмом. Вместо простого булевского...
Четыре четверки — математическая головоломка по поиску простейшего математического выражения для каждого целого числа от 0 до некоторого максимума, используя лишь общие математические символы и четвёрки (никакие другие цифры не допускаются). Большинство версий «четырёх четверок» требует, чтобы каждое выражение содержало ровно четыре четверки, но некоторые вариации требуют, чтобы каждое выражение имело минимальное количество четверок.
Вероятностно приблизительно корректное обучение (ВПК обучение, англ. Probably Approximately Correct learning, (PAC learning) в теории вычислительного обучения — это схема математического анализа машинного обучения. Схему предложил в 1984 Лесли Вэлиант.
Не путать с «симплекс-методом» — методом оптимизации произвольной функции. См. Метод Нелдера — МидаСимплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.
Подробнее: Симплекс-метод
Задача о рюкзаке (или задача о ранце) — NP-полная задача комбинаторной оптимизации. Своё название получила от конечной цели: уложить как можно большее число ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена. С различными вариациями задачи о рюкзаке можно столкнуться в экономике, прикладной математике, криптографии и логистике.
Геометрическая криптография — теоретические криптографические методы, в которых сообщения и шифротексты представлены в виде геометрических величин: углов, отрезков, а вычисления проводятся с помощью циркуля и линейки. Основана на сложности решения определенного класса геометрических задач, например, трисекции угла.
Односторонняя функция — математическая функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Здесь «легко» и «трудно» должны пониматься с точки зрения теории сложности вычислений. Разрыв между сложностью прямого и обратного преобразований определяет криптографическую эффективность односторонней функции. Неинъективность функции не является достаточным условием для того, чтобы называть её односторонней. Односторонние функции могут называться...
Полуопределённое программирование (en: Semidefinite programming, SDP) — это подраздел выпуклого программирования, которое занимается оптимизацией линейной целевой функции (целевая функция — это заданная пользователем функция, значение которой пользователь хочет минимизировать или максимизировать) на пересечении конусов положительно полуопределённых матриц с аффинным пространством.
Интерполяционный поиск (интерполирующий поиск) основан на принципе поиска в телефонной книге или, например, в словаре. Вместо сравнения каждого элемента с искомым, как при линейном поиске, данный алгоритм производит предсказание местонахождения элемента: поиск происходит подобно двоичному поиску, но вместо деления области поиска на две части, интерполирующий поиск производит оценку новой области поиска по расстоянию между ключом и текущим значением элемента. Другими словами, бинарный поиск учитывает...
В исследовании операций под аппроксимационным алгоритмом понимается алгоритм, использующийся для поиска приближённого решения оптимизационной задачи.
Подробнее: Аппроксимационный алгоритм
Полный перебор (или метод «грубой силы», англ. brute force) — метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных вариантов. Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.
Сжатие звука без потерь — совокупность преобразований, позволяющая эффективно сжимать звуковые данные с возможностью их полного восстановления. Как и любое сжатие без потерь, сжатие звуковых данных эксплуатирует какую-либо особенность данных. В данном случае это...