Licence Info
Algorithmique Avancée
TD 8 : 15-16/11/04
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).

    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.

  2. 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é ?
  3. 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.



File translated from TEX by TTH, version 3.05.
On 16 Nov 2004, 10:58.