Problème de la somme d'un sous-ensemble

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 donnés n entiers numérotés de 1 à n, ayant chacun une valeur, existe-t-il un sous-ensemble de ces éléments dont la somme des valeurs 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 problème de partition.

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 un entier :

Étant donnés n entiers numérotés de 1 à n, ayant chacun une valeur, existe-t-il un sous-ensemble de ces éléments dont la somme des valeurs 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 de N nombres x1, x2, ..., xN et un nombre s, retourner

  • oui, s'il y a un sous-ensemble dont la somme est s ;
  • non, s'il n'y a pas de sous-ensemble dont la somme est entre (1-c)s et s pour un petit c>0 ;
  • n'importe quoi, s'il y a un sous-ensemble dont la somme 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 and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979, ISBN 0-7167-1045-5.
  • Portail de la cryptologie Portail de la cryptologie
Ce document provient de « Probl%C3%A8me de la somme de sous-ensembles ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Problème de la somme d'un sous-ensemble 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 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 …   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

  • 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

  • Probleme de Mengoli — Problème de Bâle En mathématiques, le problème de Bâle (connu parfois aussi sous le nom de problème de Mengoli) est un problème célèbre dans la théorie des nombres, posé en premier par Pietro Mengoli en 1644, et résolu par le mathématicien suisse …   Wikipédia en Français

  • Problème de Mengoli — Problème de Bâle En mathématiques, le problème de Bâle (connu parfois aussi sous le nom de problème de Mengoli) est un problème célèbre dans la théorie des nombres, posé en premier par Pietro Mengoli en 1644, et résolu par le mathématicien suisse …   Wikipédia en Français

  • Problème de mengoli — Problème de Bâle En mathématiques, le problème de Bâle (connu parfois aussi sous le nom de problème de Mengoli) est un problème célèbre dans la théorie des nombres, posé en premier par Pietro Mengoli en 1644, et résolu par le mathématicien suisse …   Wikipédia en Français

  • sous- — ♦ Préfixe à valeur de préposition (sous main) ou d adverbe (sous jacent), marquant la position (sous sol, sous muqueux), la subordination (sous préfet), la subdivision (sous règne), le degré inférieur (sous littérature, sous prolétariat) et l… …   Encyclopédie Universelle

  • 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

Share the article and excerpts

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