Cours Algorithme : Les Fonctions sur les nombres

- Génération de nombres.
- Génération des structures.
- Algorithmes probabilistes.
 
   

1 Fonctions sur les nombres

  

1.1 Les nombres aléatoires

   

Il est souvent utile d'avoir une fonction qui produit des nombres apparemment aléatoires. La fonction rand() prédéfini peut faire se genre d’opération. A chaque fois qu’elle est appelée, elle donne un nombre différent (normalement en [0..N]). En réalité, elle n’est pas vraiment aléatoire mais on considère statistiquement que le résultat est convenable. 

  

1.2 Génération de nombres

  

L’algorithme suivant permet de générer des entiers de manière pseudo-aléatoires. Soient x1,...,xi,... : 

  

• On effectue un calcul simple comme xi+1 = xi*m  + c  (mod  N) pour m bien choisi et N une puissance de 2.

• On divise par N pour un réel aléatoire en [0..1]

• On multiplie ensuite par R pour un réel en [0..R]

• Et on arrondit pour un entier en [0..R?1]

  

Attention toutefois : prendre xi mod. R est très mauvais si R est une puissance de 2!! 

  

1.3 Génération de structures

 

La génération de structure consiste :

 

• Soit à générer un entier dans un bon intervalle et le décoder

• Soit à générer la structure itérativement avec un entier généré chaque fois que l'algorithme doit prendre une décision .

  

La deuxième méthode plus facile à programmer et évite problèmes d'entiers trop grands.

  

Utilisation 0: interface avec l'extérieur

   

• programme de jeu: pour ne pas toujours jouer pareil

• joli écran

• réseau: attendre un temps aléatoire avant de réessayer un transfert après une collision.

    

Utilisation 1: tester un algorithme

    

• Générer un jeu de tests sur les cas aléatoires (Ne remplace pas les tests systématiques qui utilisent chaque branche du programme)

  

Attention, se rappeler que :

  

• « Tester ne prouve jamais qu'un programme est sans fautes »

• Sauf pour ceux avec un nombre fini (et petit) de données possibles 

  

Utilisation 2: calcul numérique de statistiques

  

On peut donner plusieurs exemples d’applications dans ce domaine :

   

• Calculer la superficie moyenne du polygone défini (enveloppe convexe) par 10 points choisis aléatoirement dans le carré [0,1][0,1].

• Générer, disons 1000, cas aléatoires et calculer la superficie de chacun 

Attention, cette utilisation peut être :

  

• dangereuse : car très faible probabilité qu’on soit loin du vrai moyen.

• très dangereuse : si la distribution est très bizarre (écart type très grand), presque certain d'être loin du vrai moyen. 

  

Utilisation 3: Simulation de processus (naturels ...)

 

Exemples : 

  

• Propagation d'une maladie

• Effet sur la circulation si l’on modifie une route

• Résilience d'un réseau à des pannes

• Comportement d'une bourse où des commandes de ventes ou d'achats sont générées par des logiciels 

  

En fait, cette technique peut être utilisé partout où la complexité des interactions entre les composants d'un système exclut tout calcul direct. 

   

Utilisation 4: algorithmes probabilistes

Quelques exemples :

   

• Algorithmes de calcul exact qui utilisent des choix aléatoires

• Algorithmes calculant une probabilité d'échec (mais, souvent, ils reconnaissent qu'un échec est arrivé). 

 

Donc, répéter plusieurs fois un évènement (avec choix différents) réduit exponentiellement la probabilité d'échec 

-------------------------------------------------------------------------------------------------------
Précédent : Les Structures Complexes
  
                       Suivant : Complexité des algorithmes