Связанные понятия
Квантовый вентиль (квантовый логический элемент) — это базовый элемент квантового компьютера, преобразующий входные состояния кубитов на выходные по определённому закону. Отличается от обычных логических вентилей тем, что работает с кубитами, а следовательно подчиняется квантовой логике. Квантовые вентили в отличие от многих классических всегда являются обратимыми.
Квантовый алгоритм — это алгоритм, предназначенный для выполнения на квантовом компьютере.
Линеаризация (от лат. linearis — линейный) — один из методов приближённого представления замкнутых нелинейных систем, при котором исследование нелинейной системы заменяется анализом линейной системы, в некотором смысле эквивалентной исходной. Методы линеаризации имеют ограниченный характер, т. е. эквивалентность исходной нелинейной системы и её линейного приближения сохраняется лишь для ограниченных пространственных или временных масштабов системы, либо для определенных процессов, причём, если система...
Аппара́тный генера́тор случа́йных чи́сел (генератор истинно случайных чисел) — устройство, которое генерирует последовательность случайных чисел на основе измеряемых, хаотически изменяющихся параметров протекающего физического процесса. Работа таких устройств часто основана на использовании надёжных источников энтропии, таких, как тепловой шум, дробовой шум, фотоэлектрический эффект, квантовые явления и т. д. Эти процессы в теории абсолютно непредсказуемы, на практике же получаемые из них случайные...
Трит — логарифмическая единица измерения в теории информации, минимальная целая единица измерения количества информации источников с тремя равновероятными сообщениями. Энтропию в 1 трит имеет источник информации с тремя равновероятными состояниями. Проще говоря, по аналогии с битом, который «уменьшает незнание» об исследуемом объекте в два раза, трит «уменьшает незнание» в три раза.
Комбинационная логика (комбинационная схема) в теории цифровых устройств — двоичная логика функционирования устройств комбинационного типа. У комбинационных устройств состояние выхода однозначно определяется набором входных сигналов, что отличает комбинационную логику от секвенциальной логики, в рамках которой выходное значение зависит не только от текущего входного воздействия, но и от предыстории функционирования цифрового устройства. Другими словами, секвенциальная логика предполагает наличие...
Теоре́ма о запре́те клони́рования — утверждение квантовой теории о невозможности создания идеальной копии произвольного неизвестного квантового состояния. Теорема была сформулирована Вуттерсом, Зуреком и Диэксом в 1982 году и имела огромное значение в области квантовых вычислений, квантовой теории информации и смежных областях.
Основная теорема о рекуррентных соотношениях (англ. Master theorem) используется в анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй и властвуй» (divide and conquer), например, при оценке времени их выполнения. Теорема была популяризована в книге Алгоритмы: построение и анализ (Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн), в которой она была введена и доказана.
Семплирование по Гиббсу — алгоритм для генерации выборки совместного распределения множества случайных величин. Он используется для оценки совместного распределения и для вычисления интегралов методом Монте-Карло. Этот алгоритм является частным случаем алгоритма Метрополиса-Гастингса и назван в честь физика Джозайи Гиббса.
Предобуславливание (также предобусловливание) — процесс преобразования условий задачи для её более корректного численного решения. Предобуславливание обычно связано с уменьшением числа обусловленности задачи. Предобуславливаемая задача обычно затем решается итерационным методом.
Алгоритм Баума — Велша используется в информатике и статистике для нахождения неизвестных параметров скрытой марковской модели (HMM). Он использует алгоритм прямого-обратного хода и является частным случаем обобщённого EM-алгоритма.
Блочный Гамильтониан — гамильтониан, описывающий критическое поведение магнетика вблизи точки фазового перехода второго рода.
Счётчик числа импульсов — устройство, на выходах которого получается двоичный (двоично-десятичный) код, определяемый числом поступивших импульсов. Счётчики могут строиться на двухступенчатых D-триггерах, T-триггерах и JK-триггерах.
Корректно поставленная задача в математике — прикладная задача, математическое решение которой существует, единственно и устойчиво. Происходит от определения, данного Жаком Адамаром, согласно которому математические модели физических явлений должны иметь следующие свойства...
Цифрово́й компара́тор или компара́тор ко́дов логическое устройство с двумя словарными входами, на которые подаются два разных двоичных слова равной в битах длины и обычно с тремя двоичными выходами, на которые выдаётся признак сравнения входных слов, — первое слово больше второго, меньше или слова равны. При этом выходы «больше», «меньше» имеют смысл, если входные слова кодируют числа в том или ином машинном представлении.
Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.
Лине́йная систе́ма — любая система, для которой отклик системы на сумму воздействий равен сумме откликов на каждое воздействие. В математической модели линейной системы это означает, что оператор преобразования "вход-выход" линеен. Иногда линейное свойство системы называют принципом суперпозиции.
Норма́льный алгори́тм (алгори́фм) Ма́ркова (НАМ, также марковский алгоритм) — один из стандартных способов формального определения понятия алгоритма (другой известный способ — машина Тьюринга). Понятие нормального алгоритма введено А. А. Марковым (младшим) в конце 1940-х годов в работах по неразрешимости некоторых проблем теории ассоциативных вычислений. Традиционное написание и произношение слова «алгорифм» в этом термине также восходит к его автору, многие годы читавшему курс математической логики...
Операционное исчисление — один из методов математического анализа, позволяющий в ряде случаев с помощью простых средств решать сложные математические задачи.
Линейный конгруэнтный метод — один из методов генерации псевдослучайных чисел. Применяется в простых случаях и не обладает криптографической стойкостью. Входит в стандартные библиотеки различных компиляторов.
В математике и информатике подстановка — это операция синтаксической замены подтермов данного терма другими термами, согласно определённым правилам. Обычно речь идёт о подстановке терма вместо переменной.
Подробнее: Подстановка
В логике логи́ческими опера́циями называют действия, вследствие которых порождаются новые понятия, с использованием уже существующих. В более узком смысле, понятие логической операции используется в математической логике и программировании.
Подробнее: Логическая операция
Алгоритм Гёрцеля (англ. Goertzel algorithm) — это специальная реализация дискретного преобразования Фурье (ДПФ) в форме рекурсивного фильтра. Данный алгоритм был предложен Джеральдом Гёрцелем в 1958 году. В отличие от быстрого преобразования Фурье, вычисляющего все частотные компоненты ДПФ, алгоритм Гёрцеля позволяет эффективно вычислить значение одного частотного компонента.
Структурная индукция — конструктивный метод математического доказательства, обобщающий математическую индукцию (применяемую над натуральным рядом) на произвольные рекурсивно определённые частично упорядоченные совокупности. Структурная рекурсия — реализация структурной индукции в форме определения, процедуры доказательства или программы, обеспечивающая индукционный переход над частично упорядоченной совокупностью.
Уравнение ренормгруппы (уравнение Каллана — Симанчика) — дифференциальное уравнение для корреляционных функций (пропагаторов), показывающее их независимость от масштаба рассмотрения. Оно имеет место, например, при рассмотрении динамики системы вблизи критической точки.
Проклятие размерности (ПР) — термин, используемый в отношении ряда свойств многомерных пространств и комбинаторных задач. В первую очередь это касается экспоненциального роста необходимых экспериментальных данных в зависимости от размерности пространства при решении задач вероятностно-статистического распознавания образов, машинного обучения, классификации и дискриминантного анализа. Также это касается экспоненциального роста числа вариантов в комбинаторных задачах в зависимости от размера исходных...
Гистогра́мма в математической статистике — это функция, приближающая плотность вероятности некоторого распределения, построенная на основе выборки из него.
Псевдослуча́йная после́довательность (ПСП) — последовательность чисел, которая была вычислена по некоторому определённому арифметическому правилу, но имеет все свойства случайной последовательности чисел в рамках решаемой задачи.
Многочасти́чный фильтр (МЧФ, англ. particle filter — «фильтр частиц», «частичный фильтр», «корпускулярный фильтр») — последовательный метод Монте-Карло — рекурсивный алгоритм для численного решения проблем оценивания (фильтрации, сглаживания), особенно для нелинейных и не-гауссовских случаев. Со времени описания в 1993 году Н. Гордоном, Д. Салмондом и А. Смитом используется в различных областях — навигации, робототехнике, компьютерном зрении.
Многоме́рное норма́льное распределе́ние (или многоме́рное га́уссовское распределе́ние) в теории вероятностей — это обобщение одномерного нормального распределения. Случайный вектор, имеющий многомерное нормальное распределение, называется гауссовским вектором.
Байесовское программирование — это формальная система и методология определения вероятностных моделей и решения задач, когда не вся необходимая информация является доступной.
Сглаживающие операторы — это гладкие функции со специальными свойствами, используемые в теории распределений для построения последовательности гладких функций, приближающей негладкую (обобщённую) функцию с помощью свёртки. Интуитивно, имея функцию с особенностями и осуществляя её свёртку со сглаживающей функцией, получаем «сглаженную функцию», в которой особенности исходной функции сглажены, хотя функция остаётся близкой к исходной функции. Операторы известны также как сглаживающие операторы Фридрихса...
Подробнее: Сглаживающий оператор
Численное решение уравнений и их систем состоит в приближённом определении корней уравнения или системы уравнений и применяется в случаях, когда точный метод решения неизвестен или трудоёмок.
Вычисления с оракулом — вычисление с помощью машины Тьюринга, дополненной оракулом с неизвестным внутренним устройством.
Квантовые методы Монте-Карло — большая семья методов, для исследования сложных квантовых систем. Одна из главных задач — обеспечить надёжное решение (или достаточно точное приближение) квантовой задачи многих тел. Различные варианты этого метода имеют общую особенность: они используют метод Монте-Карло для вычисления многомерных интегралов, возникающих в различных формулировках задачи многих тел. Квантовые методы Монте-Карло позволяют описывать сложные эффекты многих частиц, зашифрованные в волновой...
Вейвлет-преобразование (англ. Wavelet transform) — интегральное преобразование, которое представляет собой свертку вейвлет-функции с сигналом. Вейвлет-преобразование переводит сигнал из временного представления в частотно-временное.
Циклический код — линейный, блочный код, обладающий свойством цикличности, то есть каждая циклическая перестановка кодового слова также является кодовым словом. Используется для преобразования информации для защиты её от ошибок (см. Обнаружение и исправление ошибок).
Фи́льтр Ка́лмана — эффективный рекурсивный фильтр, оценивающий вектор состояния динамической системы, используя ряд неполных и зашумленных измерений. Назван в честь Рудольфа Калмана.
Сверхпроводящая логика — класс логических схем, построенных на основе сверхпроводников и джозефсоновских контактов, и использующих эффект квантования магнитного потока. Отсутствие электрического сопротивления позволяет создавать логические схемы с высоким быстродействием, а последние разработки обладают и высокой энергоэффективностью. Сверхпроводящая логика является вариантом для создания процессоров, с высокой частотой переключения отдельных логических элементов - до сотен ГГц.
Таблица поиска (англ. lookup table) — это структура данных, обычно массив или ассоциативный массив, используемая с целью заменить вычисления на операцию простого поиска. Увеличение скорости может быть значительным, так как получить данные из памяти зачастую быстрее, чем выполнить трудоёмкие вычисления.
Математические основы квантовой механики — принятый в квантовой механике способ математического моделирования квантовомеханических явлений, позволяющий вычислять численные значения наблюдаемых в квантовой механике величин. Были созданы Луи де-Бройлем (открытие волн материи), В. Гейзенбергом (создание матричной механики, открытие принципа неопределённости), Э. Шрёдингером (уравнение Шрёдингера), Н. Бором (формулировка принципа дополнительности). Завершил создание математических основ квантовой механики...
Для определения средних или наиболее типичных значений совокупности используются показатели центра распределения. Основные из них — математическое ожидание, среднее арифметическое, среднее геометрическое, среднее гармоническое, среднее степенное, взвешенные средние, центр сгиба, медиана, мода.
Подробнее: Показатели центра распределения
Темпоральная логика (англ. temporal (от лат. tempus) logic) — это логика, в высказываниях которой учитывается временной аспект. Используется для описания последовательностей явлений и их взаимосвязи по временной шкале.
Элементарный клеточный автомат — это клеточный автомат с одномерным массивом ячеек в форме бесконечной в обе стороны ленты, который имеет два возможных состояния ячеек (0 и 1, «мёртвые» и «живые», «пустые» и «заполненные») и правило для определения состояния ячейки на следующем шаге, использующее только состояние ячейки и её двух соседей на текущем шаге. В целом такие автоматы являются одними из наиболее простых возможных клеточных автоматов, однако при некоторых правилах они показывают сложное поведение...
Секвенциальная логика — это логика памяти цифровых устройств. Название «секвенциальная» восходит к англ. sequential. Соответствующая логика может именоваться также как последовательностная, хотя последний термин по преимуществу употребляется в связи с логическими автоматами.
Компромисс времени и памяти (англ. Space-time trade-off, «выбор оптимального соотношения „место-время“» (англ. space-time trade-off), или, иначе, «выбор оптимального соотношения „время-память“» (англ. time-memory trade-off)) — компромиссный подход к решению ряда задач в информатике, при котором используется обратное соотношение требуемого объёма памяти и скорости выполнения программы: время вычислений может быть увеличено за счёт уменьшения используемой памяти или, наоборот, снижено за счёт увеличения...
Дискретное преобразование Фурье (в англоязычной литературе DFT, Discrete Fourier Transform) — это одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов (его модификации применяются в сжатии звука в MP3, сжатии изображений в JPEG и др.), а также в других областях, связанных с анализом частот в дискретном (к примеру, оцифрованном аналоговом) сигнале. Дискретное преобразование Фурье требует в качестве входа дискретную функцию. Такие функции часто создаются путём дискретизации...
Линейка Голомба в теории чисел — набор неотрицательных целых чисел, расположенных в виде делений на воображаемой линейке таким образом, что расстояние между любыми двумя делениями является уникальным. Другими словами, на всём протяжении линейки нельзя найти два числа, разность между которыми повторялась бы дважды.