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).
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.
   

   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

   1. Donner une fonction qui construit un graphe régulier de degré 1 (c'est-à-dire un couplage parfait) ;
   2. Votre fonction construit-elle tous les graphes possibles avec la même probabilité ?
4. le cas d > 1

   1. 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.
   2. Votre fonction construit-elle tous les graphes possibles avec la même probabilité ?
   3. Démontrez que, pour la valeur d=2, le nombre moyen d'essais reste borné quand n tend vers l'infini.