Связанные понятия
В комбинаторике последовательность Дэвенпорта — Шинцеля является последовательностью символов, в которой любые два символа могут появиться в чередующемся порядке ограниченное число раз. Максимальная возможная длина последовательности Дэвенпорта — Шинцеля ограничена числом символов, умноженном на небольшой постоянный множитель, который зависит от числа разрешённых чередований. Последовательности Дэвенпорта — Шинцеля были впервые определены в 1965 году Гарольдом Дэвенпортом и Анджеем Шинцелем для анализа...
Тест на следующий бит (англ. next-bit test) — тест, служащий для проверки генераторов псевдо-случайных чисел на криптостойкость. Тест гласит, что не должно существовать полиномиального алгоритма, который, зная первые k битов случайной последовательности, сможет предсказать k+1 бит с вероятностью, неравной ½.
Алгоритм большинства голосов Бойера — Мура — это алгоритм для нахождения преобладающего элемента последовательности. Преобладающим элементом последовательности длины n называется такой элемент этой последовательности, который встречается в ней более чем n/2 раз. Сложность данного алгоритма O(n), а требуемая дополнительная память — O(1).
В теории информации
теорема Шеннона об источнике шифрования (или теорема бесшумного шифрования) устанавливает предел максимального сжатия данных и числовое значение энтропии Шеннона.
Длинная арифметика — выполняемые с помощью вычислительной машины арифметические операции (сложение, вычитание, умножение, деление, возведение в степень, элементарные функции) над числами, разрядность которых превышает длину машинного слова данной вычислительной машины. Эти операции реализуются не аппаратно, а программно, с использованием базовых аппаратных средств работы с числами меньших порядков. Частный случай — арифметика произвольной точности — относится к арифметике, в которой длина чисел ограничена...
Циклический избыточный код (англ. Cyclic redundancy check, CRC) — алгоритм нахождения контрольной суммы, предназначенный для проверки целостности данных. CRC является практическим приложением помехоустойчивого кодирования, основанным на определённых математических свойствах циклического кода.
Пото́чный или Пото́ковый шифр — это симметричный шифр, в котором каждый символ открытого текста преобразуется в символ шифрованного текста в зависимости не только от используемого ключа, но и от его расположения в потоке открытого текста. Поточный шифр реализует другой подход к симметричному шифрованию, нежели блочные шифры.
Задача нахождения наибольшей общей подпоследовательности (англ. longest common subsequence, LCS) — задача поиска последовательности, которая является подпоследовательностью нескольких последовательностей (обычно двух). Часто задача определяется как поиск всех наибольших подпоследовательностей. Это классическая задача информатики, которая имеет приложения, в частности, в задаче сравнения текстовых файлов (утилита diff), а также в биоинформатике.
Подробнее: Наибольшая общая подпоследовательность
Симметри́чные криптосисте́мы (также симметричное шифрование, симметричные шифры) (англ. symmetric-key algorithm) — способ шифрования, в котором для шифрования и расшифровывания применяется один и тот же криптографический ключ. До изобретения схемы асимметричного шифрования единственным существовавшим способом являлось симметричное шифрование. Ключ алгоритма должен сохраняться в тайне обеими сторонами, осуществляться меры по защите доступа к каналу, на всем пути следования криптограммы, или сторонами...
Позиционная весовая матрица (ПВМ) — биоинформатический метод, который применяется для поиска мотивов в биологических последовательностях.
Алгоритм умножения Бута это алгоритм умножения, который позволяет перемножить два двоичных числа в дополнительном коде. Алгоритм был разработан Эндрю Дональдом Бутом в 1951 при проведении исследований в области кристаллографии в колледже им. Дж. Бирбека в Блумсбери (Лондон). Бут пользовался настольными вычислителями, которые выполняли операцию сдвига быстрее, чем операцию сложения, и создал алгоритм для увеличения скорости их работы. Алгоритм Бута представляет интерес при изучении архитектуры компьютера...
Алгоритм Блюма — Микали (англ. Blum-Micali algorithm) — это криптографически стойкий алогоритм генерации псевдослучайных последовательностей, с использованием зерна (Random seed). Идеи алгоритма были изложены Блюмом и Микали в 1984 году. Алгоритм был разработан на основе алгоритма генератора Шамира, предложенного Ади Шамиром годом ранее. Алгоритм отличается от предшественника более сильными требованиями к сложности вычисления выходной последовательности. В отличие от генератора Шамира выходом данного...
Строковое ядро — это ядерная функция, определённая на строках, т.е. конечных последовательностях символов, которые не обязательно имеют одну и ту же длину. Строковые ядра можно интуитивно понимать как функции, измеряющие похожесть пар строк — чем больше похожи две строки a и b, тем больше значение строкового ядра K(a, b).
Тасование Фишера — Йетса (названо в честь Рональда Фишера и Франка Йетса (Frank Yates)), известное также под именем Тасование Кнута (в честь Дональда Кнута), — это алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества. Вариант тасования Фишера-Йетса, известный как алгоритм Саттоло (Sattolo), может быть использован для генерации случайного цикла перестановок длины n. Правильно реализованный алгоритм тасования Фишера-Йетса несмещённый, так...
Свёртка последовательностей — это результат перемножения элементов двух заданных числовых последовательностей таким образом, что члены одной последовательности берутся с возрастанием индексов, а члены другой — с убыванием (что и служит основанием для принятого названия данной операции).
Случайная перестановка — это случайное упорядочение множества объектов, то есть случайная величина, элементарными событиями которой являются перестановки. Использование случайных перестановок зачастую является базой в областях, использующих рандомизированные алгоритмы. К таким областям относятся теория кодирования, криптография и моделирование. Хорошим примером случайной перестановки является тасование колоды карт.
Подробнее: Случайные перестановки
Двоичный алгоритм поиска подстроки (также bitap algorithm, shift-or algorithm) — алгоритм поиска подстроки, использующий тот факт, что в современных компьютерах битовый сдвиг и побитовое ИЛИ являются атомарными операциями. По сути, это примитивный алгоритм поиска с небольшой оптимизацией, благодаря которой за одну операцию производится до 32 сравнений одновременно (или до 64, в зависимости от разрядности машины). Легко переделывается на приблизительный поиск.
Сжатие звука без потерь — совокупность преобразований, позволяющая эффективно сжимать звуковые данные с возможностью их полного восстановления. Как и любое сжатие без потерь, сжатие звуковых данных эксплуатирует какую-либо особенность данных. В данном случае это...
Хеширование (англ. hashing – «превращать в фарш», «мешанина») — преобразование массива входных данных произвольной длины в (выходную) битовую строку установленной длины, выполняемое определённым алгоритмом. Функция, воплощающая алгоритм и выполняющая преобразование, называется «хеш-функцией» или «функцией свёртки». Исходные данные называются входным массивом, «ключом» или «сообщением». Результат преобразования (выходные данные) называется «хешем», «хеш-кодом», «хеш-суммой», «сводкой сообщения».
Алгоритм Флойда — Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом. При этом алгоритм впервые разработал и опубликовал Бернард Рой (англ. Bernard Roy) в 1959 году.
В математическом анализе и информатике кривая Мортона, Z-последовательность,Z-порядок, кривая Лебега, порядок Мортона или код Мортона — это функция, которая отображает многомерные данные в одномерные, сохраняя локальность точек данных. Функция была введена в 1966 Гаем Макдональдом Мортоном. Z-значение точки в многомерном пространстве легко вычисляется чередованием двоичных цифр его координатных значений. Когда данные запоминаются в этом порядке, могут быть использованы любые одномерные структуры...
Подробнее: Кривая Мортона
Би́товое поле (англ. bit field) в программировании — некоторое количество бит, расположенных последовательно в памяти, значение которых процессор не способен прочитать из-за особенностей аппаратной реализации.
Псевдопреобразова́ние Адама́ра (англ. Pseudo-Hadamard Transform, PHT) — обратимое преобразование битовых строк, используемое в криптографии для обеспечения диффузии при шифровании. Количество бит на входе преобразования должно быть чётным, чтобы было возможным разделение строки на две части равной длины. Создателем преобразования является французский математик Жак Адамар.
Универса́льное хеши́рование (англ. Universal hashing) — это вид хеширования, при котором используется не одна конкретная хеш-функция, а происходит выбор из заданного семейства по случайному алгоритму. Такой подход обеспечивает равномерное хеширование: для очередного ключа вероятности помещения его в любую ячейку совпадают. Известно несколько семейств универсальных хеш-функций, которые имеют многочисленные применения в информатике, в частности в хеш-таблицах, вероятностных алгоритмах и криптографии...
Криптосистема Накаша — Штерна (англ. Naccache — Stern cryptosystem)— криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи дискретного логарифмирования. В отличии от RSA, гомоморфен по сложению и вычитанию, а не по умножению...
Последовательность без простых чисел — это последовательность целых чисел, не содержащая каких-либо простых чисел. Как правило, при этом предполагается, что последовательность задана той же рекуррентной формулой, что и для чисел Фибоначчи, но с другими начальными условиями, и все члены последовательности должны быть cоставными числами, не имеющими общего для всех членов делителя. Таким образом, последовательность этих чисел определяется путём выбора двух составных чисел a1 и a2, для которых наибольший...
Целочисленная
последовательность называется полной последовательностью, если любое положительное целое число может быть выражено в виде суммы значений из последовательности, при этом каждое значение можно использовать только один раз.
Линейный криптоанализ был изобретён японским криптологом Мицуру Мацуи (яп. 松井 充 Мацуи Мицуру). Предложенный им в 1993 году (на конференции Eurocrypt '93) алгоритм был изначально направлен на вскрытие DES и FEAL. Впоследствии линейный криптоанализ был распространён и на другие алгоритмы. На сегодняшний день наряду с дифференциальным криптоанализом является одним из наиболее распространённых методов вскрытия блочных шифров. Разработаны атаки на блочные и потоковые шифры.
В информатике алгоритм выбора — это алгоритм для нахождения k-го по величине элемента в массиве (такой элемент называется k-й порядковой статистикой). Частными случаями этого алгоритма являются нахождение минимального элемента, максимального элемента и медианы. Существует алгоритм, который гарантированно решает задачу выбора k-го по величине элемента за O(n).
Алгоритм «прямого-обратного» хода — алгоритм для вычисления апостериорных вероятностей последовательности состояний при наличии последовательности наблюдений. Иначе говоря, алгоритм, вычисляющий вероятность специфической последовательности наблюдений. Алгоритм применяется в трёх алгоритмах скрытых Марковских моделей.
Битонная сортировка (англ. Bitonic sorter) — параллельный алгоритм сортировки данных, метод для создания сортировочной сети. Разработан американским информатиком Кеннетом Бэтчером в 1968 году. В основе алгоритма лежит понятие «битонной последовательности». Название было выбрано по аналогии с монотонной последовательностью.
Алгоритм Эндрю — алгоритм построения выпуклой оболочки в двумерном пространстве, модификация алгоритма Грэхема.
Код Хэ́мминга — вероятно, наиболее известный из первых самоконтролирующихся и самокорректирующихся кодов. Построен применительно к двоичной системе счисления. Позволяет исправлять одиночную ошибку (ошибка в одном бите) и находить двойную.
Числовая последовательность (ранее в русскоязычной математической литературе встречался термин вариа́нта, принадлежащий Ш. Мерэ) — это последовательность элементов числового пространства.
Целое , целочисленный тип данных (англ. Integer), в информатике — один из простейших и самых распространённых типов данных в языках программирования. Служит для представления целых чисел.
Алгоритм Дугласа-Пекера — это алгоритм, позволяющий уменьшить число точек кривой, аппроксимированной большей серией точек. Алгоритм был независимо открыт Урсом Рамером в 1972 и Давидом Дугласом и Томасом Пекером в 1973. Также алгоритм известен под следующими именами: алгоритм Рамера-Дугласа-Пекера, алгоритм итеративной ближайшей точки и алгоритм разбиения и слияния.
Компьютер для операций с математическими функциями (в отличие от обычного компьютера) оперирует с функциями на аппаратном уровне (то есть без программирования этих операций).
Алгоритм Берлекэмпа — Мэсси — алгоритм поиска кратчайшего регистра сдвига с линейной обратной связью для поданной на вход бинарной последовательности. Также алгоритм позволяет найти минимальный многочлен поданной на вход линейной рекуррентной последовательности над произвольным полем.
Байесовский подход в филогенетике позволяет получить наиболее вероятное филогенетическое дерево при заданных исходных данных, последовательностях ДНК или белков рассматриваемых организмов и эволюционной модели замен. Для снижения вычислительной сложности алгоритма расчёт апостериорной вероятности реализуется различными алгоритмами, использующими метод Монте-Карло для марковских цепей. Главными преимуществами байесовского подхода по сравнению с методами максимального правдоподобия и максимальной экономии...
Самосверточный генератор — это генератор псевдослучайных чисел, который основан на идеи сверточного генератора. Однако в отличие от него самосверточный генератор использует только один регистор сдвига с линейной обратной связью.
Алгоритм Гельфонда — Шенкса (англ. Baby-step giant-step; также называемый алгоритмом больших и малых шагов) — в теории групп детерминированный алгоритм дискретного логарифмирования в мульпликативной группе кольца вычетов по модулю простого числа. Был предложен советским математиком Александром Гельфондом в 1962 году и Дэниэлем Шенксом в 1972 году.
ГОСТ Р 34.11-94 — устаревший российский криптографический стандарт вычисления хеш-функции.
Односторонняя функция — математическая функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Здесь «легко» и «трудно» должны пониматься с точки зрения теории сложности вычислений. Разрыв между сложностью прямого и обратного преобразований определяет криптографическую эффективность односторонней функции. Неинъективность функции не является достаточным условием для того, чтобы называть её односторонней. Односторонние функции могут называться...
Линейный конгруэнтный метод — один из методов генерации псевдослучайных чисел. Применяется в простых случаях и не обладает криптографической стойкостью. Входит в стандартные библиотеки различных компиляторов.
Лавинный эффект (англ. Avalanche effect) — понятие в криптографии, обычно применяемое к блочным шифрам и криптографическим хеш-функциям. Важное криптографическое свойство для шифрования, которое означает, что изменение значения малого количества битов во входном тексте или в ключе ведет к «лавинному» изменению значений выходных битов шифротекста. Другими словами, это зависимость всех выходных битов от каждого входного бита.
Блочная сортировка (Карманная сортировка, корзинная сортировка, англ. Bucket sort) — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем...