Randomisation

Qu'un algorithme ait une complexité moyenne satisfaisante n'est pas une garantie absolue d'efficacité. D'abord, parce que les données ne vérifient pas nécessairement l'hypothèse d'uniformité à partir de laquelle cette complexité moyenne a été calculée. Ensuite, l'algorithme n'est pas toujours destiné à être utilisé sur un grand nombre de données, parmi lesquelles les cas extrêmes seraient statistiquement minoritaires : un utilisateur peut systématiquement employer l'algorithme sur des mauvais cas. C'est la situation d'un jeu qui oppose le programmeur et un utilisateur malicieux de l'algorithme : le programmeur cherche à minimiser le temps d'exécution et l'utilisateur à le maximiser (pour prouver au programmeur qu'il est incompétent). Les techniques de randomisation assurent que l'utilisateur malicieux ne peut pas gagner : comme les conditions d'uniformité sont effectivement réalisées (et pas seulement supposées), les cas extrêmes sont garantis rares, inconditionnellement. Les algorithmes randomisés sont stochastiques.

Une première technique consiste à brasser le tableau au début de l'algorithme en lui appliquant une permutation aléatoire (les n!permutations doivent être équiprobables). Cette technique est évidemment correcte pour un problème de tri, mais s'applique difficilement à d'autres types de problèmes.

L'autre technique a un champ d'applications plus large. Il arrive souvent qu'à une certaine étape d'un algorithme, un choix soit à faire entre plusieurs opérations (dans le tri rapide, il s'agit du choix du pivot) a priori équivalentes. Quand ce choix a été figé dans un algorithme déterministe, il se trouve que c'est un bon choix pour certaines données, et que c'est un mauvais choix pour d'autres. Un algorithme randomisé fera ce choix au hasard. Voici comment randomiser la fonction partition() du tri rapide :      

  int randomPartition(int m, int n) {
    int p = irand(m, n);
    échangerÉléments(m, p);
    return partition(m,n);
  }

Il suffit de remplacer dans triRapide() l'invocation de partition() par une invocation de randomPartition.

Une autre application est le hachage universel : au lieu de choisir à l'avance une fonction de hachage qui risque de se révéler mauvaise (en termes de collisions) pour certaines applications, on tire au hasard, pour chaque application, une fonction dans une famille de fonctions de hachage. On dit qu'une famille $\mathcal{H}$ de fonctions d'un univers U de clés vers l'intervalle [0,m-1] est universelle si pour toutes les clés x et $y\not= x$, le nombre de fonctions $f\in \mathcal{H}$ telles que f(x)=f(y) est $\vert\mathcal{H}\vert/m$. Il est facile, avec très peu d'arithmétique, de vérifier que la famille suivante est universelle. Soit p tel que toute clé x puisse être décomposée en p+1 entiers x₀, ..., x_p dans l'intervalle [0,m-1] ; la famille $\mathcal{H}$ est composée des fonctions $f_{\alpha}(x) = \sum_{i=0}^p \alpha_ix_i \mathop{\normalfont\mathrm{mod}}\nolimits m$, où $\alpha = (\alpha_0,\ldots, \alpha_p) \in [0,m-1]^{p+1}$. L'algorithme de hachage universel consiste à tirer $\alpha$ aléatoirement et à utiliser $f_{\alpha}$ comme fonction de hachage (il est bien sûr indispensable de stocker $\alpha$ avec la table pour les opérations ultérieures de recherche).

Les algorithmes randomisés sont appelés algorithmes de Sherwood par G. Brassard et P. Bratley, en hommage à Robin des Bois, qui pratiquait une redistribution équitable des richesses.