Problème de la somme de sous-ensembles

Problème de la somme de sous-ensembles

Le problème de la somme de sous-ensembles aussi noté SSP (de l'anglais Subset Sum Problem) est un problème important en complexité algorithmique et en cryptologie. Le problème est le suivant : étant donné un ensemble E de n entiers, existe-t-il un sous-ensemble de E dont la somme des éléments est nulle ?

C'est un problème NP-complet et l'un des plus simples à décrire. Le problème de la somme des sous-ensembles peut être vu comme un cas particulier du problème du sac à dos. Un cas particulier du problème de la somme des sous-ensembles est le partition d'un entier.

Sommaire

Exemple

On considère l'ensemble suivant : { −7, −3, −2, 5, 8}. Le problème admet une solution avec le sous-ensemble {-3, -2, 5} dont la somme est nulle.

On considère maintenant un autre ensemble : { -1, -2, -3}. Il est clair que le problème n'admet pas de solution (la somme est obligatoirement négative). Plus généralement, si tous les nombres sont strictement positifs ou tous les nombres sont strictement négatifs, alors le problème n'admet pas de solution (pour autant que la somme visée doit être nulle).

Généralisation

Le problème de la somme de sous-ensembles peut être généralisé pour toute somme cible s, avec s entier :

Étant donné un ensemble E de n entiers, existe-t-il un sous-ensemble de E dont la somme des éléments est s ?

Algorithmes de solution

Algorithme exponentiel

Algorithme pseudo-polynomial

Algorithme d'approximation

Un algorithme d'approximation peut résoudre la version suivante du problème. Étant donné un ensemble E de N entiers et un entier s, retourner

  • oui, s'il y a un sous-ensemble de E dont la somme des éléments est s ;
  • non, s'il n'y a pas de sous-ensemble de E dont la somme des éléments est entre (1-c)s et s pour un petit c>0 ;
  • n'importe quoi, s'il y a un sous-ensemble de E dont la somme des éléments est entre (1-c)s et s, mais aucun dont la somme est s.

Si tous les nombres sont non négatifs, la version approximative du problème de la somme de sous-ensembles se résout en temps polynomial en fonction de N et 1/c.

Références

  1. T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms. MIT Press, 2001. Chapter 35.5, The subset-sum problem.
  2. Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979, (ISBN 0-7167-1045-5).

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Problème de la somme de sous-ensembles de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Probleme de la somme de sous-ensembles — Problème de la somme de sous ensembles Le problème de la somme de sous ensembles aussi noté SSP (de l anglais Subset Sum Problem) est un problème important en complexité algorithmique et en cryptologie. Le problème est le suivant : étant… …   Wikipédia en Français

  • Problème de la somme d'un sous-ensemble — Problème de la somme de sous ensembles Le problème de la somme de sous ensembles aussi noté SSP (de l anglais Subset Sum Problem) est un problème important en complexité algorithmique et en cryptologie. Le problème est le suivant : étant… …   Wikipédia en Français

  • Probleme du sac a dos — Problème du sac à dos Le problème du sac à dos : quelles boîtes choisir afin de maximiser la somme emportée tout en ne dépassant pas les 15 kg autorisés ? Le problème du sac à dos, noté également KP (en anglais, Knapsack Problem) est un …   Wikipédia en Français

  • Problème du sac à dos — Le problème du sac à dos : quelles boîtes choisir afin de maximiser la somme emportée tout en ne dépassant pas les 15 kg autorisés ? En algorithmique, le problème du sac à dos, noté également KP (en anglais, Knapsack Problem) est un… …   Wikipédia en Français

  • Probleme de la couverture exacte — Problème de la couverture exacte Le problème de la couverture exacte est un problème d optimisation combinatoire NP complet qui fait partie des 21 problèmes NP complets de Karp. Sommaire 1 Énoncé 1.1 Exemple 1 1.2 Exemple 2 …   Wikipédia en Français

  • Problème aux valeurs propres généralisé — Valeur propre, vecteur propre et espace propre Fig. 1. Cette application linéaire déforme la statue de David. Les vecteurs bleus ont pour images les vecteurs verts. Ils gardent la même direction, ce sont des vecteurs propres. La valeur propre… …   Wikipédia en Français

  • Sous-espace propre — Valeur propre, vecteur propre et espace propre Fig. 1. Cette application linéaire déforme la statue de David. Les vecteurs bleus ont pour images les vecteurs verts. Ils gardent la même direction, ce sont des vecteurs propres. La valeur propre… …   Wikipédia en Français

  • Problème de la couverture exacte — Le problème de la couverture exacte est un problème d optimisation combinatoire NP complet qui fait partie des 21 problèmes NP complets de Karp. Sommaire 1 Énoncé 1.1 Exemple 1 1.2 Exemple 2 …   Wikipédia en Français

  • Sous-différentiel — En mathématiques, et plus précisément en analyse convexe, le sous différentiel est un concept permettant de décrire la variation locale d une fonction convexe (à valeurs réelles donc) non nécessairement différentiable dans un sens classique,… …   Wikipédia en Français

  • Sous-espace supplémentaire — En mathématiques, plus précisément en algèbre linéaire, deux sous espaces vectoriels d un même espace vectoriel sont supplémentaires dans cet espace si tout vecteur de l espace se décompose de façon unique en une somme d un vecteur de chacun des… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”