Связанные понятия
Структурная индукция — конструктивный метод математического доказательства, обобщающий математическую индукцию (применяемую над натуральным рядом) на произвольные рекурсивно определённые частично упорядоченные совокупности. Структурная рекурсия — реализация структурной индукции в форме определения, процедуры доказательства или программы, обеспечивающая индукционный переход над частично упорядоченной совокупностью.
Вполне упорядоченное множество — линейно упорядоченное множество M такое, что в любом его непустом подмножестве есть минимальный элемент, другими словами, это фундированное множество с линейным порядком.
Каррирование (от англ. currying, иногда — карринг) — преобразование функции от многих аргументов в набор функций, каждая из которых является функцией от одного аргумента. Возможность такого преобразования впервые отмечена в трудах Готтлоба Фреге, систематически изучена Моисеем Шейнфинкелем в 1920-е годы, а наименование получило по имени Хаскелла Карри — разработчика комбинаторной логики, в которой сведение к функциям одного аргумента носит основополагающий характер.
Ра́венство (отношение равенства) в математике — бинарное отношение, наиболее логически сильная разновидность отношений эквивалентности.
Основная теорема о рекуррентных соотношениях (англ. Master theorem) используется в анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй и властвуй» (divide and conquer), например, при оценке времени их выполнения. Теорема была популяризована в книге Алгоритмы: построение и анализ (Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн), в которой она была введена и доказана.
Упоминания в литературе
Рекурсивные функции – это подкласс вычислимых функций, а алгоритмы, определяющие вычисления, называются сопутствующими алгоритмами рекурсивных функций. Сначала фиксируются базовые рекурсивные функции, для которых сопутствующий алгоритм тривиален, однозначен; затем вводятся три правила – операторы подстановки, рекурсии и минимизации, при помощи которых на основе базовых
функций получаются более сложные рекурсивные функции.
Связанные понятия (продолжение)
Норма́льный алгори́тм (алгори́фм) Ма́ркова (НАМ, также марковский алгоритм) — один из стандартных способов формального определения понятия алгоритма (другой известный способ — машина Тьюринга). Понятие нормального алгоритма введено А. А. Марковым (младшим) в конце 1940-х годов в работах по неразрешимости некоторых проблем теории ассоциативных вычислений. Традиционное написание и произношение слова «алгорифм» в этом термине также восходит к его автору, многие годы читавшему курс математической логики...
Магма (группоид) в общей алгебре — алгебра, состоящая из множества М с одной бинарной операцией M × M → M. Помимо требования замкнутости множества относительно заданной на нём операции, других требований к операции и множеству не предъявляется.
Опера́ция — отображение, ставящее в соответствие одному или нескольким элементам множества (аргументам) другой элемент (значение). Термин «операция» как правило применяется к арифметическим или логическим действиям, в отличие от термина «оператор», который чаще применяется к некоторым отображениям множества на себя, имеющим замечательные свойства.
Переписывание — широкий спектр техник, методов и теоретических результатов, связанных с процедурами последовательной замены частей формул или термов формального языка по заданной схеме — системе переписывающих правил.
Мультииндекс (или мульти-индекс) — обобщение понятия целочисленного индекса до векторного индекса, которое нашло применение в различных областях математики, связанных с функциями многих переменных. Использование мультииндекса помогает упростить (записать более кратко) математические формулы.
Сглаживающие операторы — это гладкие функции со специальными свойствами, используемые в теории распределений для построения последовательности гладких функций, приближающей негладкую (обобщённую) функцию с помощью свёртки. Интуитивно, имея функцию с особенностями и осуществляя её свёртку со сглаживающей функцией, получаем «сглаженную функцию», в которой особенности исходной функции сглажены, хотя функция остаётся близкой к исходной функции. Операторы известны также как сглаживающие операторы Фридрихса...
Подробнее: Сглаживающий оператор
В математике и информатике подстановка — это операция синтаксической замены подтермов данного терма другими термами, согласно определённым правилам. Обычно речь идёт о подстановке терма вместо переменной.
Подробнее: Подстановка
В логике логи́ческими опера́циями называют действия, вследствие которых порождаются новые понятия, с использованием уже существующих. В более узком смысле, понятие логической операции используется в математической логике и программировании.
Подробнее: Логическая операция
Сравне́ние в программировании — общее название ряда операций над па́рами значений одного типа, реализующих математические отношения равенства и порядка. В языках высокого уровня такие операции, чаще всего, возвращают булево значение («истина» или «ложь»).
Равномощность — отношение эквивалентности на множествах ключевое в определении мощности множества.
Логика второго порядка в математической логике — формальная система, расширяющая логику первого порядка возможностью квантификации общности и существования не только над переменными, но и над предикатами. Логика второго порядка несводима к логике первого порядка. В свою очередь, она расширяется логикой высших порядков и теорией типов.
Проблема остановки (или проблема останова) — это одна из центральных проблем в теории алгоритмов, которая может неформально быть поставлена в виде...
Тип-сумма (англ. sum type; также Σ-тип, меченое объединение) — конструкция в языках программирования и интуиционистской теории типов, тип данных, построенный как дизъюнктное объединение исходных типов.
Алгоритмическая разрешимость — свойство формальной теории обладать алгоритмом, определяющим по данной формуле, выводима она из множества аксиом данной теории или нет. Теория называется разрешимой, если такой алгоритм существует, и неразрешимой, в противном случае. Вопрос о выводимости в формальной теории является частным, но вместе с тем важнейшим случаем более общей проблемы разрешимости.
Бесконечная группа — группа с бесконечным числом элементов, в противоположность конечным группам.
Точное нахождение первообразной (или интеграла) произвольных функций — процедура более сложная, чем «дифференцирование», то есть нахождение производной. Зачастую, выразить интеграл в элементарных функциях невозможно.
Подробнее: Методы интегрирования
Полукольцо — общеалгебраическая структура, похожая на кольцо, но без требования существования противоположного по сложению элемента.
Логика Хоара (англ. Hoare logic, также Floyd—Hoare logic, или Hoare rules) — формальная система с набором логических правил, предназначенных для доказательства корректности компьютерных программ. Была предложена в 1969 году английским учёным в области информатики и математической логики Хоаром, позже развита самим Хоаром и другими исследователями. Первоначальная идея была предложена в работе Флойда, который опубликовал похожую систему в применении к блок-схемам (англ. flowchart).
В математике и теоретической физике функциональная производная является обобщением производной по направлению. Разница заключается в том, что для последней дифференцирование производится в направлении какого-нибудь вектора, а для первой речь идёт о функции. Оба эти понятия можно рассматривать как обобщение обычного дифференциального исчисления.
Подробнее: Функциональная производная
Тип-произведение (также Π-тип, произведение типов; англ. product type) — конструкция в языках программирования и интуиционистской теории типов, тип данных, построенный как декартово произведение исходных типов; другими словами — кортеж типов, или «кортеж как тип». Использованные типы и порядок их следования определяют сигнатуру типа-произведения; порядок следования объектов в создаваемом кортеже сохраняется на протяжении его времени жизни согласно заданной сигнатуре.
Интервальная арифметика — математическая структура, которая для вещественных интервалов определяет операции, аналогичные обычным арифметическим. Эту область математики называют также интервальным анализом или интервальными вычислениями. Данная математическая модель удобна для исследования различных прикладных объектов...
Строковое ядро — это ядерная функция, определённая на строках, т.е. конечных последовательностях символов, которые не обязательно имеют одну и ту же длину. Строковые ядра можно интуитивно понимать как функции, измеряющие похожесть пар строк — чем больше похожи две строки a и b, тем больше значение строкового ядра K(a, b).
Многозна́чная ло́гика — тип формальной логики, в которой допускается более двух истинностных значений для высказываний. Первую систему многозначной логики предложил польский философ Ян Лукасевич в 1920 году. В настоящее время существует очень много других систем многозначной логики, которые в свою очередь могут быть сгруппированы по классам. Важнейшими из таких классов являются частичные логики и нечёткие логики.
Интегра́л Пуассо́на — общее название математических формул, выражающих решение краевой задачи или начальной задачи для уравнений с частными производными некоторых типов.
Многоме́рное норма́льное распределе́ние (или многоме́рное га́уссовское распределе́ние) в теории вероятностей — это обобщение одномерного нормального распределения. Случайный вектор, имеющий многомерное нормальное распределение, называется гауссовским вектором.
Отноше́ние — математическая структура, которая формально определяет свойства различных объектов и их взаимосвязи. Распространёнными примерами отношений в математике являются равенство (=), делимость, подобие, параллельность и многие другие.
Мультимножество в математике — обобщение понятия множества, допускающее включение одного и того же элемента по нескольку раз. Число элементов в мультимножестве, с учётом повторяющихся элементов, называется его размером или мощностью.
Конъюнкти́вная норма́льная фо́рма (КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов. Конъюнктивная нормальная форма удобна для автоматического доказательства теорем. Любая булева формула может быть приведена к КНФ. Для этого можно использовать: закон двойного отрицания, закон де Моргана, дистрибутивность.
Преде́льная то́чка множества в общей топологии — это такая точка, любая проколотая окрестность которой пересекается с этим множеством.
Байесовское программирование — это формальная система и методология определения вероятностных моделей и решения задач, когда не вся необходимая информация является доступной.
Переме́нная — атрибут физической или абстрактной системы, который может изменять своё, как правило численное, значение. Понятие переменной широко используется в таких областях как математика, естественные науки, техника и программирование. Примерами переменных могут служить: температура воздуха, параметр функции и многое другое.
Теория комбинаторных схем — это часть комбинаторики (раздела математики), рассматривающая существование, построение и свойства семейств конечных множеств, структура которых удовлетворяет обобщённым концепциям равновесия и/или симметрии. Эти концепции не определены точно, так что объекты широкого диапазона могут пониматься как комбинаторные схемы. Так, в одном случае комбинаторные схемы могут представлять собой пересечения множеств чисел, как в блок-схемах, а в другом случае могут отражать расположение...
Подробнее: Комбинаторная схема
Упорядоченное поле — алгебраическое поле, для всех элементов которого определён линейный порядок, согласованный с операциями поля. Наиболее практически важными примерами являются поля рациональных и вещественных чисел.
Те́зис Чёрча — Тью́ринга — это гипотеза, постулирующая эквивалентность между интуитивным понятием алгоритмической вычислимости и строго формализованными понятиями частично рекурсивной функции и функции, вычислимой на машине Тьюринга. В связи с интуитивностью исходного понятия алгоритмической вычислимости, данный тезис носит характер суждения об этом понятии и его невозможно строго доказать или опровергнуть. Перед точным определением вычислимой функции математики часто использовали неофициальный термин...
Прострáнством называется математическое множество, имеющее структуру, определяемую аксиоматикой свойств его элементов (например, точек в геометрии, векторов в линейной алгебре, событий в теории вероятностей и так далее).Подмножество пространства называется «подпространством», если структура пространства индуцирует на этом подмножестве структуру такого же типа (точное определение зависит от типа пространства).
Подробнее: Пространство (математика)
Математи́ческая структу́ра — название, объединяющее понятия, общей чертой которых является их применимость к множествам, природа которых не определена. Для определения самой структуры задают отношения, в которых находятся элементы этих множеств. Затем постулируют, что данные отношения удовлетворяют неким условиям, которые являются аксиомами рассматриваемой структуры.
Усло́вное распределе́ние в теории вероятностей — это распределение случайной величины при условии, что другая случайная величина принимает определённое значение.