Algorithme de tri sans stratégie

[ilialion]

Bonjour

J'aimerais bien que l'on m'aide pour résoudre cet exercice.

Considérons l'algorithme de tri suivant :

10 i = 1, u = 0

20 Enregistrer l'individu w

30 Tant que u = 0, faire :

40 Si w appartient à Ci, ranger w dans le fichier Fi et faire u = 1

50 i = i + 1

60 Fin tant.

70 Fin


Où les individus w sont tirés au hasard dans une population divisée en n catégories C1, C2,...., Cn disjointes : la proposition d'individus de catégorie C indice i dans la population est notée pi. Soit X(w) le numéro de la catégorie à laquelle appartient l'individu w et T(w) le temps nécessaire à la machine pour ranger w. Montrer que T est une fonction affine croissante de X (posons T = aX + b);
l'espérance de X dépend-elle de l'ordre dans lequel sont numérotés les catégories ? Calculer la valeur la plus défavorable (resp la plus favorable) de E[X] si n = 3 et
{p1,p2,p3} = {0.1;0.6;0.3}.

[maturin]

b correspond au temps de calculs pour faire les étapes 10, 20 et 70 (que tu fais une fois)
a correspond au temps de calcul pour faire la boucle "tant".

E(X) = somme ( i*pi) avec pi proba que X soit dans Ci.
donc si tu range tes catégorie par taille décroissante (proba decraoissante) ton espérance sera plus faible (i.e. plus favorable). Et inversement si tu ranges dans l'autre sens.

[ilialion]

Merci bcp, mais pouvez vous détaillé encore plus la démonstration.

b correspond au temps de calculs pour faire les étapes 10, 20 et 70 (que tu fais une fois)
a correspond au temps de calcul pour faire la boucle "tant".

E(X) = somme ( i*pi) avec pi proba que X soit dans Ci.
donc si tu range tes catégorie par taille décroissante (proba decraoissante) ton espérance sera plus faible (i.e. plus favorable). Et inversement si tu ranges dans l'autre sens.

[maturin]

alors si on suit ton algorithme on va faire les étapes:
10
20
30
40
50
60
30
40
50
60
...
30
40
50
60
70
on boucle entre 30 et 60 autant de fois qu'il le faut pour trouver la bonne catégorie.
Si tu appelles a le temps de calcul des opérations 30 à 60 et b le temps de calcul des opérations 10+20+70 tu trouveras bien la formule.


Après au niveau des proba, si tu appelles pi la proba d'être dans la catégorie Ci alors tu auras la proba p1 d'être dans la catégorie C1 et donc de faire une fois la boucle, la proba p2 de faire 2 fois la boucle...
Ton espérance de nombre de boucle est donc E(X)=1*p1+2*p2+...=somme(i*pi)