Связанные понятия
Принцип Дирихле нередко применяется при доказательстве теорем, особенно в дискретной математике; в частности, в теории диофантовых приближений при анализе систем линейных неравенств.
Говорят, что возникло
математическое совпадение , если два выражения дают почти одинаковые значения, хотя теоретически это совпадение никак объяснить нельзя.
Контактное число (иногда число Ньютона, в химии соответствует координационному числу) — максимальное количество шаров единичного радиуса, которые могут одновременно касаться одного такого же шара в n-мерном евклидовом пространстве (предполагается, что шары не проникают друг в друга, то есть объём пересечения любых двух шаров равен нулю).
Гипо́теза Коллатца (гипо́теза 3n+1, сираку́зская пробле́ма) — одна из нерешённых проблем математики.
Вероятностный метод — неконструктивный метод доказательства существования математического объекта с заданными свойствами. В основном используется в комбинаторике, но также и в теории чисел, линейной алгебре и математическом анализе, а также в информатике (например, метод вероятностного округления) и теории информации.
Теорема об уголках — доказанный результат в области аддитивной комбинаторики, утверждающий присутствие некой упорядоченной (в арифметическом смысле) структуры, называемой уголком, в достаточно больших двумерных множествах любой фиксированной плотности.
Задача о самом широком пути — это задача нахождения пути между двумя выбранными вершинами во взвешенном графе, максимизирующего вес минимального по весу ребра графа (если рассматривать вес ребра как ширину дороги, то задача стоит в выборе самой широкой дороги, связывающей две вершины). Задача о самом широком пути известна также как задача об узком месте или задача о пути с максимальной пропускной способностью. Можно приспособить алгоритмы кратчайшего пути для вычисления пропускной способности путём...
Задача о разорении игрока — задача из области теории вероятностей. Подробно рассматривалась российским математиком А. Н. Ширяевым в монографии «Вероятность».
Задача о змее в коробке в теории графов и информатике имеет дело с поиском определённого вида пути вдоль рёбер гиперкуба. Этот путь начинается с одного угла и проходит вдоль рёбер столько углов, сколько он может достичь. После того как достигается новый угол, предыдущий угол и все его соседи делаются недопустимыми для использования. Путь никогда не должен проходить через угол после того, как он помечен как недопустимый.
Задача Нелсона — Эрдёша — Хадвигера — задача комбинаторной геометрии, первоначально поставленная как задача о раскраске или хроматическом числе евклидова пространства.
Задача коммивояжёра (англ. Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что...
Демпстера-Шафера теория — математическая теория очевидностей (свидетельств) (), основанная на функции доверия (belief functions) и функции правдоподобия (plausible reasoning), которые используются, чтобы скомбинировать отдельные части информации (свидетельства) для вычисления вероятности события. Теория была развита Артуром П. Демпстером и Гленном Шафером.
Сюрреальные числа (англ. surreal number — название принадлежит американскому математику Дональду Кнуту) впервые были использованы под другим названием («числа» — англ. number) в работах английского математика Джона Конвея для описания ряда аспектов теории игр.
Матема́тика ку́бика Ру́бика — совокупность математических методов для изучения свойств кубика Рубика с абстрактно-математической точки зрения. Эта математика изучает алгоритмы сборки кубика и оценивает их. Основана на теории графов, теории групп, теории вычислимости и комбинаторике.
n-ое
число такси , обычно обозначаемое Ta(n) или Taxicab(n), определяется как наименьшее число, которое может быть представлено как сумма двух положительных кубов n различными способами. Наиболее известное число такси — 1729 = Ta(2) = 13 + 123 = 93 + 103.
Обнаружение столкновений (англ. Collision detection) — вычислительная проблема обнаружения пересечений между собой двух или больше объектов. Тема чаще всего связана с её использованием в физических движках, компьютерной анимации и робототехнике. В дополнение к определению, столкнулись ли два объекта, системы обнаружения столкновений могут вычислить время воздействия и сообщить о коллекторе контакта (набор пересечения точек). Ответ на столкновение (что происходит, когда столкновение обнаружено) зависит...
В математике методы проверки на простоту с помощью эллиптических кривых (англ. - Elliptic Curve Primality Proving, сокр. ЕСРР) являются одними из самых быстрых и наиболее широко используемых методов проверки на простоту . Эту идею выдвинули Шафи Гольдвассер и Джо Килиан в 1986 году; она была превращена в алгоритм А.О.Л. Аткином в том же году. Впоследствии алгоритм был несколько раз изменён и улучшен, в особенности Аткином и François Morain в 1993. Концепция использования факторизации с помощью эллиптических...
Подробнее: Тест простоты с использованием эллиптических кривых
Закон больших чисел (ЗБЧ) в теории вероятностей — принцип, описывающий результат выполнения одного и того же эксперимента много раз. Согласно закону, среднее значение конечной выборки из фиксированного распределения близко к математическому ожиданию этого распределения.
Ме́трика Шва́рцшильда — это единственное в силу теоремы Биркхофа сферически симметричное точное решение уравнений Эйнштейна без космологической константы в пустом пространстве. В частности, эта метрика достаточно точно описывает гравитационное поле уединённой невращающейся и незаряженной чёрной дыры и гравитационное поле снаружи от уединённого сферически симметричного массивного тела. Названа в честь Карла Шварцшильда, который первым её обнаружил в 1916 году.
Простра́нство-вре́мя (простра́нственно-временно́й конти́нуум) — физическая модель, дополняющая пространство равноправным временны́м измерением и таким образом создающая теоретико-физическую конструкцию, которая называется пространственно-временным континуумом. Пространство-время непрерывно и с математической точки зрения представляет собой многообразие с лоренцевой метрикой.
Теорема Бека — это один из нескольких результатов комбинаторной геометрии, два из которых приведены ниже.
Голигон — это любой многоугольник, в котором все углы прямые, а длины сторон являются последовательными целыми числами (от 1 до n). Голигоны придумал (и дал им название) Ли Сэллоус, а популяризовал Александр Дьюдени в колонке 1990 года в журнале Scientific American . Вариации определения голигонов позволяют сторонам пересекаться, иметь в качестве длин сторон любые целые числа (не обязательно последовательные) и иметь углы, отличные от 90°.
Теория Рамсея — раздел математики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок. Названа в честь Фрэнка Рамсея.
Алгоритм Гилберта — Джонсона — Кёрти (англ. Gilbert — Johnson — Keerthi algorithm, сокращённо GJK) — алгоритм для определения минимального расстояния между двумя выпуклыми множествами (объектами). В отличие от многих других алгоритмов нахождения расстояния, GJK не требует, чтобы геометрические данные были сохранены в каком-либо специфическом формате. Вместо этого алгоритм GJK полностью полагается на носитель функции и итерационным методом (с помощью итераций) генерирует ближайшие симплексы для корректного...
Метод шаров и перегородок (англ. stars and bars — букв. «звёздочки и чёрточки») — это графический метод для вывода некоторых комбинаторных теорем. Метод популяризировал Уильям Феллер в его классической книге по теории вероятностей. Метод может быть использован для решения многих простых задач подсчёта, таких как «сколькими способами можно разложить n неразличимых шаров по k различимым ящикам».
Трансвычисли́тельная зада́ча (англ. Transcomputational problem) — в теории сложности вычислений задача, для решения которой требуется обработка более чем 1093 бит информации. Число 1093, называемое «пределом Бремерманна», согласно Гансу-Иоахиму Бремерманну, представляет собой общее число бит, обрабатываемых гипотетическим компьютером размером с Землю, работающим с максимально возможной скоростью, за период времени, равный общему времени существования Земли. Термин «трансвычислительность» был предложен...
Парадо́кс Бе́лла — один из известных релятивистских парадоксов специальной теории относительности. В наиболее известном варианте самого Джона Стюарта Белла парадокс возникает при рассмотрении мысленного эксперимента, включающего в себя два ускоряющихся в одном и том же направлении космических корабля и соединяющую их натянутую до предела струну (один корабль летит строго впереди другого, т. е. ускорение направлено вдоль струны). Если корабли начнут синхронно ускоряться, то в сопутствующей кораблям...
Алгоритм Брезенхе́ма (англ. Bresenham's line algorithm) — это алгоритм, определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками. Это один из старейших алгоритмов в машинной графике — он был разработан Джеком Элтоном Брезенхэмом (англ. Jack Elton Bresenham) в компании IBM в 1962 году. Алгоритм широко используется, в частности, для рисования линий на экране компьютера. Существует обобщение алгоритма Брезенхэма для построения...
Гипотеза Хивуда , или теорема Рингеля — Янгса даёт нижнюю границу для числа цветов, которые необходимы для раскраски графа на поверхности с заданным родом. Эта граница называется хроматическим числом поверхности или числом Хивуда. Для поверхностей рода 0, 1, 2, 3, 4, 5, 6, 7, ..., требуемое число цветов равно 4, 7, 8, 9, 10, 11, 12, 12, ....
Двенадцатикратный путь или двенадцать сценариев — это систематическая классификация 12 связанных перечислительных задач, касающихся двух конечных множеств, которые включают классические задачи подсчёта перестановок, сочетаний, мультимножеств и разбиений либо множества, либо числа. Идею классификации приписывают Джиану-Карло Роту, а название двенадцатикратный путь предложил Джоэл Спенсер. Название намекает, что используя те же подходы в 12 случаях, но с небольшими изменениями в условиях, мы получаем...
Рациональное решето — это алгоритм общего вида для разложения целых чисел на простые множители. Алгоритм является частным случаем общего метода решета числового поля. Хотя он менее эффективен, чем общий алгоритм, концептуально он проще. Алгоритм может помочь понять, как работает общий метод решета числового поля.
Парадо́кс дней рожде́ния . В группе, состоящей из 23 или более человек, вероятность совпадения дней рождения (число и месяц) хотя бы у двух людей превышает 50 %. Например, если в классе 23 ученика или более, то более вероятно то, что у кого-то из одноклассников дни рождения придутся на один день, чем то, что у каждого будет свой неповторимый день рождения.
Теорема о четырёх красках — теорема, которая утверждает, что всякую расположенную на сфере карту можно раскрасить не более чем четырьмя разными цветами (красками) так, чтобы любые две области с общим участком границы были раскрашены в разные цвета. При этом области могут быть как односвязными, так и многосвязными (в них могут присутствовать «дырки»), а под общим участком границы понимается часть линии, то есть стыки нескольких областей в одной точке не считаются общей границей для них. Задача раскраски...
У́стный счёт — математические вычисления, осуществляемые человеком без помощи дополнительных устройств (компьютер, калькулятор, счёты и т. п.) и приспособлений (ручка, карандаш, бумага и т. п.).
Метод неделимых — возникшее в конце XVI века наименование совокупности приёмов, предназначенных для вычисления площадей геометрических фигур или объёмов геометрических тел.
Бесконечно малая — числовая функция или последовательность, которая стремится к нулю.
Задача о покрытии множества является классическим вопросом информатики и теории сложности. Данная задача обобщает NP-полную задачу о вершинном покрытии (и потому является NP-сложной). Несмотря на то, что задача о вершинном покрытии сходна с данной, подход, использованный в приближённом алгоритме, здесь не работает. Вместо этого мы рассмотрим жадный алгоритм. Даваемое им решение будет хуже оптимального в логарифмическое число раз. С ростом размера задачи качество решения ухудшается, но всё же довольно...
Геометрический остов (англ. geometric spanner) или t-остовной граф, или t-остов первоначально был введён как взвешенный граф на множестве точек в качестве вершин, для которого существует t-путь между любой парой вершин для фиксированного параметра t. t-Путь определяется как путь в графе с весом, не превосходящим в t раз пространственное расстояние между конечными точками. Параметр t называется коэффициентом растяжения остова.
«»В компьютерной науке, точнее, в теории детерминированных конечных автоматов (ДКА), синхронизирующее слово (или сжимающая последовательность) во входном алфавите автомата отображает все его состояния в одно и то же состояние. То есть, если слово стартует на ансамбле всех состояний автомата, проходя все ориентированные дуги с одинаковой скоростью, все пути завершатся одновременно в одном и том же состоянии. Не у каждого ДКА есть синхронизирующее слово, например, ДКА с двумя состояниями и циклами...
Подробнее: Синхронизируемое слово
В комбинаторной математике под числом встреч понимается число перестановок множества {1, ..., n} с заданным числом неподвижных элементов.
Подробнее: Число встреч (комбинаторика)
В теории графов
укрытие — это определённый тип функции на множествах вершин неориентированного графа. Если укрытие существует, его может использовать беглец, чтобы выиграть игру преследование-уклонение на графе путём использования этой функции на каждом шаге игры для определения безопасных множеств вершин, куда можно перейти. Укрытия были впервые введены Сеймуром и Томасом как средство характеризации древесной ширины графов. Другие приложения этого понятия — доказательство существования малых сепараторов...
История теории вероятностей отмечена многими уникальными особенностями. Прежде всего, в отличие от появившихся примерно в то же время других разделов математики (например, математического анализа или аналитической геометрии), у теории вероятностей по существу не было античных или средневековых предшественников, она целиком — создание Нового времени. Долгое время теория вероятностей считалась чисто опытной наукой и «не совсем математикой», её строгое обоснование было разработано только в 1929 году...
Скрытая марковская модель (СММ) — статистическая модель, имитирующая работу процесса, похожего на марковский процесс с неизвестными параметрами, и задачей ставится разгадывание неизвестных параметров на основе наблюдаемых. Полученные параметры могут быть использованы в дальнейшем анализе, например, для распознавания образов. СММ может быть рассмотрена как простейшая байесовская сеть доверия.
Задача Бёрнсайда — серия задач в теории групп вокруг вопроса о возможности определить конечность группы исходя лишь из свойств её элементов: должна ли быть конечно порождённая группа, в которой каждый элемент имеет конечный порядок, обязательно конечной.
В комбинаторной оптимизации под линейной задачей о назначениях на узкие места (linear bottleneck assignment problem, LBAP) понимается задача, похожая на задачу о назначениях.
Подробнее: Линейная задача о назначениях в узких местах
Парадокс береговой линии — противоречивое наблюдение в географических науках, связанное с невозможностью точно определить длину линии побережья из-за её фракталоподобных свойств. Первое задокументированное описание данного феномена было сделано Льюисом Ричардсоном; впоследствии оно было расширено Бенуа Мандельбротом.
В теории графов
паросочетание или независимое множество рёбер в графе — это набор попарно несмежных рёбер.