Voila j'ai fait un ptit algo pour trouver le noyau d'un ensemble, je m'explique :
 
On a par exemple un ensemble S={3,12,7) et un K=13 alors le sous-ensemble S'={3,7}
est un noyau car 13=2*3+1*7, par contre si K=11 il n'y a pas de noyau.
On veut simplement savoir si un ensemble a un noyau, pas le trouver.    
 
On souhaite un algo qui exploite les graphes.
 
J'ai fait un algo en utilisant Kruskal (j'ai mes sommets qui sont les 8,7,3,4 et mes arretes sont ponderes par la somme des deux sommets de larrete, donc je part avec un graphe connexe a donf) voici l'exemple:
 
K=19 et S={8,7,3,4}
 
On tri les arretes par ordre croissant et on part d'un des deux sommets de la plus petite arete ponderé ... on commence donc avec 3 (on test si K%3=0, si oui on sort de l'algo sinon on continu) on test si la ponderation suivante est inferieure à K si oui on continu (on emprunte l'arc de plus petite ponderation pour avancer) ..... on s'arrete avant que ca face un cycle.
 
Ainsi l'existence d'un ensemble non-vide a la sortie nous garantie que il y a un noyau.
 
(complexité en O(|E|log|V|))
 
Vous en pensez quoi ?
 
 
 

si ça fonctionne et que les performances te satisfont, ça me va.

Le probleme c'est que si le graphe est connexe "à donf" j'ai le |E| = qqchose*|V| et qui croit expo ... pas super ca.

ça veut dire que la complexité dans le pire des cas est O(n log(n)) ... on a vu pire

non ca veux dire que la complexité est expo.
 
EDIT: |E| c'est l'ensemble des arretes du graphe

vi, à mon avis il doit exister un algo meilleur.
juste quelque remarque à froid :
- si ton algo sort un ensemble vide, comment démontres-tu qu'il n'y a pas de noyau ?
- avec du pseudo-code ca serait plus précis
edit : un algo meilleur, exploitant les graphes

C'est un peu tot pour le pseudo-code...
En fait, mon algo ne sort jamais un ensemble vide, il sort soit faux soit un ensemble non-vide (dans ce cas la c'est equivalent a vrai, pourquoi je sais pas, je le sens). Mais de toute maniere ca marche pas pour K=7 et S={2,4}, ptet c'est pas bon Kruskal ici.
Le probleme c'est de savoir que sont les arretes.  (si elles sont pas ponderés, ca reduit le champs des algos des graphes applicables dessus)

13 = -26*3 + 13*7
Comment ça ? Positifs ? Fallait le dire

Comme on veux, de toute facon on ne veux ni le sous-ensemble noyau (ici si K=13 et S={3, 7, 48, 129, 311} alors le sous-ens noyau sera {3, 7}) ni les facteurs possibles ... on veux juste savoir si il y a un noyau ou pas (dans le cas contraire ca rejoint le subset-sum et là c'est cho la merde car c'est du NPC)

Ben non justement, ça change tout. Si tu accèptes les coeficients négatifs, alors le théorème de Bezout a pour conséquence que si deux des éléments de ton ensemble sont premiers entre eux, il y a un "noyau" (ces deux éléments) quel que soit K.
 
Bon je me suis un peu planté dans mon post précédent. Je voulais en fait donner un exemple avec K=11 (11 = -22*3 + 11*7).

Bein moi aussi je me suis un peu planté, les Ki sont des entiers naturels Dommage j'avais pas penser a Bezout.
 
EDIT: Ca aurais pu le faire  

petite forme chronoklazm... moi qui pensait que tu avais en tête l'équation diophantienne linéaire.
bah, ca arrive

Non les equations diophantienne ... je sais pas, elles ont un "bound ratio" qui ne me satisfait point
 
Sinon, j'ai peut etre trouvé un truc la ...
 
On nous donne au depart un S={X1, ... , Xn} d'entiers naturels positifs et un entier naturel K.
 
En entrée on a un graphe G=(V,E) ou :
   - L'ensemble V represente les sommets du graphe qui sont donc les Xi.
   - L'ensemble E tel que pour tout couple de sommets (x,y) € il y a une arrete si leurs somme est inferieure ou egale a K.
 
En sortie on veux :
   - V' un sous-ensemble de V tel que Pour tout Xi € S', somme(Xi*Ki)= K
 
Et donc supposont que l'on veux V' le plus petit possible.
 
Voila ca c'est pour la formalisation.
 
En gros l'algo se resume a un parcours de graphe à la Kruskal (on part d'un sommet quelquonque pourvu qu'il soit pas "à part" ). Sachant que à chaque pas on fait le teste suivant :
 

 
Mais bon je sais pas là ca marche pour K=15 et S={13,7,14,4,2} et j'ai peur de tester pour d'autres valeurs
 
EDIT : Au fait c'est du Greedy ca ou pas ?

kruskal est greedy donc j'aurai tendance à dire que ton algo est également, greedy

Honte à moi

K = 23
S = {5, 7, 10, 11}
=> Selon ton algo, le graphe est complet.
on a les aretes suivantes :
5+7=12
5+10=15
5+11=16
7+10=17
7+11=18
10+11=21
 
Voici ce que donne ton algo sur cet exemple :
 
5+7=12:
23 mod 5 = 3 != 0
23 mod 12 = 11 != 0
11 mod 5 = 1 != 0
11 mod 7 = 4 != 0
 
5+10=15:
23 mod 5 = 3 != 0
23 mod 15 = 8 != 0
8 mod 5 = 3 != 0
8 < 10
 
5+11=16:
23 mod 5 = 3 != 0
23 mod 16 = 7 != 0
7 mod 5 = 2 != 0
7 < 11
 
On a l'arbre couvrant minimal avec Kruskal donc l'algo nous retourne FAUX.
 
Cependant, on a bien 5 + 7 + 11 = 23

 
Bien essayer Chronoklazm !
Courage

Joli tracage
En fait j'ai l'impression qu'il me faut juste une liste temporaire avec des candidats eventuels.  
 
.....LOADING......

Je pense surtout que ton algo détecte l'existence de noyaux à 1 ou 2 éléments. Au delà, il y a un problème...

Zé zure !

d'après bezout,
a1.X1 + a2.X2 + ... + an.Xn = K    [1]
admet une solution dans Z si pgcd(a1, a2, ..., an) divise K.
 
Je vois mal comment un algo détecteur de noyau pourrait passer outre cette notion de PGCD.

... ou en faisant des modulo à la Euclide

Moi c'est le Z qui me derange, si on avait droit au Ai negatifs, ce serai vite reglé, en trouvant le premier couple d'entiers premiers entre eux (sachant qu'avec la somme ces deux entiers on a n'importe quel nombre).

Bon moi je propose :
 

 
Ca marche pour K = 23 et S = {5, 7, 10, 11}
 
.....SEARCHING FOR ERRORS.....
 
EDIT : Non en fait ca marche pas