Heuristiques et recherche locale itérative

Nous proposons maintenant une implémentation du programme qui, étant donné un graphe orienté \(G\) et un nœud \(v\) de ce graphe, calcule l'ensemble des nœuds atteignables à partir de \(v\).

Nous utiliserons le langage C++11.

# code block: build_gdb.sh

g++ -std=c++11 -g "$1.cpp" -o "$1"

# code block: build.sh

g++ -std=c++11 -O3 "$1.cpp" -o "$1"

Nous utiliserons la librairie STL. Le programme sera introduit au moyen du paradigme literate programming.

// code block reachable-include

#include <iostream>
#include <vector>
#include <set>

using namespace std;

Chaque nœud porte une valeur entière et une liste de voisins directs.

// code block reachable-struct-node

struct
node
{
  int val;
  vector<node*> nei;
};

Nous utilisons le même graphe exemple que celui dessiné plus haut.

// code block reachable-example

struct node n1; n1.val = 1;
struct node n2; n2.val = 2;
struct node n3; n3.val = 3;
struct node n4; n4.val = 4;
struct node n5; n5.val = 5;
struct node n6; n6.val = 6;
n1.nei.insert(n1.nei.begin(), &n2);
n1.nei.insert(n1.nei.begin(), &n3);
n2.nei.insert(n2.nei.begin(), &n4);
n4.nei.insert(n4.nei.begin(), &n3);
n4.nei.insert(n4.nei.begin(), &n5);
n5.nei.insert(n5.nei.begin(), &n2);
n5.nei.insert(n5.nei.begin(), &n6);

Le code principal affichera simplement la liste des noeuds atteignables à partir d'un noeud source.

// code block: reachable.cpp

  <<reachable-include>>
  <<reachable-struct-node>>
  <<reachable-algo>>

  int
  main()
  {
    <<reachable-example>>

    for( node* n : a(&n4) )
    {
      cout << n->val << " ; ";
    }
    cout << endl;

    return 0;
  }

Nous calculons la fermeture de la relation de voisinage avec l'algorithme dérivé plus haut.

// code block reachable-algo

set<node*>
a( node* src )
{
  set<node*> x;
  set<node*> y;
  y.insert(src);                      // the source is initially grey

  while( !y.empty() )
  {
    set<node*>::iterator u = y.begin();

    for( node* n : (*u)->nei )        // n is in the successors of y
    {
      if( (x.end() == x.find(n)) &&
          (y.end() == y.find(n)) )    // n is not in (x U y)
      {
        y.insert(n);                  // we still didn't see the succ of n
                                      // thus, it is a grey node
      }
    }

    x.insert(*u);                     // the node u of y is now white
    y.erase(u);
  }

  return x;
}

Nous avons par exemple :

En utilisant pour \(y\) (la structure qui contient les nœuds rencontrés mais dont les successeurs n'ont pas encore été calculés) une structure de file FIFO (First In First Out) au lieu d'un ensemble, nous obtenons le programme de recherche en largeur dans un graphe.

Nous utilison la structure de file (queue) de la STL.

// code block breadth-include

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <functional>
#include <limits>

using namespace std;

Nous suivons le schéma de l'algorithme générique atteignable dérivé plus haut.

// code block breath-algo

typedef function<void(node*)> Visitor;

void
breadth( node* src, Visitor f )
{
  set<node*> x;                   // in the end x has only white nodes
                                  // during the process, it also stores
                                  // the grey nodes

  queue<node*> y;                 // y is the queue (FIFO) of grey nodes

  y.push(src);
  x.insert(src);

  while( !y.empty() )             // there are still grey nodes
  {
    node* u = y.front();          // u is the 'oldest' element of y

    f(u);                         // visit u

    for( node* n : u->nei )       
    {
      if( x.end() == x.find(n)){ // n is a black successor of u
        y.push(n);               // n becomes grey
        x.insert(n);             // n will be white once removed from y
      }
    }

    y.pop();                      // u is now white
  }
}

Ci-dessous un résultat possible pour un parcours en largeur sur l'exemple précédent en partant du nœud 1 comme source. Nous utilisons un visiteur trivial :

// code block breadth-visit

Visitor visit = [](node* v){
  cout << v->val << " ; ";
};

L'algorithme de recherche en largeur permet de trouver les plus courts chemins d'un nœud source aux autres nœuds du graphe dans le cas d'un graphe orienté pour lequel les arêtes ont toutes le même coût (ou poids) :

// code block breadth-dist

void
findDistances( node* src, map<node*,size_t>* distances )
{

  // local function used to return infinity when
  // for a node we didn't already find a distance

  function<size_t(node*)>
  distance = [distances]( node* v )
  {
    map<node*,size_t>::iterator distIt = distances->find(v);
    if( distances->end() == distIt )
    {
      return numeric_limits<size_t>::max();
    }
    return distIt->second;
  };

  Visitor
  visit = [distances, distance]( node* v )
  {
    // distance to the source is zero

    if( distances->empty() ) (*distances)[v] = 0;

    // update the shortest known distance to the
    // successors of the currently visited node

    size_t vDist = distance(v);

    for (node* n : v->nei)
    {
      size_t nDist = distance(n);
      (*distances)[n] = min( nDist, 1 + vDist );
    }
  };

  breadth(src, visit);
}

Le programme principal calcule les plus courtes distances au noeud source 1 sur notre exemple filé.

// code block: breadth.cpp

  <<breadth-include>>
  <<reachable-struct-node>>
  <<breadth-algo>>
  <<breadth-dist>>

  int
  main()
  {
    <<reachable-example>>
    <<breadth-visit>>

    breadth(&n1, visit);
    cout << endl;

    map<node*,size_t> distances;
    findDistances(&n1, &distances);

    for( map<node*,size_t>::iterator it = distances.begin() ;
         it != distances.end() ; it++ )
    {
      cout << it->first->val << " : " << it->second << " ; ";
    }
    cout << endl;

    return 0;
  }

Nous trouvons bien :

En utilisant pour \(y\) (la structure qui contient les nœuds rencontrés mais dont les successeurs ne sont pas encore calculés, les nœuds gris) une structure de pile LIFO (Last In First Out) au lieu d'un ensemble, nous obtenons le programme de recherche en profondeur dans un graphe.

Nous utilisons la structure de données stack de la STL.

// code block depth-include

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <functional>
#include <limits>

using namespace std;

Le programme principal affichera simplement les noeuds dans l'ordre de leur visite en partant du noeud 1.

// code block: depth.cpp

  <<depth-include>>
  <<reachable-struct-node>>
  <<depth-algo>>
  int
  main()
  {
    <<reachable-example>>
    <<breadth-visit>>
    depth(&n1, visit);
    cout << endl;
    return 0;
  }

// code block: depth-algo

typedef function<void(node*)> Visitor;

void
depth( node* src, Visitor f )
{
  set<node*> x; 
  stack< pair< node* , vector<node*>::iterator > > y; 

  y.push( { src, src->nei.begin() } );          // initially the source is grey
  x.insert(src);                                // x contains both the grey nodes
                                                // and the black nodes. In the end,
                                                // there are only black nodes.

  while( !y.empty() )                           // while there are grey nodes...
  {
    node* u = y.top().first;                    // u is the grey node we will make black 
                                                // by exploring his sons

    if( y.top().second != u->nei.end() )        // if u has still unexplored sons
    {
      node* next = *(y.top().second);           // next is a son of u
      ++(y.top().second);

      if( x.end() == x.find(next) )             // if this son of u is white
      {
        y.push( { next, next->nei.begin() } );  // it becomes grey
        x.insert(next);
      }
    }
    else                                        // u has no more unexplored sons.
    {
      f(u);                                     // we can visit u
      y.pop();                                  // u is now black and can be removed from y
    }
  }
}

Ci-dessous un résultat possible d'un parcours en profondeur sur l'exemple précédent en partant du nœud 1 comme source.

La recherche en profondeur s'écrit plus naturellement sous une forme récursive :

// code block depthrec-algo

typedef function<void(node*)> Visitor;

void
depthrec( node* src, Visitor f, set<node*>* x )
{
  (*x).insert(src);

  for( node* n : src->nei )
  {
    if( (*x).end() == (*x).find(n) )
    {
      depthrec( n, f, x );
    }
  }

  f(src);
}

void
depth( node* src, Visitor f )
{
  set<node*> x;
  depthrec(src, f, &x);
}

// code block depthrec.cpp

  <<depth-include>>
  <<reachable-struct-node>>
  <<depthrec-algo>>

  int
  main()
  {
    <<reachable-example>>
    <<breadth-visit>>

    depth(&n1, visit);
    cout << endl;

    return 0;
  }

Nous considérons un graphe dont chaque arête est étiquetée avec un nombre positif ou nul. Il s'agit de calculer pour chaque nœud du graphe sa plus courte distance à un nœud \(v\) fixé. La plus courte distance entre deux nœuds est la longueur du plus court chemin entre ces deux nœuds.

L'ensemble des nœuds noirs est l'ensemble des nœuds pour lesquels la plus courte distance à \(v\) a été établie. Un plus court chemin ne visite que des nœuds noirs.

L'ensemble des nœuds gris est l'ensemble des nœuds pour lesquels la longueur d'un chemin y menant depuis \(v\) a été trouvée, mais cette longueur n'est pas nécessairement minimale. Par contre, c'est la longueur minimale sur l'ensemble des chemins qui n'ont que des nœuds noirs entre \(v\) et ce nœud gris.

Au sujet des nœuds blancs, nous ne savons rien… sinon que tout chemin depuis \(v\) jusqu'à un nœud blanc doit d'abord passer par un nœud gris.

On note \(d[u]\) la distance associée à un nœud noir ou gris.

Comment choisir le prochain nœud gris que nous ferons passer à noir ?

Nous montrons que nous pouvons choisir un nœud gris \(u\) dont la distance à \(v\), notée \(d[u]\), (et qui est la longueur d'un chemin ne passant que par des nœuds noirs) est minimale parmi l'ensemble des nœuds gris.

Considérons un chemin quelconque de \(v\) à \(u\) et notons sa longueur \(l\). Ce chemin peut contenir d'autres nœuds gris et même des nœuds blancs.

Puisque \(v\) est noir et \(u\) est gris, à un moment donné ce chemin quitte la région noire.

Soit \(g\) le premier nœud non-noir (c-à-d gris) de ce chemin.

\(g\) peut être égal à \(u\) ou ne pas être égal à \(u\).

Puisque \(u\) a été choisi pour minimiser \(d[u]\), nous avons : \(d[u] \leq d[g]\).

Puisque la distance de \(g\) à \(u\) est positive ou nulle, nous avons : \(d[g] \leq l\).

D'où : \(d[u] \leq l\). Donc ce chemin est au moins aussi long que celui dont la découverte avait mené à la mémorisation de la valeur actuelle \(d[u]\).

Donc la longueur du plus court chemin de \(v\) à \(u\) est \(d[u]\), et le nœud \(u\) peut être coloré en noir.

Tous les successeurs blancs de \(u\) sont colorés en gris, et une distance est mémorisée pour chacun d'entre eux, faite de la plus courte distance de \(v\) à \(u\) (\(d[u]\) ) à laquelle on ajoute la distance de \(u\) à ce successeur.

Tous les successeurs gris de \(u\) restent gris, mais la distance qui leur est associée peut être réduite (si le chemin qui passe par u est plus court).

Pour les successeurs noirs de \(u\), il n'y a rien à faire.

D'où l'algorithme suivant :

La liste d'adjacence d'un noeud contient maintenant les poids des arêtes qui permettent d'atteindre les voisins de ce noeud :

// code block dijkstra-struct-node

struct
node
{
  int val;
  vector< pair< int, node* > > nei;
};

Nous utilisons à nouveau la bibliothèque standard du C++.

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <list>
#include <functional>
#include <utility>
#include <limits>

using namespace std;

L'implémentation de l'algorithme suit d'assez près le pseudo-code de notre dérivation. La différence principale réside dans l'utilisation d'une file de priorité, et dans le maintient d'une structure map< node*, node* > parent qui permet de reconstruire le chemin une fois la destination atteinte.

// code block dijkstra-algo

void
dijkstra( node* src, node* target, list<node*>* r )
{
  map< node*, node* > parent;
  parent[src] = src;

  map< node*, int> d;
  d[src] = 0;

  set<node*> x;

  priority_queue< pair< int, node* > ,
                  vector< pair< int, node* > >,
                  greater< pair< int, node* > > > y;

  y.push({0, src});
  x.insert(src);

  function<int(node*)>
  dist = [d]( node* v )
  {
    map< node*, int >::const_iterator it = d.find(v);
    if( d.end() == it )
    {
      return numeric_limits<int>::max();
    }
    return it->second;
  };

  while( !y.empty() )
  {
    node* u = y.top().second;

    // once the target found, we rebuild the path to it
    if( target == u )
    {
      r->clear();
      while( u != src )
      {
        r->push_front(u);
        u = parent[u];
      }
      r->push_front(src);
      return;
    }

    x.insert(u);  // u, the 'smallest' grey node, becomes black
    y.pop();

    for( pair< int, node* > n : u->nei )
    {
      if( x.end() != x.find(n.second) ) // if n is black, do nothing...
      {
        continue;
      }

      // We don't take into account as a special case the situation of
      // n already an element of y.
      // Indeed, the basic STL priority queue doesn't have
      // an increaseKey operation.
      // Therefore, we tolerate duplicates...
      // But really, we may prefer using a "better" structure...

      if( dist(n.second) > d[u] + n.first )
      {
        d[n.second] = d[u] + n.first;
        parent[n.second] = u;
        y.push( { d[n.second], n.second } );
      }
    }
  }
}

Nous mettons à jour notre petit exemple de graphe en ajoutant des poids aux arêtes :

// code block dijkstra-example

struct node n1; n1.val = 1;
struct node n2; n2.val = 2;
struct node n3; n3.val = 3;
struct node n4; n4.val = 4;
struct node n5; n5.val = 5;
struct node n6; n6.val = 6;
n1.nei.insert(n1.nei.begin(), { 1, &n2 });
n1.nei.insert(n1.nei.begin(), { 4, &n3 });
n2.nei.insert(n2.nei.begin(), { 1, &n4 });
n2.nei.insert(n2.nei.begin(), { 2, &n5 });
n4.nei.insert(n4.nei.begin(), { 1, &n3 });
n4.nei.insert(n4.nei.begin(), { 2, &n5 });
n5.nei.insert(n5.nei.begin(), { 1, &n6 });
n6.nei.insert(n6.nei.begin(), { 1, &n2 });

Nous testons, sur cet exemple, l'algorithme de Dijkstra pour la recherche d'un plus court chemin.

// code block dijkstra.cpp

  <<dijkstra-include>>
  <<dijkstra-struct-node>>
  <<dijkstra-algo>>

  int
  main()
  {
    <<dijkstra-example>>

    list<node*> r;

    dijkstra(&n1, &n3, &r);

    for( list<node*>::iterator it = r.begin() ;
         it != r.end() ; it++ )
    {
      cout << (*it)->val << " ; ";
    }
    cout << endl;
    return 0;
  }

Le résultat de la recherche du plus court chemin de 1 vers 3 donne bien :

La fonction \(h\) est appelée fonction heuristique.

Déf. Une heuristique \(h\) est admissible si pour tout nœud \(u\), \(h(u)\) est une borne inférieure de la plus courte distance séparant \(u\) de la cible \(t\), i.e. \(h(u) \leq \delta(u,t)\) (avec \(\delta(u,t)\) désignant la longueur d'un chemin optimal entre \(u\) et \(t\) ).

Déf. Une heuristique \(h\) est consistante si pour toute arête \(e = (u,v)\) nous avons \(h(u) \leq h(v) + w(u,v)\) (avec \(w(u,v)\) le poids de l'arête \((u,v)\)).

Déf. Soient \((u_0,\dots,u_k)\) un chemin et \(g(u_i)\) le coût du chemin \((u_0,\dots,u_i)\). Nous posons \(f(u_i) = g(u_i) + h(u_i)\). Une heuristique \(h\) est monotone si pour tout \(j>i, \; 0 \leq i, \; j \leq k\) nous avons \(f(u_j) \geq f(u_i)\). C'est-à-dire que l'estimation du poids total d'un chemin ne décroît pas lors du passage d'un nœud à ses successeurs.

Nous remarquons que consistance et monotonicité sont deux propriétés équivalentes. En effet, pour deux nœuds adjacents \(u_{i-1}\) et \(u_i\) sur un chemin \((u_0,\dots,u_k)\), nous avons :

L'autre implication (viz. monotonicité implique consistance) est triviale.

Aussi, une heuristique consistante est admissible (la réciproque n'est pas vraie). En effet, si \(h\) est consistante, pour toute arête \((u,v)\) nous avons \(h(u) - h(v) \leq w(u,v)\). Soit un chemin quelconque \(p = (v_0 = u,\dots,v_k = t)\), nous avons :

En particulier, dans le cas d'un plus court chemin : \(h(u) \leq \delta(u,t)\).

L'algorithme A* est un exemple d'amélioration de l'algorithme de Dijkstra grâce à l'utilisation d'une fonction heuristique. A* associe à un nœud \(u\) du graphe la valeur :

où \(g(u)\) est le poids optimal actuellement connu pour un chemin menant de \(s\) à \(u\), et \(h(u)\) est une heuristique admissible (i.e., une borne inférieure de la distance séparant \(u\) de la cible \(t\) ).

Nous remarquons que pour un nœud \(u\) gris minimal (au sens de \(f(u)\) ), nous avons pour tout successeur \(v\) de \(u\) :

Ainsi, l'algorithme A* correspond exactement à l'algorithme de Dijkstra avec la repondération suivante :

Si l'heuristique \(h\) est monotone alors tous les poids restent positifs et la preuve de correction de Dijkstra s'applique !

De plus, nous allons montrer que, dans le cas d'une heuristique monotone, il n'existe pas d'algorithme \(A\) qui trouve la solution optimale en explorant moins de nœuds que \(A^*\). Soit \(f^* = \delta(s,t)\) le coût de la solution optimale. Nous montrons que tout algorithme optimal (i.e., qui trouvera toujours la solution optimale) doit visiter tous les nœuds \(u\) pour lesquels \(\delta(s,u) < f^*\).

Travaillons par l'absurde en supposant qu'il existe un algorithme \(A\) qui trouve une solution optimale \(p_t\) (i.e., avec \(w(p_t) = f^*\) ) en ne visitant pas un nœud \(u\) pour lequel \(\delta(s,u) < f^*\). Montrons qu'il peut alors exister un autre chemin \(q\) avec \(w(q) < f^*\) qui n'est pas trouvé par A. Soit \(q_u\) le chemin tel que \(w(q_u) = \delta(s,u)\). Mettons qu'il existe une arête \((u,t)\) de poids \(0\) (i.e., \(w(u,t) = 0\) ). Puisque le voisinage de \(u\) n'a pas été exploré par \(A\), ce dernier ne peut pas savoir que l'arête \((u,t)\) existe. Soit le chemin \(q = (q_u,t)\). Nous avons : \(w(q) = w(q_u) + w(u,t) = \delta(s,u) < f^*\).

Plus une heuristique \(h(u)\) est proche de la valeur optimale \(\delta(u,t)\) plus elle est informée.

Plus une heuristique est informée, mieux elle minimise la taille de l'espace exploré, mais en général elle est également plus coûteuse en temps de calcul qu'une heuristique moins informée.

Prenons l'exemple simple du 8-puzzle dont on rappelle ci-dessous le voisinage :

Voici quelques exemples d'heuristiques ordonnées par degré d'information :

• nombre de chiffres mal placés
• somme des distances (de manhattan) des chiffres à leurs positions d'origine
• prise en compte des échanges entre cases voisines
• …

• heuristique breadth
  • 20 coups
  • 44696 nœuds explorés
• heuristique nbmis
  • 20 coups
  • 2877 nœuds explorés
• heuristique manh
  • 20 coups
  • 189 nœuds explorés

Sujet du TP2 au format PDF.

Vous devez implémenter la procédure SEARCH de l'algorithme \(IDA^*\) en partant du code source suivant : ida_tp.cpp. Dans la fonction main, vous trouverez décrites trois configurations initiales (C0, C1 et C2) que vous utiliserez pour vos expérimentations. Par ailleurs, vous utiliserez également le code source déjà développé en cours pour l'algorithme A* : taquin15.cpp. Vous devez répondre aux questions suivantes sur Moodle :

• Si A* ne parvient pas à résoudre le taquin à partir de C2, est-ce d'abord par manque…
  1. …de temps ?
  2. ou de mémoire ?
• La quantité de mémoire utilisée par A* est-elle linéairement proportionnelle…
  1. …à la taille d'un chemin solution ?
  2. …au nombre de solutions partielles de coût inférieur à la solution optimale ?
  3. …à la taille de l'espace d'états ?
• Combien de recherches en profondeur effectue IDA* pour résoudre le taquin à partir de C0 ?
• Combien de recherches en profondeur effectue IDA* pour résoudre le taquin à partir de C1 ?
• La quantité de mémoire utilisée par IDA* est-elle linéairement proportionnelle…
  1. …à la taille d'un chemin solution ?
  2. …au nombre de solutions partielles de coût inférieur à la solution optimale ?
  3. …à la taille de l'espace d'états ?
• Quelle est la longueur (en nombre d'actions) de la solution optimale pour C2 ?
• En comparaison avec une version de l'algorithme pour laquelle les voisins d'un état sont explorés dans un ordre quelconque, la version meilleur d'abord (explorant les voisins d'un état par ordre croissant de la valeur heuristique h) pourra explorer…
  1. …plus d'états ?
  2. …moins d'états ?
  3. …au moins autant d'états que ceux vus lors des premiers \(n-1\) parcours en profondeur (la solution étant trouvée au cours du \(n\)-ème parcours) ?

  Plusieurs réponses sont possibles.

L'approche de recherche locale itérative la plus naïve pour la résolution d'un problème combinatoire est le "hill-climbing" (similaire à la ``descente de gradient'' dans le cas de fonctions continues dérivables). Il s'agit de générer une solution initiale puis, tant que possible, se déplacer vers une solution voisine meilleure.

Le problème principal de cette approche est qu'un optimum local peut être très éloigné de l'optimum global.

Le recuit simulé ("simulated annealing") est un algorithme itératif qui apporte une solution au problème de l'attraction par les optimums locaux. Une solution voisine meilleure que la solution actuelle sera toujours acceptée. Une solution voisine moins bonne que la solution actuelle sera parfois acceptée selon la probabilité :

En thermodynamique, la probabilité de trouver un système dans un état d'énergie \(E\) à une température \(T\) est proportionnelle à \(e^{-\frac{E}{kT}}\) où \(k\) est la constante de Boltzmann (\(1.3896 \times 10^{-23}\) joule/kelvin). Le facteur de Boltzmann est le rapport entre deux états d'énergies \(E1\) et \(E2\): \(e^{-\frac{\Delta E}{kT}}\).

Par exemple, une molécule de gaz dans l'atmosphère terrestre a son plus bas niveau d'énergie au niveau de la mer. Son énergie augmente avec l'altitude. La probabilité de trouver la molécule 10 mètres au dessus du niveau de la mer est presque identique à celle de la trouver au niveau de la mer car \(\Delta E\) est très petit par rapport à \(kT\). Le ratio des probabilités de ces deux niveaux d'énergie est proche de 1. Mais quand l'altitude augmente, la différence des probabilités des niveaux d'énergie augmente. La probabilité de trouver la molécule à une haute altitude décroit exponentiellement avec l'augmentation linéaire de l'altitude. Par contre, si la température augmente, la probabilité de trouver une molécule à une haute altitude augmente également.

Ainsi, le recuit simulé débute avec une température élevée qui permet d'explorer de nombreuses solutions en s'échappant des minimums locaux. Un refroidissement progressif permet d'approcher une bonne solution de faible énergie.

Ci-dessous des graphes de cette distribution pour différentes valeurs de \(T\) (dessinés avec le langage J) : \(2\) en bleu, \(3,3\) en rouge et \(10\) en vert.

load 'plot numeric'
plot (; ^@*&0.3 , ^@*&0.5 ,: ^@*&0.1) steps _2 0 20

Nous commençons par introduire un générateur de nombres aléatoires classique qui sera utilisé pour l'implémentation de l'algorithme itératif du recuit simulé. Nous avons besoin d'un générateur qui respecte une distribution uniforme. Il s'agit par exemple de générer aléatoirement un nombre à virgule flottante sur l'intervalle \([0.0 .. 1.0]\) et chaque nombre doit être équiprobable.

Commençons par quelques remarques générales :

• Nous aurons besoin de l'implémentation d'opérations arithmétiques sur des valeurs codées avec 64 bits et non signées.
• Une notion clé sera la période du générateur qui ne devrait pas être inférieure à \(\text{~} 2^{64}\).
• Il ne faudra pas utiliser les implémentations par défaut des langages C, C++, Matlab, etc. (e.g., rand, srand, etc.) car leur implémentation n'étant pas standardisée, elles ne sont pas toujours d'une qualité suffisante (nous allons comprendre pourquoi…).