Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Problème de la somme de sous-ensembles
Résumé
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.
Le problème de la somme de sous-ensembles peut être décrit avec une cible entière :
Étant donné un ensemble de entiers, existe-t-il un sous-ensemble de dont la somme des éléments est ?
Le problème de partition est un problème proche. Étant donné un ensemble de entiers, il faut décider si l'on peut partitionner en deux ensembles de même somme.
Le est le suivant. Étant donné un ensemble de entiers, existe-t-il trois entiers dont la somme est nulle ?
Ce problème peut être résolu facilement par programmation dynamique en temps O(n2), mais il est conjecturé que cette complexité est optimale. De nombreux problèmes, notamment en géométrie algorithmique sont prouvés 3SUM-difficiles.
Le problème de la somme de sous-ensembles est NP-complet : on peut par exemple lui réduire polynomialement le problème 3-SAT.
Algorithme pseudo-polynomial
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.