Subset sum problem
http://dbpedia.org/resource/Subset_sum_problem an entity of type: WikicatMathematicalProblems
مسألة مجموع المجموعات الجزئية Subset sum problem هي مسألة هامة في نظرية التعقيد الحسابي وعلم التعمية.يتم سرد المسألة على النحو التالي، من أجل مجموعة من الأعداد الصحيحة، هل يوجد بعض المجموعات الجزئية الغير خالية التي يكون مجموع عناصرها مساوياً للصفر؟على سبيل المثال هل يوجد مجموعة جزئية من المجموعة التالية {−2, −3, 15, 14, 7, −10} يكون مجموع عناصرها مساوياً للصفر؟ الجواب بكل بساطة هو نعم، لأن المجموعة الجزئية {−2, −3, −10, 15} مجموعها صفر وهو أمر من الممكن التحقق منه بكل بساطة بجمع العناصر. لكن إن عملية إيجاد كل مجموعة جزئية من المجموعة الأساسية يكون مجموع جميع عناصرها ينتهي إلى الصفر يأخذ وقتاً طويلاً.هذه المسألة هي مسألة NP كاملة وربما هي من أبسط المسائل من المسائل المعقدة.
rdf:langString
Das Teilsummenproblem (auch Untermengensummenproblem, engl. subset sum problem) ist ein berühmtes Problem der Informatik und des Operations Research.Es ist ein spezielles Rucksackproblem.
rdf:langString
El problema de la suma de subconjuntos es un problema importante en la teoría de la complejidad y en la criptografía. El problema es este: dado un conjunto de enteros, ¿existe algún subconjunto cuya suma sea exactamente cero? Por ejemplo, dado el conjunto { −7, −3, −2, 5, 8}, la respuesta es SI, porque el subconjunto { −3, −2, 5} suma cero. Este problema es NP-completo. Un problema equivalente es: dado un conjunto de enteros y un entero s, ¿existe algún subconjunto cuya suma sea s? La suma de subconjuntos también puede verse como un caso especial del problema de la mochila.
rdf:langString
部分和問題（ぶぶんわもんだい）は、計算複雑性理論・暗号理論における問題で、与えられた n 個の整数 a1,...,an から部分集合をうまく選んで、その集合内の数の和が与えられた数 N に等しくなるようにできるかどうかを判定する問題である。NP完全であることが知られている。 部分和問題は、分割問題 (Number Partitioning) の一般形でもある。分割問題とは、与えられた n 個の整数 a1,...,an を二つの集合に分け、各々の集合内の数の和がもう一方の集合内の数の和と等しくなるようにできるかどうかを判定する問題である。分割問題も、NP完全であることが示されている。 たとえば、「{1,3,7,10,13} の部分和で、和が 21 になるものは存在するか？」であれば存在する（{1,7,13}である）、が答えである。また「{2,4,6,8,10} の部分和で、和が 19 になるものは存在するか？」であれば、存在しない（どんな部分和も偶数にしかならない）、が答えである。 部分和問題は、ナップサック問題に含まれるため、動的計画法等の手法で解くことができる。（詳しくは、ナップサック問題の項を参照。）
rdf:langString
부분집합 합 문제(subset sum problem)는 계산 복잡도 이론과 암호학에 관련된 문제로, 유한 개의 정수로 이루어진 집합이 있을 때 이 집합의 부분집합 중에서 그 집합의 원소를 다 더한 값이 0이 되는 경우가 있는지를 알아내는 문제이다. 예를 들어 { −7, −3, −2, 5, 8}라는 집합이 있을 때, {-3, -2, 5}는 이 집합의 부분집합이면서 (-3)+(-2)+5=0이므로 이 경우의 답은 참이 된다. 이 문제는 NP-완전에 속한다. 이 문제에서 부분집합의 합 조건을 0 대신 일반적인 정수 s로 일반화할 수 있고, 또한 이 문제는 배낭 문제의 특수한 경우로 생각할 수 있다. 또한 집합을 합이 같은 두 집합으로 나누는 문제인 분할 문제는 이 문제의 특수한 경우이다.
rdf:langString
子集和問題（英語：Subset sum problem），又称子集合加總問題，是計算複雜度理論和密碼學中一個很重要的問題。问题可以描述为：給一個整數集合，問是否存在某個非空子集，使得子集内中的數字和為某个特定数值。例：給定集合{−7, −3, −2, 5, 8}，是否存在子集和为0的集合?答案是YES，因為子集{−3, −2, 5}的數字和是0。這個問題是NP完全问题，且或許是最容易描述的NP完全問題。 一個等價的問題是：給一個整數集合和另一個整數s，問是否存在某個非空子集，使得子集中的數字和為s。子集合加总问题可以想成是背包問題的一個特例。
rdf:langString
Le problème de la somme de sous-ensembles (en anglais : subset sum problem) est un problème de décision important en complexité algorithmique et en cryptologie. Le problème peut être décrit de la manière suivante : étant donné un ensemble de entiers, existe-t-il un sous-ensemble de dont la somme des éléments est nulle ? Par exemple, pour l'ensemble {-8, -3, -2, 4, 5}, la réponse est oui car la somme des éléments du sous-ensemble {-3, -2, 5} est nulle, par contre pour {-6, -1, 2, 3, 8} la réponse est non.
rdf:langString
The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset of integers and a target-sum , and the question is to decide whether any subset of the integers sum to precisely . The problem is known to be NP. Moreover, some restricted variants of it are NP-complete too, for example: SSP can also be regarded as an optimization problem: find a subset whose sum is at most T, and subject to that, as close as possible to T. It is NP-hard, but there are several algorithms that can solve it reasonably quickly in practice.
rdf:langString
Problem sumy podzbioru - jeden z ważniejszych problemów w teorii złożoności oraz kryptografii. Treść problemu: Mając dany skończony zbiór liczb całkowitych rozstrzygnąć, czy istnieje niepusty jego podzbiór sumujący się do zera. Np. dla zbioru {−7, −3, −2, 5, 8} odpowiedź jest pozytywna, ponieważ podzbiór {−3, −2, 5} sumuje się do zera. Problem należy do klasy problemów NP zupełnych i jest prawdopodobnie jednym z najprostszych do opisania. Można również spotkać następującą definicje problemu:
rdf:langString
Задача о сумме подмножеств — это важная задача в теории сложности алгоритмов и криптографии.Задача заключается в нахождении (хотя бы одного) непустого подмножества некоторого набора чисел, чтобы сумма чисел этого подмножества равнялась нулю.Например, пусть задано множество {−7, −3, −2, 5, 8}, тогда подмножество {−3, −2, 5} даёт в сумме ноль.Задача является NP-полной.
rdf:langString
Em ciência da computação, o problema da soma de subconjuntos é um importante problema da teoria da complexidade computacional e criptografia. O problema é este: dado um conjunto de inteiros, existe um subconjunto não-vazio cuja soma é 0? Por exemplo, dado o conjunto { −7, −3, −2, 5, 8}, a resposta é sim porque o subconjunto { -3, -2, 5} resulta numa soma que dá zero. O problema é NP-completo.
rdf:langString
В інформатиці задача про суму підмножини є важливою проблемою вибору в теорії складності та криптографії. Суть проблеми така: для заданої мультимножини цілих чисел, чи існує непорожня підмножина, сума елементів якої дорівнює нулю. Наприклад, якщо дано множину { −7, −3, −2, 5, 8}, то відповідь Так, тому що сума елементів підмножини {−3, −2, 5} дорівнює нулю. Сума підмножини може також розглядатися як особливий випадок задачі про рюкзак. Цікавим особливим випадком цієї задачі є задача про розбиття, при цьому S становить половину від суми всіх елементів у множині (тобто, ).
rdf:langString
rdf:langString
مسألة مجموع المجموعات الجزئية
rdf:langString
Teilsummenproblem
rdf:langString
Problema de la suma de subconjuntos
rdf:langString
Problème de la somme de sous-ensembles
rdf:langString
부분집합 합 문제
rdf:langString
部分和問題
rdf:langString
Problem sumy podzbioru
rdf:langString
Subset sum problem
rdf:langString
Problema da soma dos subconjuntos
rdf:langString
Задача о сумме подмножеств
rdf:langString
子集和問題
rdf:langString
Задача про суму підмножини
xsd:integer
36811
xsd:integer
1115049119
rdf:langString
مسألة مجموع المجموعات الجزئية Subset sum problem هي مسألة هامة في نظرية التعقيد الحسابي وعلم التعمية.يتم سرد المسألة على النحو التالي، من أجل مجموعة من الأعداد الصحيحة، هل يوجد بعض المجموعات الجزئية الغير خالية التي يكون مجموع عناصرها مساوياً للصفر؟على سبيل المثال هل يوجد مجموعة جزئية من المجموعة التالية {−2, −3, 15, 14, 7, −10} يكون مجموع عناصرها مساوياً للصفر؟ الجواب بكل بساطة هو نعم، لأن المجموعة الجزئية {−2, −3, −10, 15} مجموعها صفر وهو أمر من الممكن التحقق منه بكل بساطة بجمع العناصر. لكن إن عملية إيجاد كل مجموعة جزئية من المجموعة الأساسية يكون مجموع جميع عناصرها ينتهي إلى الصفر يأخذ وقتاً طويلاً.هذه المسألة هي مسألة NP كاملة وربما هي من أبسط المسائل من المسائل المعقدة.
rdf:langString
Das Teilsummenproblem (auch Untermengensummenproblem, engl. subset sum problem) ist ein berühmtes Problem der Informatik und des Operations Research.Es ist ein spezielles Rucksackproblem.
rdf:langString
El problema de la suma de subconjuntos es un problema importante en la teoría de la complejidad y en la criptografía. El problema es este: dado un conjunto de enteros, ¿existe algún subconjunto cuya suma sea exactamente cero? Por ejemplo, dado el conjunto { −7, −3, −2, 5, 8}, la respuesta es SI, porque el subconjunto { −3, −2, 5} suma cero. Este problema es NP-completo. Un problema equivalente es: dado un conjunto de enteros y un entero s, ¿existe algún subconjunto cuya suma sea s? La suma de subconjuntos también puede verse como un caso especial del problema de la mochila.
rdf:langString
Le problème de la somme de sous-ensembles (en anglais : subset sum problem) est un problème de décision important en complexité algorithmique et en cryptologie. Le problème peut être décrit de la manière suivante : étant donné un ensemble de entiers, existe-t-il un sous-ensemble de dont la somme des éléments est nulle ? Par exemple, pour l'ensemble {-8, -3, -2, 4, 5}, la réponse est oui car la somme des éléments du sous-ensemble {-3, -2, 5} est nulle, par contre pour {-6, -1, 2, 3, 8} la réponse est non. Le problème de la somme des sous-ensembles est NP-complet, c'est-à-dire considéré comme difficile à résoudre efficacement par un algorithme. Il peut être vu comme un cas particulier du problème du sac à dos.
rdf:langString
The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset of integers and a target-sum , and the question is to decide whether any subset of the integers sum to precisely . The problem is known to be NP. Moreover, some restricted variants of it are NP-complete too, for example:
* The variant in which all inputs are positive.
* The variant in which inputs may be positive or negative, and . For example, given the set , the answer is yes because the subset sums to zero.
* The variant in which all inputs are positive, and the target sum is exactly half the sum of all inputs, i.e., . This special case of SSP is known as the partition problem. SSP can also be regarded as an optimization problem: find a subset whose sum is at most T, and subject to that, as close as possible to T. It is NP-hard, but there are several algorithms that can solve it reasonably quickly in practice. SSP is a special case of the knapsack problem and of the multiple subset sum problem.
rdf:langString
部分和問題（ぶぶんわもんだい）は、計算複雑性理論・暗号理論における問題で、与えられた n 個の整数 a1,...,an から部分集合をうまく選んで、その集合内の数の和が与えられた数 N に等しくなるようにできるかどうかを判定する問題である。NP完全であることが知られている。 部分和問題は、分割問題 (Number Partitioning) の一般形でもある。分割問題とは、与えられた n 個の整数 a1,...,an を二つの集合に分け、各々の集合内の数の和がもう一方の集合内の数の和と等しくなるようにできるかどうかを判定する問題である。分割問題も、NP完全であることが示されている。 たとえば、「{1,3,7,10,13} の部分和で、和が 21 になるものは存在するか？」であれば存在する（{1,7,13}である）、が答えである。また「{2,4,6,8,10} の部分和で、和が 19 になるものは存在するか？」であれば、存在しない（どんな部分和も偶数にしかならない）、が答えである。 部分和問題は、ナップサック問題に含まれるため、動的計画法等の手法で解くことができる。（詳しくは、ナップサック問題の項を参照。）
rdf:langString
부분집합 합 문제(subset sum problem)는 계산 복잡도 이론과 암호학에 관련된 문제로, 유한 개의 정수로 이루어진 집합이 있을 때 이 집합의 부분집합 중에서 그 집합의 원소를 다 더한 값이 0이 되는 경우가 있는지를 알아내는 문제이다. 예를 들어 { −7, −3, −2, 5, 8}라는 집합이 있을 때, {-3, -2, 5}는 이 집합의 부분집합이면서 (-3)+(-2)+5=0이므로 이 경우의 답은 참이 된다. 이 문제는 NP-완전에 속한다. 이 문제에서 부분집합의 합 조건을 0 대신 일반적인 정수 s로 일반화할 수 있고, 또한 이 문제는 배낭 문제의 특수한 경우로 생각할 수 있다. 또한 집합을 합이 같은 두 집합으로 나누는 문제인 분할 문제는 이 문제의 특수한 경우이다.
rdf:langString
Problem sumy podzbioru - jeden z ważniejszych problemów w teorii złożoności oraz kryptografii. Treść problemu: Mając dany skończony zbiór liczb całkowitych rozstrzygnąć, czy istnieje niepusty jego podzbiór sumujący się do zera. Np. dla zbioru {−7, −3, −2, 5, 8} odpowiedź jest pozytywna, ponieważ podzbiór {−3, −2, 5} sumuje się do zera. Problem należy do klasy problemów NP zupełnych i jest prawdopodobnie jednym z najprostszych do opisania. Można również spotkać następującą definicje problemu: Mając dany zbiór liczb całkowitych oraz liczbę s rozstrzygnąć, czy istnieje niepusty jego podzbiór sumujący się do s.. Problem sumy podzbioru może być rozpatrywany jako szczególny przypadek problemu plecakowego. Jednym ze szczególnych przypadków problemu sumy podzbioru jest problem podziału, w którym s jest równe połowie sumy wszystkich liczb ze zbioru.
rdf:langString
Задача о сумме подмножеств — это важная задача в теории сложности алгоритмов и криптографии.Задача заключается в нахождении (хотя бы одного) непустого подмножества некоторого набора чисел, чтобы сумма чисел этого подмножества равнялась нулю.Например, пусть задано множество {−7, −3, −2, 5, 8}, тогда подмножество {−3, −2, 5} даёт в сумме ноль.Задача является NP-полной. Эквивалентной является задача нахождения подмножества, сумма элементов которого равна некоторому заданному числу s.Задачу о сумме подмножеств также можно рассматривать как некоторый специальный случай задачи о ранце.Интересным случаем задачи о суммировании подмножеств является задача о разбиении, в которой s равна половине суммы всех элементов множества.
rdf:langString
Em ciência da computação, o problema da soma de subconjuntos é um importante problema da teoria da complexidade computacional e criptografia. O problema é este: dado um conjunto de inteiros, existe um subconjunto não-vazio cuja soma é 0? Por exemplo, dado o conjunto { −7, −3, −2, 5, 8}, a resposta é sim porque o subconjunto { -3, -2, 5} resulta numa soma que dá zero. O problema é NP-completo. Um problema equivalente é este: dado um conjunto de inteiros e um inteiro s, existe algum subconjunto que some s? Problema da soma dos subconjuntos também pode ser pensado como um caso especial do problema da mochila. Um caso interessante de soma subconjunto é o problema de partição, em que s é a metade da soma de todos os elementos do conjunto.
rdf:langString
В інформатиці задача про суму підмножини є важливою проблемою вибору в теорії складності та криптографії. Суть проблеми така: для заданої мультимножини цілих чисел, чи існує непорожня підмножина, сума елементів якої дорівнює нулю. Наприклад, якщо дано множину { −7, −3, −2, 5, 8}, то відповідь Так, тому що сума елементів підмножини {−3, −2, 5} дорівнює нулю. Еквівалентна проблема полягає в наступному: задано мультимножину цілих чисел і цільова сума S, чи існує підмножина, сума елементів якої дорівнює S? Сума підмножини може також розглядатися як задача оптимізації: знайти підмножину, сума елементів якої найближче до S. Сума підмножини може також розглядатися як особливий випадок задачі про рюкзак. Цікавим особливим випадком цієї задачі є задача про розбиття, при цьому S становить половину від суми всіх елементів у множині (тобто, ). Задача є NP-повною. Проте існує декілька алгоритмів, які на практиці дозволяють швидко знайти відповідь.
rdf:langString
子集和問題（英語：Subset sum problem），又称子集合加總問題，是計算複雜度理論和密碼學中一個很重要的問題。问题可以描述为：給一個整數集合，問是否存在某個非空子集，使得子集内中的數字和為某个特定数值。例：給定集合{−7, −3, −2, 5, 8}，是否存在子集和为0的集合?答案是YES，因為子集{−3, −2, 5}的數字和是0。這個問題是NP完全问题，且或許是最容易描述的NP完全問題。 一個等價的問題是：給一個整數集合和另一個整數s，問是否存在某個非空子集，使得子集中的數字和為s。子集合加总问题可以想成是背包問題的一個特例。
xsd:nonNegativeInteger
23154