Комбинато́рика — раздел математики, посвящённый решению задач, связанных с выбором и расположением элементов некоторого множества в соответствии с заданными правилами. Каждое такое правило определяет некоторую выборку из элементов исходного множества, которая называется комбинаторной конфигурацией. Простейшими примерами комбинаторных конфигураций являются перестановки, сочетания и размещения.
Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:
- как и геометрия, обладает наглядностью;
- как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
- не имеет громоздкого математического аппарата ;
- имеет выраженный прикладной характер.
Реляционная алгебра — замкнутая система операций над отношениями в реляционной модели данных. Операции реляционной алгебры также называют реляционными операциями.
Общее знание имеет место в ситуации, когда каждому индивиду из некоторой группы известно о наступлении некого события, о наличии этого знания у других представителей группы, о наличии знания о наличии знания и так далее ad infinitum. Концепция общего знания впервые возникла в философской литературе у Дэвида Келлогга Льюиса (1969). Определение общего знания было дано тогда же социологом Моррисом Фриделлом. Математическая (теоретико-множественная) интерпретация осуществлена в 1976 году Робертом Ауманном, который занимался построением эпистемической теории игр. С 1980-х годов концепцией заинтересовались исследователи в области информатики. Общее знание лежит в основе многих логических головоломок, изучением который, в частности, занимался Джон Хортон Конвей.
Кластерный анализ — многомерная статистическая процедура, выполняющая сбор данных, содержащих информацию о выборке объектов, и затем упорядочивающая объекты в сравнительно однородные группы. Задача кластеризации относится к статистической обработке, а также к широкому классу задач обучения без учителя.
Дерево принятия решений — средство поддержки принятия решений, использующееся в машинном обучении, анализе данных и статистике. Структура дерева представляет собой «листья» и «ветки». На рёбрах («ветках») дерева решения записаны признаки, от которых зависит целевая функция, в «листьях» записаны значения целевой функции, а в остальных узлах — признаки, по которым различаются случаи. Чтобы классифицировать новый случай, надо спуститься по дереву до листа и выдать соответствующее значение.
Диаграмма Вороного конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу множества.
Обнаружение столкновений — вычислительная проблема обнаружения пересечений между собой двух или больше объектов. Тема чаще всего связана с её использованием в физических движках, компьютерной анимации и робототехнике. В дополнение к определению, столкнулись ли два объекта, системы обнаружения столкновений могут вычислить время воздействия и сообщить о коллекторе контакта. Ответ на столкновение зависит от используемого моделирования. Решение проблем обнаружения столкновений требует широкого применения понятий из линейной алгебры и вычислительной геометрии. Алгоритмы обнаружения столкновений являются одним из основных составляющих трёхмерных компьютерных игр.
Задача о покрытии множества является классическим вопросом информатики и теории сложности. Данная задача обобщает NP-полную задачу о вершинном покрытии. Несмотря на то, что задача о вершинном покрытии сходна с данной, подход, использованный в приближённом алгоритме, здесь не работает. Вместо этого мы рассмотрим жадный алгоритм. Даваемое им решение будет хуже оптимального в логарифмическое число раз. С ростом размера задачи качество решения ухудшается, но всё же довольно медленно, поэтому такой подход можно считать полезным.
Метод случайного леса — алгоритм машинного обучения, предложенный Лео Брейманом и Адель Катлер, заключающийся в использовании ансамбля решающих деревьев. Алгоритм сочетает в себе две основные идеи: метод бэггинга Бреймана и метод случайных подпространств, предложенный Тин Кам Хо. Алгоритм применяется для задач классификации, регрессии и кластеризации. Основная идея заключается в использовании большого ансамбля решающих деревьев, каждое из которых само по себе даёт очень невысокое качество классификации, но за счёт их большого количества результат получается хорошим.
Алгоритм ID3 — один из алгоритмов для построения дерева принятия решений. Разработан Джоном Р. Квинланом. Впоследствии Квинлан создал усовершенствованную версию — алгоритм C4.5.
Алгоритм CART, как видно из названия, решает задачи классификации и регрессии построением дерева решений. Он разработан в 1974—1984 годах четырьмя профессорами статистики: Лео Брейманом (Беркли), Джеромом Фридманом (Стэнфорд), Чарлзом Стоуном и Ричардом Олшеном.
Теорема о планарном разбиении — это форма изопериметрического неравенства для планарных графов, которое утверждает, что любой планарный граф может быть разбит на более мелкие части путём удаления небольшого числа вершин. В частности, удалением O(√n) вершин из графа с n вершинами можно разбить граф на несвязные подграфы, каждый из которых имеет не более 2n/3 вершин.
Двенадцатеричный путь или двенадцать сценариев — это систематическая классификация 12 связанных перечислительных задач, касающихся двух конечных множеств, которые включают классические задачи подсчёта перестановок, сочетаний, мультимножеств и разбиений либо множества, либо числа. Идею классификации приписывают Джиану-Карло Роту, а название двенадцатеричный путь предложил Джоэл Спенсер по аналогии с термином восьмеричный путь из физики, который в свою очередь произошел от понятия восьмеричный путь в буддизме. Название намекает, что используя те же подходы в 12 случаях, но с небольшими изменениями в условиях, мы получаем 12 разных результатов.
Вероятно приближённо корректное обучение — схема машинного обучения, использующая понятия асимптотической достоверности и вычислительной сложности. Предложена в 1984 году Лесли Вэлиантом.
Обучение дерева решений использует дерево решений, чтобы перейти от наблюдений над объектами к заключениям о целевых значениях объектов. Это обучение является одним из подходов моделирования предсказаний, используемых в статистике, интеллектуальном анализе данных и машинном обучении. Модели деревьев, в которых целевая переменная может принимать дискретный набор значений, называются деревьями классификации. В этих структурах деревьев листья представляют метки классов, а ветки представляют конъюнкции признаков, которые ведут в эти метки классов. Деревья решений, в которых целевая переменная может принимать непрерывные значения называются деревьями регрессии.
Модульное разложение — это разложение графа на подмножества вершин, называемых модулями. Модуль является обобщением компоненты связности графа. В отличие от компонент связности, однако, один модуль может быть собственным подмножеством другого. Модули, поэтому, ведут к рекурсивной (иерархической) декомпозиции графа, а не просто к разбиениям.
Алгоритм Шрайера — Симса — алгоритм из области вычислительной теории групп, позволяющий после однократного исполнения за линейное время находить порядок группы, порождённой перестановками, проверять принадлежность элемента такой группе и перечислять её элементы. Алгоритм был предложен Чарльзом Симсом в 1970 году для поиска примитивных групп перестановок и основывается на лемме Шрайера о порождении подгрупп. Представление группы перестановок, которое находит алгоритм, аналогично ступенчатому виду матрицы для её пространства строк. Разработанные Симсом методы лежат в основе большинства современных алгоритмов для работы с группами перестановок, модификации алгоритма также используются в современных системах компьютерной алгебры, таких как GAP и Magma. Одним из наиболее наглядных приложений алгоритма является то, что он может быть использован для решения кубика Рубика.
Минимально критичное остовное дерево во взвешенном неориентированном графе — это остовное дерево, в котором наиболее тяжёлое ребро весит как можно меньше. Критичное ребро — это самое тяжёлое ребро в стягивающем дереве. Стягивающее дерево является минимальным критичным остовным деревом, если граф не содержит стягивающего дерева с критичным ребром меньшего веса. Для ориентированного графа аналогичная задача известна как минимально критичное стягивающее ориентированное дерево.
Разрезание торта согласно полезности — это правило дележа неоднородных ресурсов, таких как торт или земельная недвижимость, между несколькими участниками с различными функциями количественной полезности так, что сумма полезности для участников будет как можно больше. Такое разрезание было вдохновлено философией утилитаризма. Разрезание торта согласно полезности часто бывает «несправедливым». Следовательно, утилитаризм конфликтует со справедливым разрезанием торта.
