Связанные понятия
В теории узлов
простой узел или простое зацепление — это узел, который, в определённом смысле, неразложим. Точнее, это нетривиальный узел, который нельзя представить в виде конкатенации двух нетривиальных узлов. Об узлах, не являющихся простыми, говорят как о составных узлах или составных зацеплениях. Определить, является ли данный узел простым или нет, может оказаться сложной задачей.
Задача развязывания — задача алгоритмического распознавания тривиального узла если задано некоторое представление узла, то есть диаграмма узла. Существует несколько видов алгоритмов развязывания. Основная нерешённая проблема — можно ли решить задачу за полиномиальное время, то есть, принадлежит ли задача классу сложности P.
В теории узлов
восьмёрка (четырёхкратный узел или узел Листинга) — это единственный узел с числом пересечений четыре. Это наименьшее возможное число пересечений, за исключением тривиального узла и трилистника. Восьмёрка является простым узлом.
В теории узлов число мостов — это инвариант узла, определяемый как минимальное число мостов, требуемых для представления узла. При этом мост может быть переброшен не только через одну линию, но и через две, три и более.
В теории узлов число отрезков — это инвариант узла, определяющий наименьшее число прямых «отрезков», которые, соединяя конец к концу, образуют узел. Конкретнее, для любого узла K число отрезков K, обозначается stick(K), — это наименьшее число звеньев ломаной, эквивалентной K.
Сателлитный узел — конструкция позволяющая построить новый узел из двух узлов с определёнными дополнительными структурами.
Узел в математике — вложение окружности (одномерной сферы) в трёхмерное евклидово пространство, рассматриваемое с точностью до изотопии. Основной предмет изучения теории узлов. Два узла топологически эквивалентны, если один из них можно продеформировать в другой, причём в процессе деформации не должно возникать самопересечений.
Красно-чёрное дерево (англ. Red-black tree, RB-Tree) — это одно из самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и быстро выполняющее основные операции дерева поиска: добавление, удаление и поиск узла. Сбалансированность достигается за счёт введения дополнительного атрибута узла дерева — «цвета». Этот атрибут может принимать одно из двух возможных значений — «чёрный» или «красный».
В математической теории узлов, движением (преобразованием) Рейдемейстера называют одно из трёх...
Подробнее: Движение Рейдемейстера
Модель Барабаши-Альберт (БА) — алгоритм генерации случайных безмасштабных сетей с использованием принципа предпочтительного присоединения. Безмасштабные сети широко распространены в природных сетях (пищевые цепочки) и сетях, созданных человеком (Интернет, всемирная паутина, сети цитирования, некоторые социальные сети).
В исследованиях графов и сетей: степенью узла сети называют число его связей с другими узлами. Распределение степеней (узлов, вершин) - это распределение вероятностей степеней во всей сети.
Подробнее: Распределение степеней
Поиск в ширину (англ. breadth-first search, BFS) — метод обхода графа и поиска пути в графе. Поиск в ширину является одним из неинформированных алгоритмов поиска.
Решётка (англ. Grid network, иногда также mesh, например 3D-mesh) — понятие из теории организации компьютерных сетей. Это топология, в которой узлы образуют регулярную многомерную решётку. При этом каждое ребро решётки параллельно её оси и соединяет два смежных узла вдоль этой оси. Не следует путать с понятием Грид, обозначающем вычислительную систему.
В беспроводных сетях
проблема незащищенного узла возникает, когда узел ошибочно считает, что не может осуществлять передачу другим узлам из-за соседнего передатчика. Возьмем для примера 4 узла, названные R1, S1, S2 и R2; два приёмника R1 и R2 находятся за пределами видимости друг друга, в то время как два передатчика S1 и S2 находятся посередине, видят друг друга и один из приёмников. Тогда в случае передачи между S1 и R1 узел S2 не сможет передавать на R2, так как он решит, что вмешается в передачу...
Обход дерева (известный также как поиск по дереву) — вид обхода графа, обусловливающий процесс посещения (проверки и/или обновления) каждого узла структуры дерева данных ровно один раз. Такие обходы классифицируются по порядку, в котором узлы посещаются. Алгоритмы в статье относятся к двоичным деревьям, но могут быть обобщены и для других деревьев.
Дерево — это топология сетей, в которой каждый узел более высокого уровня связан с узлами более низкого уровня звездообразной связью, образуя комбинацию звезд. Также дерево называют иерархической звездой.
Целые
числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме ±1.
В комбинаторной математике под числом встреч понимается число перестановок множества {1, ..., n} с заданным числом неподвижных элементов.
Подробнее: Число встреч (комбинаторика)
В теории узлов ленточный узел — это узел, который ограничивает самопересекающийся круг только с ленточными особенностями. Интуитивно, этот вид особенности может быть образован путём совершения разреза в круге и пропусканием другой части круга через разрез. Более формально, этот тип особенности заключается в самопересечении по дуге. Прообраз этой дуги состоит из двух дуг круга, одна из которых полностью лежит внутри круга, а концы другой находятся на краю круга.
Задача коммивояжёра (англ. Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что...
Инвариант конечного типа (или инвариант Васильева) — класс инвариантов узлов, характеризующийся определённым соотношением на все разрешения сингулярного узла с данным числом самопересечений.
Матема́тика ку́бика Ру́бика — совокупность математических методов для изучения свойств кубика Рубика с абстрактно-математической точки зрения. Эта математика изучает алгоритмы сборки кубика и оценивает их. Основана на теории графов, теории групп, теории вычислимости и комбинаторике.
Разделение секрета (англ. Secret sharing) — термин в криптографии, под которым понимают любой из способов распределения секрета среди группы участников, каждому из которых достаётся своя некая доля. Секрет может воссоздать только коалиция участников из первоначальной группы, причём входить в коалицию должно не менее некоторого изначально известного их числа.
Дерево — одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связным графом, не содержащим циклы. Большинство источников также добавляют условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указывается, что рёбра графа не должны быть взвешенными.
Скейн-соотношение (или соотношение типа Конвея) часто используют, чтобы простым способом определить многочлен узла. Неформально говоря, скейн-соотношение задаёт линейную связь значений многочлена узла на трёх зацеплениях, которые отличаются друг от друга лишь в малой области. Для некоторых многочленов, таких как полиномы Конвея, Александера и Джонса, подходящего скейн-соотношения достаточно, чтобы вычислить многочлен рекурсивно. Для других, таких как полином HOMFLY, требуются более сложные алгоритмы...
Сюрреальные числа (англ. surreal number — название принадлежит американскому математику Дональду Кнуту) впервые были использованы под другим названием («числа» — англ. number) в работах английского математика Джона Конвея для описания ряда аспектов теории игр.
Цикломати́ческая сло́жность програ́ммы (англ. cyclomatic complexity of a program) — структурная (или топологическая) мера сложности компьютерной программы. Мера была разработана Томасом Дж. Маккейбом в 1976 году.
В теории узлов
мутация — это операция над узлом, которая может привести к другому узлу.
Задача о самом широком пути — это задача нахождения пути между двумя выбранными вершинами во взвешенном графе, максимизирующего вес минимального по весу ребра графа (если рассматривать вес ребра как ширину дороги, то задача стоит в выборе самой широкой дороги, связывающей две вершины). Задача о самом широком пути известна также как задача об узком месте или задача о пути с максимальной пропускной способностью. Можно приспособить алгоритмы кратчайшего пути для вычисления пропускной способности путём...
Тасование Фишера — Йетса (названо в честь Рональда Фишера и Франка Йетса (Frank Yates)), известное также под именем Тасование Кнута (в честь Дональда Кнута), — это алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества. Вариант тасования Фишера-Йетса, известный как алгоритм Саттоло (Sattolo), может быть использован для генерации случайного цикла перестановок длины n. Правильно реализованный алгоритм тасования Фишера-Йетса несмещённый, так...
Задача о змее в коробке в теории графов и информатике имеет дело с поиском определённого вида пути вдоль рёбер гиперкуба. Этот путь начинается с одного угла и проходит вдоль рёбер столько углов, сколько он может достичь. После того как достигается новый угол, предыдущий угол и все его соседи делаются недопустимыми для использования. Путь никогда не должен проходить через угол после того, как он помечен как недопустимый.
Октодерево (дерево октантов, восьмеричное дерево, англ. octree) — тип древовидной структуры данных, в которой у каждого внутреннего узла ровно восемь «потомков». Восьмеричные деревья чаще всего используются для разделения трёхмерного пространства, рекурсивно разделяя его на восемь ячеек. Октодеревья являются трёхмерными аналогами квадродеревьев. Англоязычное название «octree» сформировано из oct + tree и обычно пишется как «octree», а не «octtree».
Обучение дерева решений использует дерево решений (как предиктивную модель), чтобы перейти от наблюдений над объектами (представленными в ветвях) к заключениям о целевых значениях объектов (представленных в листьях). Это обучение является одним из подходов моделирования предсказаний, используемых в статистике, интеллектуальном анализе данных и обучении машин. Модели деревьев, в которых целевая переменная может принимать дискретный набор значений, называются деревьями классификации. В этих структурах...
Тёщин узел — верёвочный узел для соединения (связывания) верёвок и тросов. Он ненадёжен. Похож на бабий узел, однако ходовые концы выходят не с одной стороны, а по диагонали. Таким образом, тёщин узел сочетает в себе недостатки бабьего и воровского узлов.
Метод узловых потенциалов — метод расчета электрических цепей путём записи системы линейных алгебраических уравнений, в которой неизвестными являются потенциалы в узлах цепи. В результате применения метода определяются потенциалы во всех узлах цепи, а также, при необходимости, токи во всех рёбрах.
Двоичное дерево поиска (англ. binary search tree, BST) — это двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска)...
Куб Фибоначчи можно определить в терминах кодов Фибоначчи и расстояния Хэмминга, независимых множеств вершин в путях, или через дистрибутивные решётки.
Безопасное простое число — это простое число вида 2p + 1, где p также простое (и наоборот, p есть простое число Софи Жермен). Несколько первых безопасных простых чисел...
Зада́ча о кратча́йшем пути ́ — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь.
Ошибка на единицу или ошибка неучтённой единицы (англ. off-by-one error) — логическая ошибка в алгоритме, включающая в частности дискретный вариант нарушения граничных условий.
Система Штейнера (названа именем Якоба Штейнера) — вариант блок-схем, точнее, t-схемы с λ = 1 и t ≥ 2.
Префиксное дерево (также бор, луч, нагруженное дерево, англ. trie) — структура данных, позволяющая хранить ассоциативный массив, ключами которого являются строки. Представляет собой корневое дерево, каждое ребро которого помечено каким-то символом так, что для любого узла все рёбра, соединяющие этот узел с его сыновьями, помечены разными символами. Некоторые узлы префиксного дерева выделены (на рисунке они подписаны цифрами) и считается, что префиксное дерево содержит данную строку-ключ тогда и только...
В теории узлов хиральный узел — это узел, который не эквивалентен своему зеркальному отражению. Ориентированный узел, эквивалентный своему зеркальному отражению, называется амфихиральным узлом или ахиральным узлом. Хиральность узла является инвариантом узла. Хиральность узлов можно далее классифицировать в зависимости от того, обратим он или нет.
Праймориал (англ. Primorial, иногда именуется также «примориал») — в теории чисел функция над рядом натуральных чисел, схожая с функцией факториала, с разницей в том, что праймориал является последовательным произведением простых чисел, меньших или равных данному, в то время как факториал является последовательным произведением всех натуральных чисел, меньших или равных данному.