Randomized algorithms

Reading time15 min

En bref

Résumé de l’article

Dans cet article, nous introduisons les algorithmes randomisés, qui utilisent l’aléa pour prendre des décisions, ce qui entraîne des variations potentielles dans l’exécution et le résultat entre différentes exécutions avec la même entrée. Ils sont classés en Monte-Carlo (qui fournit des résultats corrects avec une forte probabilité) et Las-Vegas (qui fournit toujours des résultats corrects mais avec des performances variables).

À titre d’exemple, nous étudierons l’algorithme de Frievald pour la multiplication de matrices, qui offre une approche randomisée efficace avec une complexité temporelle attendue de $O(n^2)$. Nous nous concentrerons sur un autre exemple, le fingerprinting, qui est une technique utilisée pour vérifier l’égalité des données avec un transfert minimal d’informations, en utilisant des fonctions de hachage aléatoires.

Les nombres aléatoires, essentiels pour les algorithmes randomisés, sont généralement générés par des méthodes pseudo-aléatoires, car la véritable aléa est difficile à obtenir. Nous discutons des défis liés à la génération de nombres aléatoires et de l’importance de propriétés telles que l’uniformité, l’indépendance et la reproductibilité dans la génération de nombres pseudo-aléatoires.

Principaux enseignements

  • Les algorithmes randomisés peuvent être plus efficaces et plus simples que les algorithmes déterministes mais n’offrent pas de garantie de correction, fournissant seulement une probabilité d’exactitude.

  • Générer des nombres aléatoires est complexe. Bien que générer de véritables nombres aléatoires soit difficile, les nombres pseudo-aléatoires sont largement utilisés dans les algorithmes. De bons générateurs de nombres pseudo-aléatoires doivent équilibrer rapidité, portabilité et uniformité.

Contenu de l’article

1 — Qu’est-ce qu’un algorithme randomisé ?

Commençons par donner la définition d’un algorithme probabiliste :

Un algorithme probabiliste est un algorithme qui génère un nombre aléatoire $r \in \mathbb{R}$ et prend une décision basée sur la valeur de $r$.

Notez que pour une même entrée sur différentes exécutions, un algorithme randomisé peut :

  • Effectuer un nombre différent d’étapes.
  • Produire un résultat différent.

Nous pouvons classer les algorithmes probabilistes en deux catégories :

  • Monte-Carlo – Ces algorithmes s’exécutent en temps polynomial, la sortie est toujours correcte avec une forte probabilité. Ils sont utilisés lorsque le temps est critique, mais que la correction exacte n’est pas essentielle.
  • Las-Vegas – Ces algorithmes s’exécutent en temps polynomial attendu, la sortie est toujours correcte. Ils sont utilisés dans des situations où la correction est non négociable, mais les performances peuvent être variables.

1.1 — Pourquoi utiliser des algorithmes probabilistes ?

Avantages :

  • bien conçus, plus efficaces dans la plupart des exécutions.
  • Conceptuellement plus simples et plus élégants.

Inconvénients :

  • Manque de correction : les algorithmes probabilistes fournissent la plupart du temps une probabilité de correction, plutôt que de garantir un résultat correct à chaque fois.
  • Solutions approximatives.
  • Les tests peuvent être plus difficiles car deux exécutions du même algorithme avec la même entrée peuvent produire des sorties différentes.

2 — Quelques exemples

2.1 — Vérificateur de produit matriciel

Essayez de répondre à la question suivante :

Quelle est la complexité de la multiplication de deux matrices $n\times n$ $A$ et $B$ ?

Solution

Définissons $C:=A\times B$. Chaque élément $c_{ij}$ de la matrice résultante $C$ est égal à $c_{ij}=\sum_{k=1}^na_{ik}b_{kj}$. Cela implique que pour calculer $c_{ij}$, nous devons effectuer $n$ multiplications et $n-1$ additions. Puisqu’il y a $n^2$ éléments dans $C$, la complexité du calcul de $C$ est $O(n^3)$.

Peut-on concevoir un algorithme qui fait mieux que $O(n^3)$ ?

Réponse – L’algorithme de Frievald. Il fonctionne comme suit :

Choisir un vecteur binaire aléatoire $r:=[r_i]_{1\leq i \leq n}$, où $Pr[r_i = 1] = Pr[r_i = 0] = 1/2$ pour tout $i\in [[1,n]]$. L’algorithme renverra true si $ABr = Cr$ et false sinon.

Quelle est la complexité de l’algorithme de Frievald ?

Solution

$O(n^2)$.

Que peut-on attendre de cet algorithme ?

  • Si $AB = C$, alors $Pr[output=true] = 1$.
  • Si $AB \neq C$, alors $Pr[output=false] \leq \frac{1}{2}$.

2.2 — Fingerprinting

Voici une définition du fingerprinting :

Un algorithme de fingerprinting est une procédure qui associe un élément de données arbitrairement grand (comme un fichier informatique) à une chaîne de bits beaucoup plus courte, son empreinte, qui identifie de manière unique les données originales à toutes fins pratiques, tout comme les empreintes digitales humaines identifient de manière unique les personnes à des fins pratiques.

Formellement, un algorithme de fingerprinting est la tâche qui conçoit une famille de fonctions $H$ (“famille de hachage”) telle que, si l’on sélectionne une fonction $h \in H$, alors si $x = y$, il est aussi vrai que $h(x) = h(y)$ avec une forte probabilité, avec la contrainte qu’il est plus rapide de vérifier que $h(x)=h(y)$ que $x=y$.

Application – Alice et Bob ont chacun un grand fichier composé de $n$ caractères ASCII (128 caractères). Ils doivent déterminer si leurs fichiers sont identiques avec la contrainte qu’ils veulent envoyer le moins d’informations possible sur leurs fichiers respectifs.

Solution – Fingerprinting de Reed-Solomon :

  • Le fichier d’Alice (resp. de Bob) est une séquence de caractères $(a_1,\ldots, a_n)$ (resp. $(b_1, \ldots , b_n)$) où chaque caractère peut prendre $m$ valeurs.
  • Fixons un nombre premier $p > \max\{m, n^2\}$, $F_p$ désignant l’ensemble des entiers modulo $p$ (toute l’arithmétique est faite modulo $p$).
  • Pour chaque $r \in F_p$, définissons $h_r(a_1,\ldots, a_n) = \sum_{i=1}^na_ir^i$. La famille $H$ de fonctions de hachage que nous considérerons est $H = \{h_r : r \in F_p\}$. Chaque fonction de hachage prend $(a_1,\ldots , a_n)$ comme coefficients d’un polynôme de degré $n$ évalué en $r$.
  • Alice choisit un élément aléatoire $r$ dans $F_p$, calcule $v = h_r(a)$, et envoie $v$ et $r$ à Bob. Bob renvoie true si $v = h_r(b)$, et false sinon.
Information

Vous pouvez voir la similarité entre le fingerprinting de Reed-Solomon et l’algorithme de Frievald, où l’on évalue simplement une fonction en une valeur aléatoire.

3 — Génération de nombres aléatoires

Nous avons vu dans la section précédente que l’utilisation de l’aléa dans les algorithmes peut améliorer drastiquement leurs performances. Cependant, se pose la question de savoir comment générer des nombres aléatoires dans un ordinateur.

Une suite de nombres aléatoires, $R_1,R_2,\ldots,$ doit posséder deux propriétés statistiques importantes :

  • Uniformité – $P(R_i\leq x)= x$, avec $x\in[0,1]$.
  • Indépendance – Chaque événement est indépendant de toute combinaison d’autres événements.

En pratique, il est très difficile de générer de véritables nombres aléatoires, et les algorithmes actuels génèrent des nombres pseudo-aléatoires.

La génération de nombres pseudo-aléatoires peut présenter les défauts suivants :

  • Les nombres générés peuvent ne pas être uniformément distribués.
  • Les nombres générés peuvent être à valeurs discrètes au lieu de valeurs continues.
  • Autocorrélation entre les nombres.

Malgré ces problèmes, les nombres pseudo-aléatoires sont encore largement utilisés pour simuler l’aléa. Lors de la conception d’algorithmes pour générer des nombres pseudo-aléatoires, vous devez toujours considérer les propriétés suivantes :

  • L’algorithme doit être rapide.
  • L’algorithme doit être portable sur différents ordinateurs et idéalement sur différents langages de programmation.
  • La séquence générée doit être reproductible.
  • La séquence générée doit approcher étroitement les propriétés d’uniformité et d’indépendance.

Un exemple classique de génération de nombres aléatoires est la méthode congruentielle linéaire. La méthode congruentielle linéaire, proposée par Lehmer, produit une suite d’entiers $R_1,R_2,\ldots,$ entre zéro et $m-1$ selon la relation récursive suivante :

$$R_{i+1}=(aR_{i}+c)\text{ mod } m,\;i=0,1,2,\ldots \;,$$

où :

  • La valeur initiale $R_0$ est appelée la graine.
  • $a$ est appelée le multiplicateur constant.
  • $c$ est l’incrément.
  • $m$ est le module.
Information

Pour générer des nombres aléatoires entre 0 et 1, vous pouvez utiliser $\frac{R_i}{m}$.

Pour aller plus loin

On dirait que cette section est vide !

Y a-t-il quelque chose que vous auriez aimé voir ici ? Faites-le nous savoir sur le serveur Discord ! Peut-être pouvons-nous l’ajouter rapidement. Sinon, cela nous aidera à améliorer le cours pour l’année prochaine !

Pour aller au-delà