Связанные понятия
Лемма о накачке (лемма о разрастании, лемма-насос; англ. pumping lemma) — важное утверждение теории автоматов, позволяющее во многих случаях проверить, является ли данный язык автоматным. Поскольку все конечные языки являются автоматными, эту проверку имеет смысл делать только для бесконечных языков. Термин «накачка» в названии леммы отражает возможность многократного повторения некоторой подстроки в любой строке подходящей длины любого бесконечного автоматного языка.
Омега-язык (ω-язык) — это множество бесконечно длинных последовательностей символов.
Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются одиночными нетерминалами (объектами, обозначающими какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющими конкретного символьного значения). Смысл термина «контекстно-свободная» заключается в том, что есть возможность применить продукцию к нетерминалу, причём независимо...
Теория Рамсея — раздел математики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок. Названа в честь Фрэнка Рамсея.
Двенадцатикратный путь или двенадцать сценариев — это систематическая классификация 12 связанных перечислительных задач, касающихся двух конечных множеств, которые включают классические задачи подсчёта перестановок, сочетаний, мультимножеств и разбиений либо множества, либо числа. Идею классификации приписывают Джиану-Карло Роту, а название двенадцатикратный путь предложил Джоэл Спенсер. Название намекает, что используя те же подходы в 12 случаях, но с небольшими изменениями в условиях, мы получаем...
Сюрреальные числа (англ. surreal number — название принадлежит американскому математику Дональду Кнуту) впервые были использованы под другим названием («числа» — англ. number) в работах английского математика Джона Конвея для описания ряда аспектов теории игр.
Теорема Курселя — утверждение о том, что любое свойство графа, определяемое в логике графов второго порядка, может быть установлено за линейное время на графах с ограниченной древесной шириной. Результат впервые доказан Брюно Курселем в 1990 году и независимо переоткрыт Бори, Паркером и Товейем.
Теорема об уголках — доказанный результат в области аддитивной комбинаторики, утверждающий присутствие некой упорядоченной (в арифметическом смысле) структуры, называемой уголком, в достаточно больших двумерных множествах любой фиксированной плотности.
Неконструктивное доказательство (неэффективное доказательство) — класс математических доказательств, доказывающих лишь существование в заданном (как правило, бесконечном) множестве элемента, удовлетворяющего заданным свойствам, но не дающее никакой информации о других свойствах элемента, то есть не позволяющие ни предъявить его, ни приблизительно описать. Доказательства, которые доказывают существование элемента, предъявляя способ получения этого элемента, называются конструктивными.
При конструктивном подходе к определению вещественного числа вещественные числа строят, исходя из рациональных, которые считают заданными. Во всех трёх нижеизложенных способах за основу берутся рациональные числа и конструируются новые объекты, называемые иррациональными числами. В результате пополнения ими множества рациональных чисел, мы получаем множество вещественных чисел.
Подробнее: Конструктивные способы определения вещественного числа
В теоретической информатике, точнее, в теории формальных языков, высота итерации — это мера структурной сложности регулярных выражений — высота итерации регулярного выражения равна максимальной глубине вложенности звёздочек, присутствующих в регулярном выражении.
Подробнее: Высота итерации языка
Четыре четверки — математическая головоломка по поиску простейшего математического выражения для каждого целого числа от 0 до некоторого максимума, используя лишь общие математические символы и четвёрки (никакие другие цифры не допускаются). Большинство версий «четырёх четверок» требует, чтобы каждое выражение содержало ровно четыре четверки, но некоторые вариации требуют, чтобы каждое выражение имело минимальное количество четверок.
Рациональное решето — это алгоритм общего вида для разложения целых чисел на простые множители. Алгоритм является частным случаем общего метода решета числового поля. Хотя он менее эффективен, чем общий алгоритм, концептуально он проще. Алгоритм может помочь понять, как работает общий метод решета числового поля.
Лемма регулярности Семереди — лемма из общей теории графов, утверждающая, что вершины любого достаточно большого графа можно разбить на конечное число групп таких, что почти во всех двудольных графах, соединяющих вершины из двух разных групп, рёбра распределены между вершинами почти равномерно. При этом минимальное требуемое количество групп, на которые нужно разбить множество вершин графа, может быть сколь угодно большим, но количество групп в разбиении всегда ограничено сверху.
В математике методы проверки на простоту с помощью эллиптических кривых (англ. - Elliptic Curve Primality Proving, сокр. ЕСРР) являются одними из самых быстрых и наиболее широко используемых методов проверки на простоту . Эту идею выдвинули Шафи Гольдвассер и Джо Килиан в 1986 году; она была превращена в алгоритм А.О.Л. Аткином в том же году. Впоследствии алгоритм был несколько раз изменён и улучшен, в особенности Аткином и François Morain в 1993. Концепция использования факторизации с помощью эллиптических...
Подробнее: Тест простоты с использованием эллиптических кривых
Группа Григорчука — первый пример конечнопорождённой группы промежуточного роста (то есть её рост быстрее полиномиального, но медленнее экспоненциального).
Принцип Дирихле нередко применяется при доказательстве теорем, особенно в дискретной математике; в частности, в теории диофантовых приближений при анализе систем линейных неравенств.
Индуктивное логическое программирование (Inductive Logic Programming, ILP) — раздел машинного обучения, который использует логическое программирование как форму представления примеров, фоновых знаний и гипотез. Получив описания уже известных фоновых знаний и набор примеров, представленных как логическая база фактов, система ILP может породить логическую программу в форме гипотез, объясняющую все положительные примеры и ни одного отрицательного.
Гипотеза об экспоненциальном времени — это недоказанное допущение о вычислительной сложности, которое сформулировали Импальяццо и Патури. Гипотеза утверждает, что 3-SAT (или любая из связанных NP-полных задач) не может быть решена за субэкспоненциальное время в худшем случае. Из верности гипотезы об экспоненциальном времени, если она верна, следовало бы, что P ≠ NP, но гипотеза является более сильным утверждением. Из утверждения гипотезы можно показать, что многие вычислительные задачи эквиваленты...
«Тогда́ и то́лько тогда ́» — логическая связка эквиваленции между утверждениями, применяемая в логике, математике, философии. Чтобы быть эквиваленцией, связка должна быть идентична стандартному материальному условному высказыванию («только тогда» эквивалентно «если … то»), соединённому со своей противоположностью, откуда и название связки. В результате истинность одного утверждения требует такой же истинности другого, то есть либо оба они истинны, либо оба ложны. Можно спорить о том, передаёт ли выражение...
Арифме́тика (др.-греч. ἀριθμητική (árithmitikí) — от ἀριθμός (árithmós) «число») — раздел математики, изучающий числа, их отношения и свойства. Предметом арифметики является понятие числа (натуральные, целые, рациональные, вещественные, комплексные числа) и его свойства. В арифметике рассматриваются измерения, вычислительные операции (сложение, вычитание, умножение, деление) и приёмы вычислений. Изучением свойств отдельных целых чисел занимается высшая арифметика, или теория чисел. Теоретическая...
Бесконечно малая — числовая функция или последовательность, которая стремится к нулю.
Гипотеза Хивуда , или теорема Рингеля — Янгса даёт нижнюю границу для числа цветов, которые необходимы для раскраски графа на поверхности с заданным родом. Эта граница называется хроматическим числом поверхности или числом Хивуда. Для поверхностей рода 0, 1, 2, 3, 4, 5, 6, 7, ..., требуемое число цветов равно 4, 7, 8, 9, 10, 11, 12, 12, ....
Теорема Рамсея — теорема комбинаторики о разбиениях множеств, сформулированная и доказанная английским математиком Фрэнком Рамсеем в 1930 году. Встречается в литературе в разных формулировках. Эта теорема положила начало теории Рамсея.
В комбинаторике,
Числа Нараяны N(n, k), n = 1, 2, 3 ..., 1 ≤ k ≤ n, формируют треугольную матрицу натуральных чисел, называемую Треугольником Нараяны, который всплывает во многих задачах перечислительной комбинаторики. Названы в честь индийского математика Т. В. Нараяны (1930–1987).
Порядок Шарковского — упорядочение натуральных чисел, связанное с исследованием периодических точек динамических систем на отрезке или на вещественной прямой.
Ошибка на единицу или ошибка неучтённой единицы (англ. off-by-one error) — логическая ошибка в алгоритме, включающая в частности дискретный вариант нарушения граничных условий.
Вероятностный метод — неконструктивный метод доказательства существования математического объекта с заданными свойствами. В основном используется в комбинаторике, но также и в теории чисел, линейной алгебре и математическом анализе, а также в информатике (например, метод вероятностного округления) и теории информации.
РЕФАЛ (РЕкурсивных Функций АЛгоритмический) — один из старейших функциональных языков программирования, ориентированный на символьные вычисления: обработку символьных строк (например, алгебраические выкладки); перевод с одного языка (искусственного или естественного) на другой; решение проблем, связанных с искусственным интеллектом. Соединяет в себе математическую простоту с практической направленностью на написание больших и сложных программ.
История арифметики охватывает период от возникновения счёта до формального определения чисел и арифметических операций над ними с помощью системы аксиом. Арифметика — наука о числах, их свойствах и отношениях — является одной из основных математических наук. Она тесно связана с алгеброй и теорией чисел.
Принцип минимальной длины описания (англ. minimum description length, MDL) — это формализация бритвы Оккама, в которой лучшая гипотеза (модель и её параметры) для данного набора данных это та, которая ведёт к лучшему сжиманию даных. Принцип MDL предложил Йорма Риссанен в 1978. Принцип является важной концепцией в теории информации и теории вычислительного обучения.
Суффиксное дерево — бор, содержащий все суффиксы некоторой строки (и только их). Позволяет выяснять, входит ли строка w в исходную строку t, за время O( w ), где w — длина строки w.
Число ́ — основное понятие математики, используемое для количественной характеристики, сравнения, нумерации объектов и их частей. Письменными знаками для обозначения чисел служат цифры, а также символы математических операций. Возникнув ещё в первобытном обществе из потребностей счёта, понятие числа с развитием науки значительно расширилось.
В теории информации
теорема Шеннона об источнике шифрования (или теорема бесшумного шифрования) устанавливает предел максимального сжатия данных и числовое значение энтропии Шеннона.
Теорема Сарда — одна из теорем математического анализа, имеющих важные приложения в теории катастроф и теории динамических систем.Названа в честь американского математика Артура Сарда.
В теории графов медианным графом называется неориентированный граф, в котором любые три вершины a, b, и c имеют единственную медиану — вершину m(a,b,c), которая принадлежит кратчайшим путям между каждой парой вершин a, b и c.
Подробнее: Медианный граф
Мно́жество — одно из ключевых понятий математики; это математический объект, сам являющийся набором, совокупностью, собранием каких-либо объектов, которые называются элементами этого множества и обладают общим для всех их характеристическим свойством. Изучением общих свойств множеств занимаются теория множеств, а также смежные разделы математики и математической логики.
Языком
Дика (англ. Dyck language) над 2n буквами называется контекстно-свободный язык над алфавитом...
Задача коммивояжёра (англ. Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что...
Вероя́тностное простра́нство — понятие, введённое А. Н. Колмогоровым в 30-х годах XX века для формализации понятия вероятности, которое дало начало бурному развитию теории вероятностей как строгой математической дисциплины.
Множество больших тригонометрических сумм — понятие теории чисел — множество индексов, в которых преобразование Фурье характеристической функции заданного подмножества группы принимает достаточно большие значения.
Папирус Ахмеса был обнаружен в 1858 году в Фивах и часто называется папирусом Ринда (Райнда) по имени его первого владельца.
Логическая вероятность — логическое отношение между двумя предложениями, степень подтверждения гипотезы H свидетельством E.
Длинная арифметика — выполняемые с помощью вычислительной машины арифметические операции (сложение, вычитание, умножение, деление, возведение в степень, элементарные функции) над числами, разрядность которых превышает длину машинного слова данной вычислительной машины. Эти операции реализуются не аппаратно, а программно, с использованием базовых аппаратных средств работы с числами меньших порядков. Частный случай — арифметика произвольной точности — относится к арифметике, в которой длина чисел ограничена...
Сжатие звука без потерь — совокупность преобразований, позволяющая эффективно сжимать звуковые данные с возможностью их полного восстановления. Как и любое сжатие без потерь, сжатие звуковых данных эксплуатирует какую-либо особенность данных. В данном случае это...
Говорят, что возникло
математическое совпадение , если два выражения дают почти одинаковые значения, хотя теоретически это совпадение никак объяснить нельзя.