Содержание
20 отношения: NP-полная задача, Класс P, Паросочетание, Остовное дерево, Оптимизация (математика), Равенство классов P и NP, Симплекс-метод, Удовлетворение ограничений, Целочисленное программирование, Матроид, Минимальное остовное дерево, Задача раскроя, Задача коммивояжёра, Задача о ранце, Задача о восьми ферзях, Задача о максимальном потоке, Задача о назначениях, Задача о назначении целей, Граф (математика), Линейное программирование.
- Теоретическая информатика
- Теория сложности вычислений
NP-полная задача
NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных).
Посмотреть Комбинаторная оптимизация и NP-полная задача
Класс P
В теории алгоритмов классом P (от polynomial) называют множество задач, для которых существуют «быстрые» алгоритмы решения (время работы которых полиномиально зависит от размера входных данных).
Посмотреть Комбинаторная оптимизация и Класс P
Паросочетание
В теории графов паросочетание или независимое множество рёбер в графе — это набор попарно несмежных рёбер.
Посмотреть Комбинаторная оптимизация и Паросочетание
Остовное дерево
Остовное дерево графа состоит из минимального подмножества рёбер графа, таких, что из любой вершины графа можно попасть в любую другую вершину, двигаясь по этим рёбрам.
Посмотреть Комбинаторная оптимизация и Остовное дерево
Оптимизация (математика)
Оптимизация — в математике, информатике и исследовании операций задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства, ограниченной набором линейных и/или нелинейных равенств и/или неравенств.
Посмотреть Комбинаторная оптимизация и Оптимизация (математика)
Равенство классов P и NP
Вопрос о равенстве классов сложности ''P'' и ''NP'' (в русских источниках также известный как проблема перебора) — это одна из центральных открытых проблем теории алгоритмов уже более трёх десятилетий.
Посмотреть Комбинаторная оптимизация и Равенство классов P и NP
Симплекс-метод
Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.
Посмотреть Комбинаторная оптимизация и Симплекс-метод
Удовлетворение ограничений
Одной из важных задач искусственного интеллекта (ИИ) является задача удовлетворения ограничений (УО) (constraint satisfaction problem).
Посмотреть Комбинаторная оптимизация и Удовлетворение ограничений
Целочисленное программирование
Задача целочисленного программирования — это задача математической оптимизации или выполнимости, в которой некоторые или все переменные должны быть целыми числами.
Посмотреть Комбинаторная оптимизация и Целочисленное программирование
Матроид
Матроид — классификация подмножеств некоторого множества, представляющая собой обобщение идеи независимости элементов, аналогично независимости элементов линейного пространства, на произвольное множество.
Посмотреть Комбинаторная оптимизация и Матроид
Минимальное остовное дерево
Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном взвешенном неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.
Посмотреть Комбинаторная оптимизация и Минимальное остовное дерево
Задача раскроя
Задача раскроя — это NP-полная задача оптимизации, по существу, сводимая к задаче о ранце.
Посмотреть Комбинаторная оптимизация и Задача раскроя
Задача коммивояжёра
43589145600 вариантов. Задача коммивояжёра (Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.
Посмотреть Комбинаторная оптимизация и Задача коммивояжёра
Задача о ранце
Пример задачи о ранце: необходимо уложить коробки в ранец вместимостью 15 кг так, чтобы стоимость уложенных коробок была максимальной Задача о ранце (или задача о рюкзаке) — NP-полная задача комбинаторной оптимизации.
Посмотреть Комбинаторная оптимизация и Задача о ранце
Задача о восьми ферзях
Задача о восьми ферзях.Одно из решений: a7, b4, c2, d8, e6, f1, g3, h5:(87) Зада́ча о восьми́ фе́рзя́х — широко известная задача по расстановке фигур на шахматной доске.
Посмотреть Комбинаторная оптимизация и Задача о восьми ферзях
Задача о максимальном потоке
Максимальный поток в транспортной сети. Числа обозначают потоки и пропускные способности. В теории оптимизации и теории графов, задача о максимальном потоке заключается в нахождении такого потока по транспортной сети, что сумма потоков из истока, или, что то же самое, сумма потоков в сток максимальна.
Посмотреть Комбинаторная оптимизация и Задача о максимальном потоке
Задача о назначениях
Задача о назначениях — одна из фундаментальных задач комбинаторной оптимизации в области математической оптимизации или исследовании операций.
Посмотреть Комбинаторная оптимизация и Задача о назначениях
Задача о назначении целей
Задача о назначении целей — это класс задач комбинаторной оптимизации.
Посмотреть Комбинаторная оптимизация и Задача о назначении целей
Граф (математика)
Неориентированный граф с шестью вершинами и семью рёбрами Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.
Посмотреть Комбинаторная оптимизация и Граф (математика)
Линейное программирование
Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Посмотреть Комбинаторная оптимизация и Линейное программирование
См. также
Теоретическая информатика
- INRIA
- Алгоритм
- Естественная информатика
- Идемпотентность
- Квантовое машинное обучение
- Квантовый алгоритм
- Класс сложности
- Коиндукция
- Комбинаторная оптимизация
- Корекурсия
- Лямбда-исчисление
- Массив Монжа
- Машина Тьюринга
- Наименьший общий предок
- Пи-исчисление
- Премия Гёделя
- Премия Кнута
- Рекурсивная функция
- Рекурсивное определение
- Система типов Хиндли — Милнера
- Спинтроника
- Теоретическая информатика
- Формальная верификация
- Формальные методы
- Формальный язык
Теория сложности вычислений
- L-нотация
- Аппроксимационный алгоритм
- Временная сложность алгоритма
- Вычислительная сложность
- Вычислительная топология
- Доказательство
- Задача изоморфности графов
- Класс сложности
- Колмогоровская сложность
- Комбинаторная оптимизация
- Модель вычислений
- Оценка сложности песен
- Псевдополиномиальный алгоритм
- Сложность аппроксимации
- Списочное декодирование
- Теория сложности вычислений
- Трансвычислительная задача
- Универсальное хеширование
- Экзистенциальная теория вещественных чисел