Связанные понятия
Ранцевая криптосистема Шора-Ривеста была предложена в 1985 году (Chor, 1985; Chor and Rivest, 1988). В настоящее время она является единственной известной схемой шифрования, основанной на задаче о ранце, которая не использует модульного умножения для маскировки простой задачи о ранце На данный момент создано множество рюкзачных криптосистем, например ранцевая криптосистема Меркла — Хеллмана. Однако практически все существующие на сегодняшний день взломаны или признаны потенциально небезопасными...
Псевдопреобразова́ние Адама́ра (англ. Pseudo-Hadamard Transform, PHT) — обратимое преобразование битовых строк, используемое в криптографии для обеспечения диффузии при шифровании. Количество бит на входе преобразования должно быть чётным, чтобы было возможным разделение строки на две части равной длины. Создателем преобразования является французский математик Жак Адамар.
В комбинаторике последовательность Дэвенпорта — Шинцеля является последовательностью символов, в которой любые два символа могут появиться в чередующемся порядке ограниченное число раз. Максимальная возможная длина последовательности Дэвенпорта — Шинцеля ограничена числом символов, умноженном на небольшой постоянный множитель, который зависит от числа разрешённых чередований. Последовательности Дэвенпорта — Шинцеля были впервые определены в 1965 году Гарольдом Дэвенпортом и Анджеем Шинцелем для анализа...
Алгоритм исчисления порядка (index-calculus algorithm) — вероятностный алгоритм вычисления дискретного логарифма в кольце вычетов по модулю простого числа. На сложности нахождения дискретного логарифма основано множество алгоритмов связанных с криптографией. Так как для решения данной задачи с использованием больших чисел требуется большое количество ресурсов, предоставить которые не может ни один современный компьютер. Примером такого алгоритма является ГОСТ Р 34.10-2012.
Алгоритм Джонсона — позволяет найти кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. Данный алгоритм работает, если в графе содержатся рёбра с положительным или отрицательным весом, но отсутствуют циклы с отрицательным весом.
Перенос и заём в арифметике — приёмы, применяемые в арифметических алгоритмах позиционных систем счисления при выполнении операций сложения и вычитания соответственно, а также (в составе тех же сложения и вычитания) и иных арифметичких операций. Перенос можно понимать как выделение умножения на основание системы счисления в отдельное слагаемое, с последующей перегруппировкой слагаемых.
Лине́йная интерполя́ция — интерполяция алгебраическим двучленом P1(x) = ax + b функции f, заданной в двух точках x0 и x1 отрезка . В случае, если заданы значения в нескольких точках, функция заменяется кусочно-линейной функцией.
Целочисленная сортировка — это задача сортировки коллекции значений данных при помощи целочисленных ключей. Алгоритмы целочисленной сортировки можно применять и для задач, в которых ключами являются числа с плавающей запятой или текстовые строки. Возможность выполнения целочисленных арифметических операций над ключами позволяет алгоритмам целочисленной сортировки быть во многих случаях быстрее, чем аналогичные алгоритмы сортировки с использованием сравнений, в зависимости от допустимых в модели вычислений...
Квазиньютоновские методы — методы оптимизации, основанные на накоплении информации о кривизне целевой функции по наблюдениям за изменением градиента, чем принципиально отличаются от ньютоновских методов. Класс квазиньютоновских методов исключает явное формирование матрицы Гессе, заменяя её некоторым приближением.
Зако́н Амдала (англ. Amdahl's law, иногда также Закон Амдаля-Уэра) — иллюстрирует ограничение роста производительности вычислительной системы с увеличением количества вычислителей. Джин Амдал сформулировал закон в 1967 году, обнаружив простое по существу, но непреодолимое по содержанию ограничение на рост производительности при распараллеливании вычислений: «В случае, когда задача разделяется на несколько частей, суммарное время её выполнения на параллельной системе не может быть меньше времени выполнения...
Итерация в программировании — в широком смысле — организация обработки данных, при которой действия повторяются многократно, не приводя при этом к вызовам самих себя (в отличие от рекурсии). В узком смысле — один шаг итерационного, циклического процесса.
Алгоритм Дугласа-Пекера — это алгоритм, позволяющий уменьшить число точек кривой, аппроксимированной большей серией точек. Алгоритм был независимо открыт Урсом Рамером в 1972 и Давидом Дугласом и Томасом Пекером в 1973. Также алгоритм известен под следующими именами: алгоритм Рамера-Дугласа-Пекера, алгоритм итеративной ближайшей точки и алгоритм разбиения и слияния.
Макроконвейер — распределенная многопроцессорная система, обладающая программной и аппаратной поддержкой организации вычислений по макроконвейерному принципу. Этот принцип был предложен в 1978 году советским математиком В. М. Глушковым. Его суть состоит в том, что при распределении вычислительных заданий между процессорами каждому процессору на очередном шаге вычислений дается такое задание, которое может загрузить его работой на определенное время, без взаимодействия с другими процессорами. Последовательное...
Граф зависи́мостей — ориентированный граф, отображающий соотношение множества элементов некоторой совокупности в соответствии с выбранным транзитивным отношением над ней.
Перебор делителей (пробное деление) — алгоритм факторизации или тестирования простоты числа путём полного перебора всех возможных потенциальных делителей.
Список с пропусками (англ. Skip List) — вероятностная структура данных, основанная на нескольких параллельных отсортированных связных списках с эффективностью, сравнимой с двоичным деревом (порядка O(log n) среднее время для большинства операций).
Комбинаторный взрыв — термин, используемый для описания эффекта резкого («взрывного») роста временной сложности алгоритма при увеличении размера входных данных задачи.
Слабая сходимость в функциональном анализе — вид сходимости в топологических векторных пространствах.
Модели дискретного выбора — экономические (эконометрические) модели, позволяющие описывать, объяснять и прогнозировать выбор между, двумя или более альтернативами (то есть когда множество альтернатив не более чем счетно). Модели дискретного выбора позволяют на основе некоторых характеристик (атрибутов) экономического субъекта или ситуации оценить вероятность выбора той или иной альтернативы.
Подробнее: Дискретный выбор
Производящий функционал — это расширение понятия производящей функции моментов для одномерного / конечномерного распределения Гаусса на континуальное распределение Гаусса.
В геометрии
домино замощение области в евклидовой плоскости — это мозаика области плитками домино, образованными объединением двух единичных квадратов, соединённых по ребру. Эквивалентно это паросочетание в графе решётки, образованное помещением вершины в центр каждого квадрата области и соединением двух вершин, если два соответствующих квадрата смежны.
Мажорита́рный элеме́нт (мажоритарный клапан, переключатель по большинству, ППБ) — логический элемент из класса пороговых, с чётным или нечётным числом входов и одним выходным сигналом, значение которого совпадает со значением на большинстве входов. При чётном числе входов большинством считается n/2+1, соответственно, n/2 к большинству не относится. Таким образом, элемент работает по «принципу большинства»: если на большинстве входов будет сигнал «1», то и на выходе схемы установится сигнал «1»; и...
Группа Григорчука — первый пример конечнопорождённой группы промежуточного роста (то есть её рост быстрее полиномиального, но медленнее экспоненциального).
В данной статье приведен список различных квадратурных формул, для численного интегрирования.
Подробнее: Список квадратурных формул
Эллиптические уравнения — класс дифференциальных уравнений в частных производных, описывающих стационарные процессы.
Подробнее: Эллиптическое уравнение
Говорят, что ориентированный
граф апериодичен, если нет целого числа k > 1, делящего длину любого цикла графа. Эквивалентно, граф апериодичен, если наибольший общий делитель длин его циклов равен единице. Этот наибольший общий делитель для графа G называется периодом графа G.
Двунаправленный поиск пути в ширину (или глубину) — усложнённый алгоритм поиска в ширину (или глубину), идея которого заключается в формировании процесса поиска от начальной (прямой поиск) и от конечной вершины (обратный поиск) графа.
Метод спектрального элемента (МСЭ) для решения дифференциальных уравнений в частных производных — это метод конечных элементов, в котором используются кусочные многочлены высокой степени в качестве базисных функций. Метод спектрального элемента предложил в статье 1984 года Т. Патера.
В теории графов графом единичных кругов называется граф пересечений семейства единичных кругов на евклидовой плоскости. То есть мы образуем вершину для каждого круга и соединяем две вершины ребром, если соответствующие круги пересекаются.
Подробнее: Граф единичных кругов
Область главных идеалов — это область целостности, в которой любой идеал является главным. Более общее понятие — кольцо главных идеалов, от которого не требуется целостности (однако некоторые авторы, например Бурбаки, ссылаются на кольцо главных идеалов как на целостное кольцо).
Комплекс Кошуля был впервые введён в математике Жаном-Луи Кошулем, чтобы определить теорию когомологий алгебр Ли. Впоследствии он оказался полезной общей конструкцией гомологической алгебры. Его гомологии могут быть использованы для того, чтобы определить, является ли последовательность элементов кольца M-регулярной, и, как следствие, он может быть использован ля того, чтобы доказать базовые свойства глубины модуля или идеала.
Гибри́дная (или комбини́рованная) криптосисте́ма — это система шифрования, совмещающая преимущества криптосистемы с открытым ключом с производительностью симметричных криптосистем. Симметричный ключ используется для шифрования данных, а асимметричный для шифрования самого симметричного ключа, иначе это называется числовой упаковкой.
В коммутативной алгебре, дробный идеал — это обобщение понятия идеала целостного кольца, особенно полезное при изучении дедекиндовых колец. Условно говоря, дробные идеалы — это идеалы со знаменателями. В случаях, когда одновременно обсуждаются дробные и обычные идеалы, последние называют целыми идеалами.
В математике константой
Чигера (также числом Чигера или изопериметрическим числом) графа называется числовая характеристика графа, отражающая, есть ли у графа «узкое место» или нет. Константа Чигера как способ измерения наличия «узкого места» представляет интерес во многих областях, например, для создания сильно связанных компьютерных сетей, для тасования карт и в топологии малых размерностей (в частности, при изучении гиперболических 3-мерных многообразий). Названа в честь математика Джефа Чигера...
Метод простой итерации — один из простейших численных методов решения уравнений. Метод основан на принципе сжимающего отображения, который применительно к численным методам в общем виде также может называться методом простой итерации или методом последовательных приближений. В частности, для систем линейных алгебраических уравнений существует аналогичный метод итерации.
Алгебраическая связность графа G — это второе из минимальных собственных значений матрицы Кирхгофа графа G. Это значение больше нуля в том и только в том случае, когда граф G является связным. Это следствие того факта, что сколько раз значение 0 появляется в качестве собственного значения матрицы Кирхгофа, из стольких компонент связности состоит граф. Величина этого значения отражает насколько хорошо связен весь граф и используется для анализа устойчивости и синхронизации сетей.
В теории колец,
простой модуль (также используется название «неприводимый модуль») над кольцом R — это модуль над R, не имеющий ненулевых собственных подмодулей. Эквивалентно, модуль является простым тогда и только тогда, когда любой циклический модуль, порожденный одним его элементом (ненулевым элементом), совпадает со всем модулем. Простые модули служат для построения модулей конечной длины, в этом смысле они похожи на простые группы.
В статистике метод оценки с помощью апостериорного максимума (MAP) тесно связан с методом максимального правдоподобия (ML), но дополнительно при оптимизации использует априорное распределение величины, которую оценивает.
Подробнее: Оценка апостериорного максимума
Избыточность — термин из теории информации, означающий превышение количества информации, используемой для передачи или хранения сообщения, над его информационной энтропией. Для уменьшения избыточности применяется сжатие данных без потерь, в то же время контрольная сумма применяется для внесения дополнительной избыточности в поток, что позволяет производить исправление ошибок при передаче информации по каналам, вносящим искажения (спутниковая трансляция, беспроводная передача и т. д.).
Зада́ча Не́ймана , вторая краевая задача — в дифференциальных уравнениях краевая задача с заданными граничными условиями для производной искомой функции на границе области — так называемые граничные условия второго рода. По типу области задачи Неймана можно разделить на два типа: внутренние и внешние. Названа в честь Карла Неймана.
Метод характеристик — метод решения дифференциальных уравнений в частных производных. Обычно применяется к решению уравнений в частных производных первого порядка, но он может быть применен и к решению гиперболических уравнений более высокого порядка.
Гипотеза об экспоненциальном времени — это недоказанное допущение о вычислительной сложности, которое сформулировали Импальяццо и Патури. Гипотеза утверждает, что 3-SAT (или любая из связанных NP-полных задач) не может быть решена за субэкспоненциальное время в худшем случае. Из верности гипотезы об экспоненциальном времени, если она верна, следовало бы, что P ≠ NP, но гипотеза является более сильным утверждением. Из утверждения гипотезы можно показать, что многие вычислительные задачи эквиваленты...
Лексикографический поиск в ширину (англ. lexicographic breadth-first search, LBFS or Lex-BFS) — алгоритм упорядочивания вершин графа. Алгоритм отличается от алгоритма поиска в ширину и дает более упорядоченную последовательность вершин графа.
(Топологический)
индекс Хосойи , известный также как Z индекс, графа — это полное число паросочетаний на нём. Индекс Хосойи всегда больше либо равен одному, поскольку пустое множество рёбер считается как паросочетание. Эквивалентно, индекс Хосойи — это число непустых паросочетаний плюс один.