Discussion:Problème de la couverture irredondante

Doublon ?

 Lf69100 :Bonjour,

il me semble que cet article porte sur le même sujet que problème de la couverture exacte, qu'en pensez-vous ? --Roll-Morton (discuter) 8 juillet 2014 à 11:45 (CEST)

 Epsilon0 et Lf69100 : Je réitère.--Roll-Morton (discuter) 16 février 2015 à 11:57 (CET)

A ce que je comprends de ce présent article, une couverture irrédondante n'exige pas que les sous-ensembles soient disjoints (comme il en est pour une couverture exacte) mais seulement que tout sous ensemble soit nécessaire (relativement aux autres), càd ait un élement n'appartenant à aucun des autres sous-ensembles. --Epsilon0 ε₀ 16 février 2015 à 14:57 (CET)

Ah oui bien vu, j'avais mal lu. Par contre du coup ça revient à problème de couverture par ensembles, sauf si je me trompe encore. --Roll-Morton (discuter) 16 février 2015 à 20:06 (CET)

Là encore, tel que je comprends la formulation de Problème de couverture par ensembles (et de en:Set cover problem ), ce n'est pas exactement le même problème qui est abordé ... même si clairement on surfe sur les mêmes notions et que je n'aurais rien contre un article général recouverturant  ;-) ces trois sujets. Prenons l'ensemble {1, 2, 3}

• { {1, 2}, {3} } est une couverture exacte ... qui est tout bonnement Partition d'un ensemble !!
• { {1, 2}, {2, 3} } est une couverture irredondante (<-- a t-on des ref sur cette notion ?  Lf69100 : ouh, ouh ) mais pas une couverture exacte
• Un Problème de couverture par ensembles semble être (d'après ce que je comprends) de déterminer étant donné un ensemble (ici {1, 2, 3} ) ET une couverture irrédondante, par exemple ({ {1, 2}, {2, 3}, {3, 1} }, LA couverture exacte utilisant cette couverture irrédondante de l'ensemble. ... Manque de bol mon exemple montre qu'elle n'est pas forcément unique comme semble le laisser penser l'article ;-).

Bon, mon avis est :

• 1/qu'il y a la question ("simple") de la partition d'un ensemble par des classes d'équivalence, rendu par le problème de la couverture exacte
• 2/ qu'il y a moult autres questions de recouvrements (moins "simples") que l'on peut se poser sur le sujet et qui peuvent mériter des articles autonomes sur wp s'ils possèdent, comme ce semble être le cas pour Problème de couverture par ensembles, une littérature propre.

Bon, je mets un mot sur le thé avec lien vers cette discussion. --Epsilon0 ε₀ 16 février 2015 à 22:27 (CET)

Hum, je connais pas mal problème de couverture par ensembles, et dans ce problème, un élément peut être couvert plusieurs fois. Par exemple, étant donné les éléments 1,2,3,4,5 et les ensembles (1,2,3)(3,4,5)(4)(5), la couverture ((1,2,3)(3,4,5)) est licite et c'est même la meilleure couverture, car c'est celle qui utilise le moins d'ensembles. Pour le problème de la couverture exacte, la seule solution licite est ((1,2,3)(4)(5)). Je pense que le terme couverture irredondante vient juste d'une communauté différente mais désigne bien problème de couverture par ensembles. Mais l'article problème de couverture par ensembles ne semble pas être assez clair, si tu as du temps je suis preneur de critiques.--Roll-Morton (discuter) 17 février 2015 à 14:21 (CET)

D'une part je crois qu'il vaut mieux conserver, pour le problème de la couverture exacte, un article différent de celui sur les partitions (questions combinatoires, algorithmiques pour le premier ...), et des autre problèmes (algo différents).

D'autre part probablement "couverture irredondante" et "couverture par ensembles" paraissent liés. Ici cette histoire de moyens (ça se ramène toujours à des ensembles ?) n'est pas lumineuse. Là bas c'est plus clair, mais l'introduction ne correspond pas exactement à l'énoncé formel donné ensuite (évidemment c'est très lié, taille minimum / taille donnée). Il devrait être plus clair qu'il peut y avoir plusieurs solutions de cardinal minimum. Si je comprends bien, ici c'est la recherche d'une solution minimale (pour l'inclusion), là bas d'une solution de "taille" (taille n'étant définie qu'indirectement ensuite comme le nombre de sous-ensembles) donnée ou de taille minimale. Une solution peut être minimale pour l'inclusion sans être de taille minimale. Toute solution de taille minimale (en étendant aux définitions avec des poids) est minimale pour l'inclusion. Donc les problèmes sont liés mais un peu différents, je ne sais pas si ça a une incidence suffisante, du point de vue algo en particulier, pour mériter deux articles. Proz (discuter) 17 février 2015 à 23:09 (CET)

Hum oui, j'ai encore lu l'article trop en diagonale. En effet il est ici question de couverture minimale pour l'inclusion. Donc un concept a priori différent. Ok. La question est maintenant de trouver des sources pour cet article, de voir si il est plus question de combinatoire ou d'algorithmique, et de décider si cette appellation est assez notoire pour avoir son article.

Pour ce qui est de couverture par ensemble, je vais essayer de l'améliorer dans les prochains jours.

Pour couverture exacte, je pense en effet qu'il faut garder l'article, c'est une appellation classique pour un problème algorithmique connu.--Roll-Morton (discuter) 18 février 2015 à 10:41 (CET)

Eclaircissement(s)(?)

Bonjour. Merci pour votre discussion.

1. Cette page s'intéresse aux couvertures telles que aucun de leurs ensembles n'est contenu dans l'union des autres, i.e. telles que chaque ensemble soit nécessaire au titre d'au moins 1 point.

C'est le prélude à la recherche d'une couverture optimale. Chaque ensemble étant censé avoir un coût strictement positif, chaque couverture optimale est donc, par l'absurde, nécessairement irredondante en ce sens.

L'optimisation s'achève en fonction du coût de chaque couverture irredondante, dépendant du coût de chaque ensemble.

On n'exige pas que les ensembles soient disjoints, le coût d'un ensemble n'étant pas forcément une fonction monotone du nombre de points couverts.

En Décimal Codé Binaire, (0, 1, 2, 6) =(0000, 0001, 0010, 0110) = (000*, 00*0, 0*10)

Dans un cadre booléen, la somme de 4 produits de 4 variables est plus chère que la somme de 3 produits de 3 variables, et la seconde couverture est ici préférable.

Au-delà, on aura même (0, 1, 2, 6) =(000*, 00*0, **10) si on est certain de l'impossibilité des codes 10 = (1010) et 14 = (1110). La présence du poids 2 et l'absence du poids 0 suffit alors à détecter les codes 2 et 6, et les non-codes 10 et 14, dont on exploite l'absence en ne tenant plus compte du poids 8. Ce genre d'optimisation phi-booléenne fournirait une troisième couverture encore moins onéreuse.

2. Ma terminologie est celle de l' Algèbre de Boole de J. Kuntzmann (IMAG, 1965-1980).

3. Ceci dit, quelles sont les améliorations les plus urgentes ?

--Lf69100 (discuter) 6 mai 2015 à 16:28 (CEST)

 Lf69100 : A la lecture d débat ci-dessus, ce serait bien d'éclaircir certaines choses, par ex. l'usage du vocabulaire (pour moi ce qu'est un "moyen" n'est pas clair à la première lecture par ex.) qui n'est pas usuel partout, ou de donner des équivalences. Proz (discuter) 26 mai 2015 à 23:30 (CEST)

Nouveau Commentaire

0 - J'ai un peu rerédigé.

1 - Etant donné les éléments 1,2,3,4,5 et les ensembles (1,2,3)(3,4,5)(4)(5),

la couverture ((1,2,3)(3,4,5)) est licite et c'est même la meilleure couverture, au sens où elle utilise le moins d'ensembles.

Pour le problème de la couverture exacte, la seule solution licite est ((1,2,3)(4)(5)).

Pour le problème de la couverture irredondante, les solutions sont ((1,2,3)(3,4,5)) ET ((1,2,3)(4)(5)) MAIS PAS ((1,2,3)(3,4,5)(4)(5)). Les coûts ou poids attachés à chaque ensemble couvrant permettront de décider laquelle est optimale :

soit ((1,2,3)(3,4,5)) ou ((1,2,3)(4)(5)), selon le coût relatif de (3, 4, 5) et de ((4) (5)).

On ne peut aller plus loin sans remonter au problème-cadre (tournée, synthèse de circuit logique...), qui impose sa hiérarchie des coûts.

2 - Outre la méthode tabulaire, on donne une méthode basée sur la réduction par absorption d'un polynôme exprimant la réalisation de la couverture

3 - La méthode s'étend au cas où on a (a) des points à couvrir (b) des points à ne pas couvrir (c) des points indifférents, annexables si besoin pour optimisation. L'ouvrage de Kuntzmann est orienté calcul booléen en vue de l'électronique digitale, pour la synthèse de fonctions éventuellement complexes, mais pas forcément totalement définies (ex: circuiterie pour arithmétique décimale codée binaire).

4 - Hiérarchiser les méthodes de couverture pourrait supposer une table d'orientation des lecteurs.

5 - Comment rédiger (terminologie, exemples) pour que les pages mathématiques Wiki soient attractives ?

Lf69100 (discuter) 11 septembre 2015 à 11:44 (CEST)

bandeau à sourcer ?

Je ne pense pas que ce bandeau soit adéquat puisque la source est bien indiquée, et qu'il ne doit pas y avoir de souci à trouver ce qui se rapporte à l'article (qui est court). Proz (discuter) 26 mai 2015 à 23:32 (CEST)

Proz (d · c · b) {{source(s) à lier p-e? Fou de bassan / ^{Argument(s) ?} 26 mai 2015 à 23:36 (CEST)

A dire vrai je pense que le problème est plutôt de faire le lien avec le reste, parce que ces choses sont traitées dans des domaines avec des traditions différentes, et vocabulaires différents (algèbre de Boole /électronique, théorie des graphes, logique ...) et que les gens ne se comprennent pas toujours bien entre eux. Donc "source à lier" (même si ce serait mieux plus tard qu'elles le soient) ne me semble vraiment pas essentiel. Personnellement je préfère ce genre de bandeau quand il y a vraiment un problème potentiel (là en plus j'ai l'impression que Lf69100 connait le sujet). Proz (discuter) 26 mai 2015 à 23:48 (CEST)

Proz (d · c · b)

1. -"très exagéré" Fou de bassan / ^{Argument(s) ?} 26 mai 2015 à 23:49 (CEST)