Probleme de dénombrement

par **scelerat** » 18 Aoû 2006, 18:53

scelerat a écrit:Je suis quasiment sur que le nombre est min(M-1, K-1) comme indique precedemment.

Je n'en suis plus sur du tout, j'ai meme un contre-exemple :happy2:
Le contre-exemple est assez instructif : on prend le milieu du domaine et les fonctions decroissantes du coin en haut a gauche au milieu, on les complete par symetrie par rapport au milieu, on a deja autant de fonctions non-dominees que de fonctions decroissantes sur (M/2, K/2).

par **Patastronch** » 18 Aoû 2006, 19:31

scelerat a écrit:Je n'en suis plus sur du tout, j'ai meme un contre-exemple :happy2:
Le contre-exemple est assez instructif : on prend le milieu du domaine et les fonctions decroissantes du coin en haut a gauche au milieu, on les complete par symetrie par rapport au milieu, on a deja autant de fonctions non-dominees que de fonctions decroissantes sur (M/2, K/2).

Oui c'est la voix que j'avais exploré comme je le disais avant. Mais rien ne garantit qu'on construit un maximum, et le résultat est polynomiale. Donc je peux minorer polynomialement, mais je cherche a majorer polynomialement (ou a minorer avec une fonction non majorable par un polynome). Donc a moins de prouver que cette configuration avec la symétrie est maximale, ca ne m'avait mené nul part.

Par contre je ne comprends pas ce que tu entends par :

"on a deja autant de fonctions non-dominees que de fonctions decroissantes sur (M/2, K/2)"

Pourquoi on a une égalité ?

par **scelerat** » 19 Aoû 2006, 11:26

Patastronch a écrit:Oui c'est la voix que j'avais exploré comme je le disais avant. Mais rien ne garantit qu'on construit un maximum, et le résultat est polynomiale.

Comment ca polynomial ?
Le nombre de fonctions decroissantes sur ([1,K/2],[M-M/2,M]) est sauf erreur un truc non polynomial, comme ca a ete dit dans cette discussion. Je complete chaque fonction decroissante sur ([1,K/2],[M-M/2,M]) par sa symetrique par rapport au milieu du rectangle (K,M). J'ai un ensemble de courbes decroissantes sur (K,M), de cardinal non-polynomial, et qui se croisent toutes au meme point : le centre du rectangle.

Patastronch a écrit:Par contre je ne comprends pas ce que tu entends par :

"on a deja autant de fonctions non-dominees que de fonctions decroissantes sur (M/2, K/2)"

Pourquoi on a une égalité ?

Si on prend deux quelconques de ces fonctions, elles sont distinctes sur le premier petit rectangle, donc il y a au moins un point ou l'une est superieure a l'autre, et par la symetrie qui a servi a les construire, l'autre est forcement superieure a l'une au point symetrique par rapport au milieu dans le second petit rectangle. L'ensemble est un donc jeu de fonctions non-dominees. Il n'est peut etre pas maximal, mais il est deja non-polynomial.

par **Patastronch** » 19 Aoû 2006, 13:09

scelerat a écrit:Comment ca polynomial ?
Le nombre de fonctions decroissantes sur ([1,K/2],[M-M/2,M]) est sauf erreur un truc non polynomial, comme ca a ete dit dans cette discussion. Je complete chaque fonction decroissante sur ([1,K/2],[M-M/2,M]) par sa symetrique par rapport au milieu du rectangle (K,M). J'ai un ensemble de courbes decroissantes sur (K,M), de cardinal non-polynomial, et qui se croisent toutes au meme point : le centre du rectangle.

Il n'y en a pas autant que de fonctions décroissantes, voir ci apres.

scelerat a écrit: Si on prend deux quelconques de ces fonctions, elles sont distinctes sur le premier petit rectangle, donc il y a au moins un point ou l'une est superieure a l'autre, et par la symetrie qui a servi a les construire, l'autre est forcement superieure a l'une au point symetrique par rapport au milieu dans le second petit rectangle. L'ensemble est un donc jeu de fonctions non-dominees. Il n'est peut etre pas maximal, mais il est deja non-polynomial.

Tu dis que toutes courbes differente sont non Dominée 2 à 2. C est pas pareil. Je peux avoir A et B non dominées entre elles, B et C non dominées entre elle, mais C qui domine A. Donc l'ensemble final ne sera pas A,B,C mais B et C (la relation de non dominance n'est pas transitive). Ce n'est pas parcequ'une courbe est non dominée par un sous-ensemble de courbes qu'elle sera non dominée dans tous l'ensemble optimal de courbe.

Pour etre sur qu'elle soit non dominée, elle doit etre maximal dans cette partie pour au moins une valeur sur K (car par conséquent elle sera minimal dans l'autre partie) ce qui impliquera qu'elle croisera toutes les autres courbes. Je ne sais pas si je suis assez clair.
et le nombre de courbes étant maximale pour une valeur entre 1 et K et minimal entre 1 et K, est K-2. Rien de plus polynomial (sauf erreur de ma part).

Cependant, bien que le critère d'etre maximal au moins une fois et etre minimal au moins une fois implique la non dominance dans l'ensemble, autant un non dominée pourait ne pas etre maximal (ou minimal) un seule fois. Je n'ai pas une équivalence du tout.

Donc j'avais fait une autre approche par construction. Chaque courbe qu'on ajoute dans l'ensemble doit etre supérieur a toutes les courbes précdentes, et par symétrie sera donc inférieur a toutes les courbes précédente et l'ensebmle final sera un ensemble de non dominés. Ce dénombrement (que je n'ai plus sous la main mais que je pourais retrouver si vous voulez) était également polynomial pour ma méthode d'ajout des courbes.
Le tout est de trouver comment ajouter les courbes une par une pour s'assurer que l'ensemble final soit de cardinal maximal.

par **Bouchra** » 21 Aoû 2006, 12:41

Bonjour,
Est-ce que par ex pour 3*3 la courbe :
.
.

.

.

est dominée par :

.

.

.

?

par **aviateurpilot** » 21 Aoû 2006, 12:59

:we: oui :we:

par **Bouchra** » 21 Aoû 2006, 20:37

D'accord, merci.

par **scelerat** » 27 Aoû 2006, 16:05

Patastronch,
Je ne pense pas que tu aies lu avec attention la construction que je propose, ni que tu aies fait le dessin.
En tout cas, si dans un ensemble de courbes, quelle que soit la paire que l'on choisit, aucune des deux courbes ne domine l'autre, je ne vois pas comment il pourrait y exister une courbe dominee.

par **scelerat** » 27 Aoû 2006, 16:22

Pour essayer de faire comprendre le contre-exemple sans un dessin complet, je montre un ensemble de courbes decroissantes au sens large toutes non-dominees :
[FONT=Courier New]
1111....
2222....
3333....
4444....
55555555
....4444
....3333
....2222
....1111
[/FONT]
Les courbes 1,2,3,4,5 sont toutes decroissantes, et aucune n'est dominee.

par **Patastronch** » 27 Aoû 2006, 16:32

scelerat a écrit:Patastronch,
Je ne pense pas que tu aies lu avec attention la construction que je propose, ni que tu aies fait le dessin.
En tout cas, si dans un ensemble de courbes, quelle que soit la paire que l'on choisit, aucune des deux courbes ne domine l'autre, je ne vois pas comment il pourrait y exister une courbe dominee.

Oui tu as raison, j'avais mal pigé l'idée. Ca m'a l'air juste (puisque toutes courbes majorées dans le premier carré seront minorées dans le second par symétrie centrale), et ca permet de minorer le maximum de courbes par une fonction non majorable par un polynome.

Probleme résolu haut la main. L'idée est simple mais fallait y penser !

Merci !

par **scelerat** » 28 Aoû 2006, 09:25

Patastronch a écrit:L'idée est simple mais fallait y penser !

Oui, a tel point que j'ai longtemps cru au contraire !

Probleme de dénombrement

Qui est en ligne