комбинаторная задача
1Задача об упаковке в контейнеры — В теории сложности вычислений задача об упаковке в контейнеры NP трудная комбинаторная задача. Задача заключается в упаковке объектов предопределённой формы в конечное число контейнеров предопределённой формы таким способом, чтобы число… …
2Задача трехмерной упаковки в объем — В теории сложности вычислений задача об упаковке в контейнеры NP трудная комбинаторная задача. Задача заключается в упаковке объектов предопределённой формы в конечное число контейнеров предопределённой формы таким способом, чтобы число… …
3Задача о покрытии множества — является классическим вопросом информатики и теории сложности. Данная задача обобщает NP полную задачу о вершинном покрытии (и потому является NP сложной). Несмотря на то, что задача о вершинном покрытии сходна с данной, подход, использованный в… …
4Задача о вершинном покрытии — NP полная задача информатики в области теории графов. Часто используется в теории сложности для доказательства NP полноты более сложных задач. Содержание 1 Определение 2 NP полнота 3 Ссылки …
5Задача о независимом множестве — относится к классу NP полных задач в области теории графов. Эквивалентна задаче о клике. Содержание 1 Определения 2 Максимальное независимое множество в дереве …
6Задача о клике — относится к классу NP полных задач в области теории графов. Впервые она была сформулирована в 1972 году Ричардом Карпом.[1] …
7Задача о мятом рубле — или задача о салфетке Маргулиса формулируется следующим образом: Можно ли сложить прямоугольный лист бумаги на плоскости так, что периметр полученной фигуры превысит периметр исходного листа? В математически точной формулировке требуется уточнить …
8Задача Лебега — состоит в отыскании плоской фигуры наименьшей площади, которая способна накрыть собой любую плоскую фигуру диаметра 1. Замечания Любая фигура диаметра 1 может быть накрыта фигурой постоянной ширины 1. Для фигур постоянной ширины, диаметр… …
9Задача о 18 точках — (парадокс 18 точек) одна из задач вычислительной геометрии. Поместим на отрезок точку с номером 1. Затем добавим ещё одну с номером 2 таким образом, чтобы они оказались в разных половинах отрезка. Третью точку добавим таким образом, чтобы все три …
10Задача коммивояжёра — Оптимальный маршрут коммивояжёра через 15 крупнейших городов Германии. Указанный маршрут является самым коротким из всех возможных 43 589 145 600. Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр …