Licence Info Algorithmique Avancée TD 7 : novembre 2006 Nombres aléatoires

On suppose qu’une fonction rand() est disponible qui retourne un entier pseudo-aléatoire distribué uniformément dans [0...N).

1. Ecrire une fonction randint(a,b) qui retourne un entier distribué à peu près uniformément dans [a...b], (a b sont des entiers).

fonction randint(val a,b : entier):entier;
var n:entier;
debut
   n:=N/(b-a+1); /*arrondi a l'entier plus bas*/
   retourne(a+rand()/n);
fin
finfonction

2. On veut donner à une variable i une valeur entre 1 et m de telle façon que la probabilité que i prenne une valeur j est p_{j}; les probabilités p_{j} ont été calculées et stockées dans un tableau P et, bien sûr, leur somme est 1. Ecrire une procédure qui effectue cette opération le plus efficacement possible.

procédure choisir(ref P:tab; ref i:entier);
var x:réel;
   début
   x:=(rand()+0.0)/N);
   i:=1;
   tantque i<m ET x>P[i] faire
/* test i<m nécessaire en raison d'arithmétique réelle inexacte*/
      x:=x-P[i];
      i:=i+1
   fintantque;
finprocédure;

Dans les deux exercices qui suivent, on veut construire un graphe aléatoire, non-orienté et régulier (tous les sommets ont le même degré d), sur l’ensemble de sommets 1...2n. Ce graphe peut être représenté par une matrice d’adjacence ou par une autre représentation plus compacte.

3. le cas d = 1 (a) Donner une fonction qui construit un graphe régulier de degré 1

(c’est-à-dire un couplage parfait) ;

procedure couplage(val n:entier; ref Tableau: C);
var i, j, posj, compteur, restant:entier;
var DISP: Tableau 1..2*n de entier;
debut
   pour compteur allant de 1 a 2*n faire
      DISP[compteur]:=compteur;
   restant=2n;
/* les nombres restant disponibles sont dans DISP entre [1] et [restant]*/
   pour compteur allant de 1 a n faire
      i:=DISP[restant];
      restant:=restant-1;
      posj:=randint(1,restant);
      j:=DISP[posj];
      DISP[posj]:=DISP[restant];
      restant=restant-1;
      /*signaler en C que i et j sont couples*/
      C[j]:=i;
      C[i]:=j;
   finpour;
fin
finprocedure

(b) Votre fonction construit-elle tous les graphes possibles avec la même probabilité ? Réponse: Oui (si on suppose que randint est uniforme)

4. le cas d > 1

(a) Si d > 1 on peut essayer d’utiliser un algorithme à rejet ; on construit d couplages parfaits et, dans le cas où ça ne donne pas un bon graphe (parce que deux de ces couplages contiennent une même arête), on abandonne cet essai et recommence du début. Donner une fonction qui applique une méthode de ce type.

procedure graphe(val n, d: entier; ref Tableau2D: G);
var reussi: booleen;
var coup, i, coup2: entier;
debut
   repeter
      pour coup allant de 1 a d faire
         couplage(n,G[coup]);
      finpour;
      reussi:=vrai;
      pour i allant de 1 a 2*n-1 faire
         /* reussi = faux si i a le meme partenaire en deux couplages*/

         pour coup allant de 1 a d-1 faire
            pour coup2 allant de coup+1 a d faire
               si G[coup][i]=G[coup2][i] alors
                  reussi:=faux;
               finsi;
            finpour;
         finpour;
      finpour;
   jusqu'a reussi finrepeter;
fin
finprocedure
/*il serait plus efficace de sortir des boucles des qu'un
sommet a le meme partenaire en deux couplages*/

(b) Votre fonction construit-elle tous les graphes possibles avec la même probabilité ? Réponse Non. Même pour d = 2 il y a des graphes qui ne se construisent pas par l’union de d couplages, et qui, donc, ont probabilité 0; par exemple le graphe à 6 sommets et arêtes (1, 2), (2, 3), (3, 1), (4, 5), (5, 6), (6, 4).

(c) Démontrez que, pour la valeur d = 2, le nombre moyen d’essais reste borné quand n tend vers l’infini. Réponse Le nombre moyen d’essais est le réciproque de la probabilité de réussite à chaque essai; donc, il suffit de démontrer que cette probabilité est supérieure à c pour tout n et pour c > 0 indépendant de n. La probabilité d’échec à un essai est inférieure (ou égale) au nombre d’arêtes communes aux deux couplages; chaque couplage a n arêtes parmi les 2n(2n − 1)/2 paires de sommets; donc chaque arête du premier couplage a probabilité 1/(2n − 1) d’être aussi dans le deuxième. on conclut que la probabilité d’échec est au plus n/(2n − 1) et (sauf le cas trivial n = 1) la probabilité de réussite est au moins 1/3; Finalement le nombre d’essais reste inférieur à 3 quand n tend vers l’infini.