Связанные понятия
Комбинаторный взрыв — термин, используемый для описания эффекта резкого («взрывного») роста временной сложности алгоритма при увеличении размера входных данных задачи.
Минимизация эмпирического риска (МЭР, англ. Empirical risk minimization, ERM) — это принцип статистической теории обучения, который определяет семейство алгоритмов обучения и который задаёт теоретические границы производительности.
В комбинаторике последовательность Дэвенпорта — Шинцеля является последовательностью символов, в которой любые два символа могут появиться в чередующемся порядке ограниченное число раз. Максимальная возможная длина последовательности Дэвенпорта — Шинцеля ограничена числом символов, умноженном на небольшой постоянный множитель, который зависит от числа разрешённых чередований. Последовательности Дэвенпорта — Шинцеля были впервые определены в 1965 году Гарольдом Дэвенпортом и Анджеем Шинцелем для анализа...
Рационализируемость (англ. rationalizability) — концепция решения в теории игр. Концепция задумана как набор минимальных ограничений, при которых игроки остаются рациональными и имеет место общее знание о рациональности каждого из участников. Иными словами, имеют место рациональность и общая вера в рациональность. В частности, концепция менее требовательна, чем равновесие Нэша, и совокупность равновесий в игре является подмножеством множества рационализируемых решений. Обе концепции требуют от игроков...
В статистике метод оценки с помощью апостериорного максимума (MAP) тесно связан с методом максимального правдоподобия (ML), но дополнительно при оптимизации использует априорное распределение величины, которую оценивает.
Подробнее: Оценка апостериорного максимума
Алгоритм Джонсона — позволяет найти кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. Данный алгоритм работает, если в графе содержатся рёбра с положительным или отрицательным весом, но отсутствуют циклы с отрицательным весом.
Статистическая мощность в математической статистике — вероятность отклонения основной (или нулевой) гипотезы при проверке статистических гипотез в случае, когда конкурирующая (или альтернативная) гипотеза верна. Чем выше мощность статистического теста, тем меньше вероятность совершить ошибку второго рода. Величина мощности также используется для вычисления размера выборки, необходимой для подтверждения гипотезы с необходимой силой эффекта.
Концепцией
решения (англ. solution concept) в теории игр называют формальное правило, предсказывающее, по какому сценарию пройдёт игра. Если говорить точнее, предсказания касаются стратегий игроков и, следовательно, исхода игры при заданных допущениях. Предсказания называются решениями игры. Наиболее распространены равновесные концепции решения, в том числе равновесие Нэша. Существуют и иные концепции, не являющиеся равновесными. В отличие от равновесных, они не требуют от игроков обоснованных вер...
Модели дискретного выбора — экономические (эконометрические) модели, позволяющие описывать, объяснять и прогнозировать выбор между, двумя или более альтернативами (то есть когда множество альтернатив не более чем счетно). Модели дискретного выбора позволяют на основе некоторых характеристик (атрибутов) экономического субъекта или ситуации оценить вероятность выбора той или иной альтернативы.
Подробнее: Дискретный выбор
Зако́н Амдала (англ. Amdahl's law, иногда также Закон Амдаля-Уэра) — иллюстрирует ограничение роста производительности вычислительной системы с увеличением количества вычислителей. Джин Амдал сформулировал закон в 1967 году, обнаружив простое по существу, но непреодолимое по содержанию ограничение на рост производительности при распараллеливании вычислений: «В случае, когда задача разделяется на несколько частей, суммарное время её выполнения на параллельной системе не может быть меньше времени выполнения...
Алгоритм умножения Бута это алгоритм умножения, который позволяет перемножить два двоичных числа в дополнительном коде. Алгоритм был разработан Эндрю Дональдом Бутом в 1951 при проведении исследований в области кристаллографии в колледже им. Дж. Бирбека в Блумсбери (Лондон). Бут пользовался настольными вычислителями, которые выполняли операцию сдвига быстрее, чем операцию сложения, и создал алгоритм для увеличения скорости их работы. Алгоритм Бута представляет интерес при изучении архитектуры компьютера...
Задача о наибольшем пустом прямоугольнике или задача о максимальном пустом прямоугольнике — это задача поиска прямоугольника максимального размера, который следует разместить среди препятствий на плоскости. Существует несколько вариантов задачи, в зависимости от особенностей формулировки, в частности, от способов измерения «размера», области (типы препятствий) и ориентации прямоугольника.
Деление на ноль в математике — деление, при котором делитель равен нулю. Такое деление может быть формально записано а⁄0, где а — это делимое.
Термостатика — одно из названий классической термодинамики, акцентирующее внимание на том, что эта научная дисциплина представляет собой феноменологическую теорию стационарных состояний и квазистатических процессов в сплошных средах, и в явном виде отражающее современное деление термодинамики на статическую и нестатическую части — равновесную термодинамику и неравновесную термодинамику.
Вектор Шепли — принцип оптимальности распределения выигрыша между игроками в задачах теории кооперативных игр. Представляет собой распределение, в котором выигрыш каждого игрока равен его среднему вкладу в благосостояние тотальной коалиции при определенном механизме её формирования.
Функция предельного правдоподобия (англ. Marginal Likelihood Function) или интегрированное правдоподобие (англ. integrated likelihood) — это функция правдоподобия, в которой некоторые переменные параметры исключены. В контексте байесовской статистики, функция может называться обоснованностью (англ. evidence) или обоснованностью модели (англ. model evidence).
Подробнее: Предельное правдоподобие
Квазиньютоновские методы — методы оптимизации, основанные на накоплении информации о кривизне целевой функции по наблюдениям за изменением градиента, чем принципиально отличаются от ньютоновских методов. Класс квазиньютоновских методов исключает явное формирование матрицы Гессе, заменяя её некоторым приближением.
В теории игр Принцесса и Чудовище — это игра преследования, в которой два игрока играют в некоторой области. Разработана Руфусом Айзексом и опубликована в его книге Дифференциальные игры (1965) в следующем виде: «Монстр ищет принцессу, потраченное на поиск время является ценой игры. Оба находятся в совершенно тёмном помещении (любой формы), но оба знают его границы. Найти принцессу означает, что расстояние между принцессой и монстром оказывается в пределах радиуса захвата, который должен быть относительно...
Теорема Коуза (теорема Коуза — Стиглера) — положение новой институциональной экономики, согласно которому при нулевых трансакционных издержках рынок справляется с любыми внешними эффектами.
Ящик Эджворта — используемая в микроэкономике графическая конструкция, состоящая из двух диаграмм с кривыми безразличия. Впервые описана британским экономистом и философом Фрэнсисом Эджвортом в 1881 году, далее развита в работах Вильфредо Парето и Артура Боули. Ящик Эджворта является одним из инструментов в теории общего равновесия и иногда называется «ящиком обмена благ». Он хорошо пригоден для анализа распределения двух благ между двумя экономическими субъектами в экономике обмена в теории потребителя...
Полуинвариант ы, или семиинварианты, или кумулянты — коэффициенты в разложении логарифма характеристической функции случайной величины в ряд Маклорена.
Перебор делителей (пробное деление) — алгоритм факторизации или тестирования простоты числа путём полного перебора всех возможных потенциальных делителей.
Закон сравнительных суждений - психофизический закон, определяющий отношение между двумя объектами в психическом пространстве человека. Сформулирован Л. Л. Терстоуном.
Двунаправленный поиск пути в ширину (или глубину) — усложнённый алгоритм поиска в ширину (или глубину), идея которого заключается в формировании процесса поиска от начальной (прямой поиск) и от конечной вершины (обратный поиск) графа.
Гипотеза об экспоненциальном времени — это недоказанное допущение о вычислительной сложности, которое сформулировали Импальяццо и Патури. Гипотеза утверждает, что 3-SAT (или любая из связанных NP-полных задач) не может быть решена за субэкспоненциальное время в худшем случае. Из верности гипотезы об экспоненциальном времени, если она верна, следовало бы, что P ≠ NP, но гипотеза является более сильным утверждением. Из утверждения гипотезы можно показать, что многие вычислительные задачи эквиваленты...
Блочный клеточный автомат — класс клеточных автоматов, в которых решётка разбита на блоки, а функция перехода применяется к каждому блоку по отдельности. Блочные клеточные автоматы полезны для моделирования физических явлений, поскольку часто несложно выбрать функции перехода так, чтобы получившийся клеточный автомат был обратим и подчинялся выбранным законам сохранения.
Итерация в программировании — в широком смысле — организация обработки данных, при которой действия повторяются многократно, не приводя при этом к вызовам самих себя (в отличие от рекурсии). В узком смысле — один шаг итерационного, циклического процесса.
Алгоритм Дугласа-Пекера — это алгоритм, позволяющий уменьшить число точек кривой, аппроксимированной большей серией точек. Алгоритм был независимо открыт Урсом Рамером в 1972 и Давидом Дугласом и Томасом Пекером в 1973. Также алгоритм известен под следующими именами: алгоритм Рамера-Дугласа-Пекера, алгоритм итеративной ближайшей точки и алгоритм разбиения и слияния.
Метод простой итерации — один из простейших численных методов решения уравнений. Метод основан на принципе сжимающего отображения, который применительно к численным методам в общем виде также может называться методом простой итерации или методом последовательных приближений. В частности, для систем линейных алгебраических уравнений существует аналогичный метод итерации.
Задача выполнимости формул в теориях (англ. satisfiability modulo theories, SMT) — это задача разрешимости для логических формул с учётом лежащих в их основе теорий. Примерами таких теорий для SMT-формул являются: теории целых и вещественных чисел, теории списков, массивов, битовых векторов и т. п.
Рекурсивное определение или индуктивное определение определяет сущность в терминах её самой (то есть рекурсивно), хотя и полезным способом. Для того, чтобы это было возможно, определение в любом данном случае должно быть хорошо-основанным, избегая бесконечной регрессии.
Закон повторного логарифма — предельный закон теории вероятностей. Теорема определяет порядок роста делителя последовательности сумм случайных величин, при котором эта последовательность не сходится к нулю, но остается почти всюду в конечных пределах.
Граф зависи́мостей — ориентированный граф, отображающий соотношение множества элементов некоторой совокупности в соответствии с выбранным транзитивным отношением над ней.
Неравенство Хёфдинга является частным случаем неравенства Адзума — Хёфдинга и более общим случаем неравенства Бернштейна, доказанного Сергеем Бернштейном в 1923 году. Они также являются частными случаями неравенства МакДиармида.
Лемма о накачке (лемма о разрастании, лемма-насос; англ. pumping lemma) — важное утверждение теории автоматов, позволяющее во многих случаях проверить, является ли данный язык автоматным. Поскольку все конечные языки являются автоматными, эту проверку имеет смысл делать только для бесконечных языков. Термин «накачка» в названии леммы отражает возможность многократного повторения некоторой подстроки в любой строке подходящей длины любого бесконечного автоматного языка.
Эффекти́вная оце́нка в математической статистике — несмещенная статистическая оценка, дисперсия которой совпадает с нижней гранью в неравенстве Крамера-Рао.
Вне́шне несвя́занные уравне́ния (англ. Seemingly Unrelated Regressions (SUR)) — система эконометрических уравнений, каждое из которых является самостоятельным уравнением со своей зависимой и объясняющими экзогенными переменными. Модель предложена Зельнером в 1968 году. Важной особенностью данных уравнений является то, что несмотря на кажущуюся несвязанность уравнений их случайные ошибки предполагаются коррелированными между собой.
Неуверенные данные встречается в области сенсорных сетей; тексты с шумом в изобилии встречаются в социальных сетях, интернете и на предприятиях, где структурированные и неструктурированные данные могут быть старыми, устаревшими или попросту некорректными; в моделировании, когда математическая модель способна быть лишь приближением реального процесса. При представлении таких данных в базе данных, указание вероятностии корректности различных значений также должно быть произведено.
Иерархия вер (англ. belief hierarchy) — объект эпистемической теории игр, позволяющий определить категорию, рациональности и общей веры в рациональность. Под верой понимается вероятностное распределение на неком пространстве неопределённости — например, на множестве стратегий другого игрока (однако элементы пространства могут иметь и экзогенную природу). Концепция иерархии вер введена Мертенсом и Замиром. Иерархию вер можно задать напрямую, либо с помощью дополнительной структуры — типов игроков...
Нумерация Гёделя — это функция g, сопоставляющая каждому объекту некоторого формального языка её номер. С её помощью можно явно пронумеровать следующие объекты языка: переменные, предметные константы, функциональные символы, предикатные символы и формулы, построенные из них. Построение нумерации Гёделя для объектов теории называется арифметизацией теории — оно позволяет переводить высказывания, аксиомы, теоремы, теории в объекты арифметики. При этом требуется, чтобы нумерация g была эффективно вычислимой...
Мартинга́л в теории случайных процессов — такой случайный процесс, что наилучшим (в смысле среднеквадратичного) предсказанием поведения процесса в будущем является его настоящее состояние.
Геометрический решатель (англ. Geometric Constraint Solver), решатель геометрических ограничений, геометрический решатель задач в ограничениях — это программная компонента, которая встраивается в САПР и позволяет инженеру точно позиционировать геометрические элементы друг относительно друга.
Зада́ча Не́ймана , вторая краевая задача — в дифференциальных уравнениях краевая задача с заданными граничными условиями для производной искомой функции на границе области — так называемые граничные условия второго рода. По типу области задачи Неймана можно разделить на два типа: внутренние и внешние. Названа в честь Карла Неймана.
Анализ полных наблюдений (англ. listwise/casewise deletion, реже англ. complete-case analysis) — статистический метод обработки пропущенных данных, основанный на удалении всех наблюдений с неполными признаковыми описаниями. Считается самым простым способом разрешения проблемы пропущенных данных.
Интервальная оце́нка — это пара чисел в математической статистике, оцениваемых на основе наблюдений, между которыми предположительно находится оцениваемый параметр.
Социальная кибернетика (англ. Sociocybernetics) — независимый раздел в социологии, основанный на общей теории систем и кибернетике.