Partition problem
http://dbpedia.org/resource/Partition_problem an entity of type: Agent
Problém dvou loupežníků je v matematické informatice NP-úplný problém, jak rozdělit kořist (oceněné věci) mezi dva loupežníky tak, aby lup byl rozdělen rovným dílem (součet hodnot věcí v jedné skupině byl roven součtu hodnot věcí v druhé skupině).
rdf:langString
Das Partitionsproblem (auch Zahlenaufteilungsproblem, oft mit PARTITION notiert) ist ein Optimierungs- bzw. Entscheidungsproblem der Kombinatorik.
rdf:langString
En informatique théorique, le problème de partition est le problème de décision qui, étant donné un multiensemble S d'entiers naturels, détermine s'il existe une partition de S en deux sous-ensembles S1 and S2 tels que la somme des éléments de S1 soit égale à la somme des éléments de S2. On ne connait pas d'algorithme en temps polynomial permettant de trouver une solution exacte rapidement dans tous les cas, c'est un problème NP-complet.
rdf:langString
분할 문제(partition problem)는 전산학에서 다루는 NP-완전 문제이다. 이 문제는 정수 중복집합을 합이 같은 두 집합으로 나눌 수 있는지를 묻는다. 더 정확히 기술하면, 정수 중복집합 S가 있을 때, S를 S1과 S2로 나누어서 두 부분집합에 속한 숫자들의 합이 똑같도록 할 수 있는지를 묻는 문제이다. 부분집합 S1과 S2는 서로소이고 S를 덮는다는 관점에서 볼 때 S를 분할한다. 분할 문제는 부분집합 합 문제의 특수한 경우와 동치이다. 정수 집합 S가 있고 S의 모든 원소의 합이 t일 때, 원소의 합이 t/2가 되는 부분집합 S1이 있는지를 묻는 것이다. (S − S1을 찾는 것도 이와 동치이다.) 그러므로 부분집합 합 문제에 대한 동적계획법이 분할 문제에도 잘 작동한다. 분할 문제의 변형으로 가 있다. 집합 S를 원소의 합이 |S|/3 인 세 부분집합으로 나누는 문제이다. 분할 문제와 달리 3분할 문제를 푸는 의사 다항 시간 알고리즘은 가 아닌 한 존재하지 않는다. 즉, 3분할 문제는 을 쓰는 경우에도 NP-완전이다.
rdf:langString
Problem podziału – jeden z modelowych problemów NP-zupełnych przedstawiający się następująco: czy dla danego skończonego multizbioru liczb całkowitych istnieje jego podział na dwa jego podzbiory U i T, że suma elementów zbioru T równa się sumie elementów zbioru U?
rdf:langString
Het partitieprobleem is een probleem uit de combinatoriek.
rdf:langString
分区问题（英語：Partition problem）是数论和计算机科学领域的问题，目的是把一个多重集分为和两个子集，要求和这两个集合中所有数的和相等。尽管分区问题属于NP完全问题，但是依然存在伪多项式时间的动态规划解法，而且在很多情况下也存在启发式的解法，能够求出最优解或近似最优解。正是基于这一点，这类问题也被称为“最简单的难题”。 分区问题存在一个最佳化問題，该问题是将分为和，要求中元素的和与中元素的和相差最小。这一问题属于NP困难问题，但在实践中依旧存在高效的解法。 分区问题是以下两个相关问题的特殊情况：
* 子集和问题：从集合找到一个子集，使其所有元素的和等于一给定值（分区问题就是T为所有元素之和的时的特殊情况）
* ：将集合分为个子集，要求每个子集的元素之和都相等（分区问题就是时的特殊情况）
* 但是需要注意的是，三分区问题与分区问题有很大不同，三分区问题要求每个子集中都有3个元素。三分区问题比分区问题更难，甚至连伪多项式时间算法都不存在，除非满足P=NP。
rdf:langString
En ciencias de la computación, el Problema de la partición es un problema NP-completo, que visto como un problema de decisión, consiste en decidir si, dado un multiconjunto de números enteros, puede este ser particionado en dos "mitades" tal que sumando los elementos de cada una, ambas den como resultado la misma suma. Más precisamente, dado un multiconjunto S de enteros: ¿existe alguna forma de partir S en dos subconjuntos S1 y S2, tal que la suma de los elementos en S1 sea igual que la suma de los elementos en S2?
rdf:langString
In number theory and computer science, the partition problem, or number partitioning, is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2. Although the partition problem is NP-complete, there is a pseudo-polynomial time dynamic programming solution, and there are heuristics that solve the problem in many instances, either optimally or approximately. For this reason, it has been called "the easiest hard problem".
rdf:langString
Na ciência da computação, o problema da partição (ou particionamento de números) é a tarefa de decidir se um determinado multiconjunto S de números inteiros positivos pode ser particionado em dois subconjuntos de S1 e S2 , tais que a soma dos números em S1 é igual à soma dos números em S2. Embora o problema da partição seja NP-completo, existe uma solução com programação dinâmica com tempo pseudo-polinomial e há uma heurística que resolve o problema, em muitos casos, de forma otimizada, ou aproximadamente. Por esta razão, ele tem sido chamado de "o problema NP-difícil mais fácil".
rdf:langString
Задача разбиения множества чисел — это задача определения, можно ли данное мультимножество S положительных целых чисел разбить на два подмножества S1 и S2, таких, что сумма чисел из S1 равна сумме чисел из S2. Хотя задача разбиения чисел является NP-полной, существует решение псевдополиномиального времени методом динамического программирования и существуют эвристические алгоритмы решения для многих конкрентных задач либо оптимально, либо приближённо. По этой причине задачу называют "простейшей NP-трудной задачей".
rdf:langString
У теорії чисел та інформатиці, задачею про розбиття (або розбиття числа) є визначення того, чи можна дану множину S натуральних чисел розбити на дві підмножини S1 і S2 так, щоб сума чисел у S1 дорівнювала сумі чисел в S2. Хоча задача про розбиття NP-повна, існує псевдо-поліноміальне рішення динамічного програмування часу, і є евристики, які вирішують цю задачу оптимально або приблизно. З цієї причини її назвали «найлегшою NP-важкою задачею» . Задача про розбиття є окремим випадком задачі про суми підмножин, тому її можна точно розв'язати за час O(2S/2).
rdf:langString
rdf:langString
Problém dvou loupežníků
rdf:langString
Partitionsproblem
rdf:langString
Problema de la partición
rdf:langString
Problème de partition
rdf:langString
분할 문제
rdf:langString
Partition problem
rdf:langString
Partitieprobleem
rdf:langString
Problem podziału
rdf:langString
Problema da partição
rdf:langString
Задача разбиения множества чисел
rdf:langString
分区问题
rdf:langString
Задача про розбиття
xsd:integer
3269567
xsd:integer
1124243272
rdf:langString
Problém dvou loupežníků je v matematické informatice NP-úplný problém, jak rozdělit kořist (oceněné věci) mezi dva loupežníky tak, aby lup byl rozdělen rovným dílem (součet hodnot věcí v jedné skupině byl roven součtu hodnot věcí v druhé skupině).
rdf:langString
Das Partitionsproblem (auch Zahlenaufteilungsproblem, oft mit PARTITION notiert) ist ein Optimierungs- bzw. Entscheidungsproblem der Kombinatorik.
rdf:langString
En informatique théorique, le problème de partition est le problème de décision qui, étant donné un multiensemble S d'entiers naturels, détermine s'il existe une partition de S en deux sous-ensembles S1 and S2 tels que la somme des éléments de S1 soit égale à la somme des éléments de S2. On ne connait pas d'algorithme en temps polynomial permettant de trouver une solution exacte rapidement dans tous les cas, c'est un problème NP-complet.
rdf:langString
En ciencias de la computación, el Problema de la partición es un problema NP-completo, que visto como un problema de decisión, consiste en decidir si, dado un multiconjunto de números enteros, puede este ser particionado en dos "mitades" tal que sumando los elementos de cada una, ambas den como resultado la misma suma. Más precisamente, dado un multiconjunto S de enteros: ¿existe alguna forma de partir S en dos subconjuntos S1 y S2, tal que la suma de los elementos en S1 sea igual que la suma de los elementos en S2? El problema de partición es equivalente a un caso particular del problema de la suma de subconjuntos, el cual dice: dado un conjunto S de enteros, ¿existe algún subconjunto S1 de S cuyos elementos suman exactamente t /2, donde t es la suma de todos los elementos de S? La equivalencia puede verse definiendo S2 como la diferencia S − S1. Por lo tanto, la solución con programación dinámica existente para resolver el problema de suma de subconjuntos, utilizando tiempo pseudo-polinómico, también es aplicable al problema de partición. Una variación de este problema es el problema de la 3-partición, en donde el conjunto S debe particionarse en |S|/3 subconjuntos que sumen lo mismo. A diferencia del problema de partición, este problema no es resoluble en tiempo pseudo-polinómico, a menos que P = NP: esto porque el problema de 3-partición permanece en la clase NP-completa incluso utilizando codificación unaria.
rdf:langString
In number theory and computer science, the partition problem, or number partitioning, is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2. Although the partition problem is NP-complete, there is a pseudo-polynomial time dynamic programming solution, and there are heuristics that solve the problem in many instances, either optimally or approximately. For this reason, it has been called "the easiest hard problem". There is an optimization version of the partition problem, which is to partition the multiset S into two subsets S1, S2 such that the difference between the sum of elements in S1 and the sum of elements in S2 is minimized. The optimization version is NP-hard, but can be solved efficiently in practice. The partition problem is a special case of two related problems:
* In the subset sum problem, the goal is to find a subset of S whose sum is a certain target number T given as input (the partition problem is the special case in which T is half the sum of S).
* In multiway number partitioning, there is an integer parameter k, and the goal is to decide whether S can be partitioned into k subsets of equal sum (the partition problem is the special case in which k = 2).
* However, it is quite different than the 3-partition problem: in that problem, the number of subsets is not fixed in advance – it should be |S|/3, where each subset must have exactly 3 elements. 3-partition is much harder than partition – it has no pseudo-polynomial time algorithm unless P = NP.
rdf:langString
분할 문제(partition problem)는 전산학에서 다루는 NP-완전 문제이다. 이 문제는 정수 중복집합을 합이 같은 두 집합으로 나눌 수 있는지를 묻는다. 더 정확히 기술하면, 정수 중복집합 S가 있을 때, S를 S1과 S2로 나누어서 두 부분집합에 속한 숫자들의 합이 똑같도록 할 수 있는지를 묻는 문제이다. 부분집합 S1과 S2는 서로소이고 S를 덮는다는 관점에서 볼 때 S를 분할한다. 분할 문제는 부분집합 합 문제의 특수한 경우와 동치이다. 정수 집합 S가 있고 S의 모든 원소의 합이 t일 때, 원소의 합이 t/2가 되는 부분집합 S1이 있는지를 묻는 것이다. (S − S1을 찾는 것도 이와 동치이다.) 그러므로 부분집합 합 문제에 대한 동적계획법이 분할 문제에도 잘 작동한다. 분할 문제의 변형으로 가 있다. 집합 S를 원소의 합이 |S|/3 인 세 부분집합으로 나누는 문제이다. 분할 문제와 달리 3분할 문제를 푸는 의사 다항 시간 알고리즘은 가 아닌 한 존재하지 않는다. 즉, 3분할 문제는 을 쓰는 경우에도 NP-완전이다.
rdf:langString
Problem podziału – jeden z modelowych problemów NP-zupełnych przedstawiający się następująco: czy dla danego skończonego multizbioru liczb całkowitych istnieje jego podział na dwa jego podzbiory U i T, że suma elementów zbioru T równa się sumie elementów zbioru U?
rdf:langString
Het partitieprobleem is een probleem uit de combinatoriek.
rdf:langString
Na ciência da computação, o problema da partição (ou particionamento de números) é a tarefa de decidir se um determinado multiconjunto S de números inteiros positivos pode ser particionado em dois subconjuntos de S1 e S2 , tais que a soma dos números em S1 é igual à soma dos números em S2. Embora o problema da partição seja NP-completo, existe uma solução com programação dinâmica com tempo pseudo-polinomial e há uma heurística que resolve o problema, em muitos casos, de forma otimizada, ou aproximadamente. Por esta razão, ele tem sido chamado de "o problema NP-difícil mais fácil". Há uma versão otimizada do problema da partição, que é particionar o multiconjunto S em dois subconjuntos S1, S2 , tais que a diferença entre a soma dos elementos de S1 e a soma dos elementos de S2 é minimizada. A versão de otimização é NP-difícil, mas pode ser resolvida de forma eficiente na prática.
rdf:langString
Задача разбиения множества чисел — это задача определения, можно ли данное мультимножество S положительных целых чисел разбить на два подмножества S1 и S2, таких, что сумма чисел из S1 равна сумме чисел из S2. Хотя задача разбиения чисел является NP-полной, существует решение псевдополиномиального времени методом динамического программирования и существуют эвристические алгоритмы решения для многих конкрентных задач либо оптимально, либо приближённо. По этой причине задачу называют "простейшей NP-трудной задачей". Существует оптимизационная версия задачи разбиения, в которой требуется разбить мультимножество S на два подмножества S1 и S2, таких, что разность между суммой элементов S1 и суммой элементов S2 минимальна. Оптимизационная версия является NP-трудной задачей, но на практике может быть решена эффективно.
rdf:langString
У теорії чисел та інформатиці, задачею про розбиття (або розбиття числа) є визначення того, чи можна дану множину S натуральних чисел розбити на дві підмножини S1 і S2 так, щоб сума чисел у S1 дорівнювала сумі чисел в S2. Хоча задача про розбиття NP-повна, існує псевдо-поліноміальне рішення динамічного програмування часу, і є евристики, які вирішують цю задачу оптимально або приблизно. З цієї причини її назвали «найлегшою NP-важкою задачею» . Існує версія оптимізації задачі про розбиття, яка полягає в розбитті мультимножини S на дві підмножини S1, S2, так що різниця між сумою елементів в S1 і сумою елементів в S2 мінімізована. Оптимізаційна версія NP-важка, але на практиці її можна ефективно вирішити. Задача про розбиття є окремим випадком задачі про суми підмножин, тому її можна точно розв'язати за час O(2S/2).
rdf:langString
分区问题（英語：Partition problem）是数论和计算机科学领域的问题，目的是把一个多重集分为和两个子集，要求和这两个集合中所有数的和相等。尽管分区问题属于NP完全问题，但是依然存在伪多项式时间的动态规划解法，而且在很多情况下也存在启发式的解法，能够求出最优解或近似最优解。正是基于这一点，这类问题也被称为“最简单的难题”。 分区问题存在一个最佳化問題，该问题是将分为和，要求中元素的和与中元素的和相差最小。这一问题属于NP困难问题，但在实践中依旧存在高效的解法。 分区问题是以下两个相关问题的特殊情况：
* 子集和问题：从集合找到一个子集，使其所有元素的和等于一给定值（分区问题就是T为所有元素之和的时的特殊情况）
* ：将集合分为个子集，要求每个子集的元素之和都相等（分区问题就是时的特殊情况）
* 但是需要注意的是，三分区问题与分区问题有很大不同，三分区问题要求每个子集中都有3个元素。三分区问题比分区问题更难，甚至连伪多项式时间算法都不存在，除非满足P=NP。
xsd:nonNegativeInteger
18899