Связанные понятия
В математике деление на два, деление пополам — это математическая операция, частный случай деления. Древние египтяне отличали деление на два от деления на другие числа, поскольку их алгоритм умножения использовал деление на два как один из промежуточных этапов. В XVI веке некоторые математики предложили рассматривать деление на два как операцию, отличающуюся от деления на другие числа. В современном программировании также иногда выделяют деление именно на два.
Дополнительный код (англ. two’s complement, иногда twos-complement) — наиболее распространённый способ представления отрицательных целых чисел в компьютерах. Он позволяет заменить операцию вычитания на операцию сложения и сделать операции сложения и вычитания одинаковыми для знаковых и беззнаковых чисел, чем упрощает архитектуру ЭВМ. В англоязычной литературе обратный код называют первым дополнением, а дополнительный код называют вторым дополнением.
Свёртка последовательностей — это результат перемножения элементов двух заданных числовых последовательностей таким образом, что члены одной последовательности берутся с возрастанием индексов, а члены другой — с убыванием (что и служит основанием для принятого названия данной операции).
Прямой код — способ представления двоичных чисел с фиксированной запятой в компьютерной арифметике. Главным образом используется для записи неотрицательных чисел. В случае использования прямого кода для чисел как положительных, так и отрицательных, то есть чисел, запись которых подразумевает возможность использования знака минус (знаковых чисел), хранимые цифровые разряды числа дополняются знаковым разрядом.
В теории информации
теорема Шеннона об источнике шифрования (или теорема бесшумного шифрования) устанавливает предел максимального сжатия данных и числовое значение энтропии Шеннона.
Цифрово́й компара́тор или компара́тор ко́дов логическое устройство с двумя словарными входами, на которые подаются два разных двоичных слова равной в битах длины и обычно с тремя двоичными выходами, на которые выдаётся признак сравнения входных слов, — первое слово больше второго, меньше или слова равны. При этом выходы «больше», «меньше» имеют смысл, если входные слова кодируют числа в том или ином машинном представлении.
Полусумма́тор — комбинационная логическая схема, имеющая два входа и два выхода (двухразрядный сумматор, бинарный сумматор). Полусумматор позволяет вычислять сумму A+B, где A и B — это разряды (биты) обычно двоичного числа, при этом результатом будут два бита S и C, где S — это бит суммы по модулю 2, а C — бит переноса.
Алгоритм Гельфонда — Шенкса (англ. Baby-step giant-step; также называемый алгоритмом больших и малых шагов) — в теории групп детерминированный алгоритм дискретного логарифмирования в мульпликативной группе кольца вычетов по модулю простого числа. Был предложен советским математиком Александром Гельфондом в 1962 году и Дэниэлем Шенксом в 1972 году.
Основная теорема о рекуррентных соотношениях (англ. Master theorem) используется в анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй и властвуй» (divide and conquer), например, при оценке времени их выполнения. Теорема была популяризована в книге Алгоритмы: построение и анализ (Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн), в которой она была введена и доказана.
Строковое ядро — это ядерная функция, определённая на строках, т.е. конечных последовательностях символов, которые не обязательно имеют одну и ту же длину. Строковые ядра можно интуитивно понимать как функции, измеряющие похожесть пар строк — чем больше похожи две строки a и b, тем больше значение строкового ядра K(a, b).
Универса́льное хеши́рование (англ. Universal hashing) — это вид хеширования, при котором используется не одна конкретная хеш-функция, а происходит выбор из заданного семейства по случайному алгоритму. Такой подход обеспечивает равномерное хеширование: для очередного ключа вероятности помещения его в любую ячейку совпадают. Известно несколько семейств универсальных хеш-функций, которые имеют многочисленные применения в информатике, в частности в хеш-таблицах, вероятностных алгоритмах и криптографии...
Алгоритм Грэхема — алгоритм построения выпуклой оболочки в двумерном пространстве.
Обратный код (англ. ones' complement) — метод вычислительной математики, позволяющий вычесть одно число из другого, используя только операцию сложения над натуральными числами. Ранее метод использовался в механических калькуляторах (арифмометрах). Многие ранние компьютеры, включая CDC 6600, LINC, PDP-1 и UNIVAC 1107, использовали обратный код. Большинство современных компьютеров используют дополнительный код.
Матрица жёсткости (матрица Дирихле) — матрица особого вида, использующаяся в методе конечных элементов для решения дифференциальных уравнений в частных производных. Она применяется при решениях задач электродинамики и механики.
Математические обозначения («язык математики») — сложная графическая система обозначений, служащая для изложения абстрактных математических идей и суждений в человеко-читаемой форме. Составляет (по своей сложности и разнообразию) значительную долю неречевых знаковых систем, применяемых человечеством. В данной статье описывается общепринятая международная система обозначений, хотя различные культуры прошлого имели свои собственные, и некоторые из них даже имеют ограниченное применение до сих пор...
Бесконечная группа — группа с бесконечным числом элементов, в противоположность конечным группам.
Циклический код — линейный, блочный код, обладающий свойством цикличности, то есть каждая циклическая перестановка кодового слова также является кодовым словом. Используется для преобразования информации для защиты её от ошибок (см. Обнаружение и исправление ошибок).
Циклическое число — целое число, циклические перестановки цифр которого являются произведениями этого числа на последовательные числа. Наиболее известный пример такого числа — 142857...
Сумматор с сохранением переноса (англ. carry-save adder) — является видом цифровых сумматоров, используемых в компьютерной микроархитектуре для вычисления суммы трёх или более n-битных чисел в двоичной системе счисления. Он отличается от других цифровых сумматоров тем, что его выходные два числа той же размерности, что и входные, одно из которых является частной суммой битов, а другое является последовательностью битов переноса.
В области математики и теории информации линейный код — это важный тип блокового кода, использующийся в схемах определения и коррекции ошибок. Линейные коды, по сравнению с другими кодами, позволяют реализовывать более эффективные алгоритмы кодирования и декодирования информации.
Подробнее: Линейный код
Криптосистема Уильямса (Williams System) — система шифрования с открытым ключом, созданная Хью Коуи Уильямсом (Hugh Cowie Williams) в 1984 году.
Блочный код — в информатике тип канального кодирования. Он увеличивает избыточность сообщения так, чтобы в приёмнике можно было расшифровать его с минимальной (теоретически нулевой) погрешностью, при условии, что скорость передачи информации (количество передаваемой информации в битах в секунду) не превысила бы канальную производительность.
Код Хэ́мминга — вероятно, наиболее известный из первых самоконтролирующихся и самокорректирующихся кодов. Построен применительно к двоичной системе счисления. Позволяет исправлять одиночную ошибку (ошибка в одном бите) и находить двойную.
Предобуславливание (также предобусловливание) — процесс преобразования условий задачи для её более корректного численного решения. Предобуславливание обычно связано с уменьшением числа обусловленности задачи. Предобуславливаемая задача обычно затем решается итерационным методом.
Магма (группоид) в общей алгебре — алгебра, состоящая из множества М с одной бинарной операцией M × M → M. Помимо требования замкнутости множества относительно заданной на нём операции, других требований к операции и множеству не предъявляется.
Итеративное сжатие — это алгоритмическая техника разработки фиксированно-параметрически разрешимых алгоритмов, в которой один элемент (такой как вершина графа) добавляется в задачу на каждом шаге и используется небольшое решение задачи перед добавлением элемента, чтобы найти небольшое решение задачи после добавления.
Точное нахождение первообразной (или интеграла) произвольных функций — процедура более сложная, чем «дифференцирование», то есть нахождение производной. Зачастую, выразить интеграл в элементарных функциях невозможно.
Подробнее: Методы интегрирования
Денормализованные числа (англ. denormalized numbers) или субнормальные числа (англ. subnormal numbers) — вид чисел с плавающей запятой, определённый в стандарте IEEE 754. При записи в форматах float, double, long double их экспонента будет записана как 0. Для получения их значения не требуется использование неявной единицы; мантисса просто умножается на наименьшую для данного формата экспоненту.
Гистогра́мма в математической статистике — это функция, приближающая плотность вероятности некоторого распределения, построенная на основе выборки из него.
Диаграмма Насси — Шнейдермана (англ. Nassi — Shneiderman diagram) — это графический способ представления структурированных алгоритмов и программ, разработанный в 1972 году американскими аспирантами Беном Шнейдерманом и Айзеком Насси.
Код Гре́я — двоичный код, иначе зеркальный код, он же код с отражением, в котором две «соседние» (в упорядоченном, то есть лексикографическом, наборе) кодовые комбинации различаются только цифрой в одном двоичном разряде. Иными словами, расстояние Хэмминга между соседними кодовыми комбинациями равно 1.
Пре́фиксный код в теории кодирования — код со словом переменной длины, имеющий такое свойство (выполнение условия Фано): если в код входит слово a, то для любой непустой строки b слова ab в коде не существует. Хотя префиксный код состоит из слов разной длины, эти слова можно записывать без разделительного символа.
В прикладной статистике метод наименьших полных квадратов (МНПК, TLS — англ. Total Least Squares) — это вид регрессии с ошибками в переменных, техника моделирования данных с помощью метода наименьших квадратов, в которой принимаются во внимание ошибки как в зависимых, так и в независимых переменных. Метод является обобщением регрессии Деминга и ортогональной регрессии и может быть применён как к линейным, так и нелинейным моделям.
Мультииндекс (или мульти-индекс) — обобщение понятия целочисленного индекса до векторного индекса, которое нашло применение в различных областях математики, связанных с функциями многих переменных. Использование мультииндекса помогает упростить (записать более кратко) математические формулы.
Алгоритм Берлекэмпа — Мэсси — алгоритм поиска кратчайшего регистра сдвига с линейной обратной связью для поданной на вход бинарной последовательности. Также алгоритм позволяет найти минимальный многочлен поданной на вход линейной рекуррентной последовательности над произвольным полем.
В математике и информатике подстановка — это операция синтаксической замены подтермов данного терма другими термами, согласно определённым правилам. Обычно речь идёт о подстановке терма вместо переменной.
Подробнее: Подстановка
Метод неопределённых коэффициентов ― метод, используемый в математике для нахождения искомой функции в виде точной или приближённой линейной комбинации конечного или бесконечного набора базовых функций.
Таблица поиска (англ. lookup table) — это структура данных, обычно массив или ассоциативный массив, используемая с целью заменить вычисления на операцию простого поиска. Увеличение скорости может быть значительным, так как получить данные из памяти зачастую быстрее, чем выполнить трудоёмкие вычисления.
Аффинный шифр — это частный случай более общего моноалфавитного шифра подстановки. К шифрам подстановки относятся также шифр Цезаря, ROT13 и Атбаш. Поскольку аффинный шифр легко дешифровать, он обладает слабыми криптографическими свойствами.
Алгоритм Гёрцеля (англ. Goertzel algorithm) — это специальная реализация дискретного преобразования Фурье (ДПФ) в форме рекурсивного фильтра. Данный алгоритм был предложен Джеральдом Гёрцелем в 1958 году. В отличие от быстрого преобразования Фурье, вычисляющего все частотные компоненты ДПФ, алгоритм Гёрцеля позволяет эффективно вычислить значение одного частотного компонента.
Формальное дифференцирование — операция над элементами кольца многочленов или кольцом формальных степенных рядов, повторяющая форму производных из математического анализа. Алгебраическое преимущество формального дифференцирования состоит в том, что оно не опирается на понятие предела, которое в общем случае невозможно определить для кольца. Многие свойства производной верны для формального дифференцирования, но некоторые, особенно касающиеся утверждений, содержащих числа, не верны. В основном формальное...
Распределением
регистров в процессе компиляции называется отображение множества большого числа переменных фрагмента компьютерной программы (виртуальных регистров промежуточного представления) на, как правило, небольшое множество физических регистров микропроцессора. Распределение регистров может выполняться в отдельно взятом базовом блоке (локальное распределение регистров) или во всей процедуре (глобальное распределение регистров).
Оператор Собеля — дискретный дифференциальный оператор, вычисляющий приближённое значение градиента яркости изображения. Результатом применения оператора Собеля в каждой точке изображения является либо вектор градиента яркости в этой точке, либо его норма. Используется в области обработки изображений, в частности, часто применяется в алгоритмах выделения границ.
Система типов Си — реализация понятия типа данных в языке программирования Си. Сам язык предоставляет базовые арифметические типы, а также синтаксис для создания массивов и составных типов. Некоторые заголовочные файлы из стандартной библиотеки Си содержат определения типов с дополнительными свойствами.
Двоичный алгоритм поиска подстроки (также bitap algorithm, shift-or algorithm) — алгоритм поиска подстроки, использующий тот факт, что в современных компьютерах битовый сдвиг и побитовое ИЛИ являются атомарными операциями. По сути, это примитивный алгоритм поиска с небольшой оптимизацией, благодаря которой за одну операцию производится до 32 сравнений одновременно (или до 64, в зависимости от разрядности машины). Легко переделывается на приблизительный поиск.