Домашня
Випадкова
Поблизу
Увійти
Налаштування
Пожертвувати
Про Вікіпедію
Відмова від відповідальності
Знайти
Шаблон
:
NP-повні задачі
Мова
Спостерігати
Редагувати
п
о
р
NP-повні задачі
Класифікація
Дослідження операцій
:
Оптимізація
:
Комбінаторна оптимізація
Основи
NP-повна задача
·
Клас складності NP
·
Клас складності P
Задачі
Задача заміщення сторінок
·
Задача здійсненності бульових формул
·
Задача комівояжера
·
Задача листоноші
·
Задача пакування рюкзака
·
Задача про кліку
·
Задача про точне покриття
·
Задача про пакування в ємності
(
двомірне пакування
•
лінійне пакування
тощо) •
Задача Штейнера
•
Задача про вершинне покриття
•
Задача про незалежну множину
•
Задача про покриття множини
·
...
Теорія складності обчислень
Теорія складності обчислень
•
Класи складності
Логічні ігри
та
головоломки
Гра в п'ятнашки (гра в
N
2
-1)
(
Задача пошуку найкоротшого рішення
) •
Задачі, рішення яких застосовуються в Тетрисі
•
Задача узагальненого судоку
•
Задача про заповнення латинського квадрата
•
Задачі какуро
Списки
21 NP-повна задача Карпа
·
Список NP-повних задач
Дослідники
Річард Карп
Див. також
Прикладна математика
•
Теорія алгоритмів
•
Динамічне програмування