| rdfs:comment
| - مسألة مجموع المجموعات الجزئية Subset sum problem هي مسألة هامة في نظرية التعقيد الحسابي وعلم التعمية.يتم سرد المسألة على النحو التالي، من أجل مجموعة من الأعداد الصحيحة، هل يوجد بعض المجموعات الجزئية الغير خالية التي يكون مجموع عناصرها مساوياً للصفر؟على سبيل المثال هل يوجد مجموعة جزئية من المجموعة التالية {−2, −3, 15, 14, 7, −10} يكون مجموع عناصرها مساوياً للصفر؟ الجواب بكل بساطة هو نعم، لأن المجموعة الجزئية {−2, −3, −10, 15} مجموعها صفر وهو أمر من الممكن التحقق منه بكل بساطة بجمع العناصر. لكن إن عملية إيجاد كل مجموعة جزئية من المجموعة الأساسية يكون مجموع جميع عناصرها ينتهي إلى الصفر يأخذ وقتاً طويلاً.هذه المسألة هي مسألة NP كاملة وربما هي من أبسط المسائل من المسائل المعقدة. (ar)
- Das Teilsummenproblem (auch Untermengensummenproblem, engl. subset sum problem) ist ein berühmtes Problem der Informatik und des Operations Research.Es ist ein spezielles Rucksackproblem. (de)
- 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. (es)
- 部分和問題（ぶぶんわもんだい）は、計算複雑性理論・暗号理論における問題で、与えられた 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 になるものは存在するか？」であれば、存在しない（どんな部分和も偶数にしかならない）、が答えである。 部分和問題は、ナップサック問題に含まれるため、動的計画法等の手法で解くことができる。（詳しくは、ナップサック問題の項を参照。） (ja)
- 부분집합 합 문제(subset sum problem)는 계산 복잡도 이론과 암호학에 관련된 문제로, 유한 개의 정수로 이루어진 집합이 있을 때 이 집합의 부분집합 중에서 그 집합의 원소를 다 더한 값이 0이 되는 경우가 있는지를 알아내는 문제이다. 예를 들어 { −7, −3, −2, 5, 8}라는 집합이 있을 때, {-3, -2, 5}는 이 집합의 부분집합이면서 (-3)+(-2)+5=0이므로 이 경우의 답은 참이 된다. 이 문제는 NP-완전에 속한다. 이 문제에서 부분집합의 합 조건을 0 대신 일반적인 정수 s로 일반화할 수 있고, 또한 이 문제는 배낭 문제의 특수한 경우로 생각할 수 있다. 또한 집합을 합이 같은 두 집합으로 나누는 문제인 분할 문제는 이 문제의 특수한 경우이다. (ko)
- 子集和問題（英語：Subset sum problem），又称子集合加總問題，是計算複雜度理論和密碼學中一個很重要的問題。问题可以描述为：給一個整數集合，問是否存在某個非空子集，使得子集内中的數字和為某个特定数值。例：給定集合{−7, −3, −2, 5, 8}，是否存在子集和为0的集合?答案是YES，因為子集{−3, −2, 5}的數字和是0。這個問題是NP完全问题，且或許是最容易描述的NP完全問題。 一個等價的問題是：給一個整數集合和另一個整數s，問是否存在某個非空子集，使得子集中的數字和為s。子集合加总问题可以想成是背包問題的一個特例。 (zh)
- 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. (fr)
- 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. (en)
- 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: (pl)
- Задача о сумме подмножеств — это важная задача в теории сложности алгоритмов и криптографии.Задача заключается в нахождении (хотя бы одного) непустого подмножества некоторого набора чисел, чтобы сумма чисел этого подмножества равнялась нулю.Например, пусть задано множество {−7, −3, −2, 5, 8}, тогда подмножество {−3, −2, 5} даёт в сумме ноль.Задача является NP-полной. (ru)
- 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. (pt)
- В інформатиці задача про суму підмножини є важливою проблемою вибору в теорії складності та криптографії. Суть проблеми така: для заданої мультимножини цілих чисел, чи існує непорожня підмножина, сума елементів якої дорівнює нулю. Наприклад, якщо дано множину { −7, −3, −2, 5, 8}, то відповідь Так, тому що сума елементів підмножини {−3, −2, 5} дорівнює нулю. Сума підмножини може також розглядатися як особливий випадок задачі про рюкзак. Цікавим особливим випадком цієї задачі є задача про розбиття, при цьому S становить половину від суми всіх елементів у множині (тобто, ). (uk)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)