Задача о разбиении: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Задача о разбиении''' (''Partitioning problem'') - одна из основных ''<math>\cal NP</math>-полных'...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Задача о разбиении''' (''Partitioning problem'') -
'''Задача о разбиении''' (''[[Partitioning problem]]'') одна из основных ''<math>\mathcal NP</math>-полных'' задач. Формулируется следующим образом.
одна из основных ''<math>\cal NP</math>-полных'' задач.
Формулируется следующим образом.


Существует ли разбиение данного конечного множества
Существует ли разбиение данного конечного множества элементов, имеющих неотрицательный вес, на два подмножества, равных по суммарному весу составляющих их элементов?
элементов, имеющих неотрицательный вес, на два подмножества, равных по
суммарному весу составляющих их элементов?


См. также ''Задача о вершинном покрытии, Задача о выполнимости, Задача о клике, Задача о неэквивалентности регулярных выражений, Задача о точном покрытии 3-множествами, Задача о трехмерном сочетании, Классы <math>\cal P</math> и <math>\cal NP</math>, Метод локальной замены, Метод построения компонент, Метод сужения задачи, Полиномиальная сводимость (трансформируемость), <math>\cal NP</math>-полная задача, Труднорешаемая задача.''
==См. также==
* ''[[Задача о вершинном покрытии]],''
* ''[[Задача о выполнимости]],''
* ''[[Задача о клике]],''
* ''[[Задача о неэквивалентности регулярных выражений]],''
* ''[[Задача о точном покрытии 3-множествами]],''
* ''[[Задача о трехмерном сочетании]],''
* ''[[Классы P и NP|Классы <math>\mathcal P</math> и <math>\mathcal NP</math>]],''
* ''[[Метод локальной замены]],''
* ''[[Метод построения компонент]],''
* ''[[Метод сужения задачи]],''
* ''[[Полиномиальная сводимость (трансформируемость)]],''
* ''[[NP-Полная задача|<math>\mathcal NP</math>-полная задача]],''
* ''[[Труднорешаемая задача]].''
==Литература==
==Литература==
[Ахо-Хопкрофт-Ульман],
* Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. —  М.: Мир, 1979.


[Касьянов/95]
* Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.

Текущая версия от 15:45, 11 февраля 2011

Задача о разбиении (Partitioning problem) — одна из основных [math]\displaystyle{ \mathcal NP }[/math]-полных задач. Формулируется следующим образом.

Существует ли разбиение данного конечного множества элементов, имеющих неотрицательный вес, на два подмножества, равных по суммарному весу составляющих их элементов?

См. также

Литература

  • Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.