CHRONIQUE. Mathématiques : une astuce probabiliste pour les suites de nombres

ANDRZEJ WOJCICKI / SCIENCE PHOTO L / AWO / Science Photo Library via AFP

Comment compter le nombre d'éléments distincts d'une suite de nombres ? Ce problème a des applications concernant la cybersécurité, entre autres, nous explique Claire Mathieu, directrice de recherche au CNRS.

Cet article est extrait du mensuel Sciences et Avenir - La Recherche n°904, daté juin 2022.

La suite (12, 17, 12, 15, 17, 15, 15) contient trois éléments distincts, à savoir {12, 15, 17}. Comment compter le nombre d'éléments distincts d'une suite de nombres ? Ce problème a des applications concernant la cybersécurité, entre autres. A priori la solution semble simple : en mémorisant l'ensemble des éléments déjà vus à mesure que les éléments défilent. Mais comment faire si on n'a pas assez de place pour tout le monde ? Par exemple, si les éléments distincts sont des entiers entre 1 et 1000, mais qu'on a juste la place d'en stocker 1 ? Impossible alors de faire le décompte exact.

Une solution approchée, en recourant aux probabilités

Il existe une solution approchée, en recourant aux probabilités. Pour cela, on utilise une fonction h qui transforme chaque nombre x entre 1 et 1000 en un autre nombre h) entre x (1 et 1000, qui soit quasiment aléatoire.

À chaque nombre x de la suite qui passe, on regarde si h) est divisible par 1, 2, 4, 8, 16, 32, x (64, 128, 256 ou 512 : dix possibilités. À mesure que les éléments passent, on mémorise le plus grand diviseur rencontré. Ainsi, on a un seul diviseur à mémoriser, et donc la place mémoire est minuscule !

Une estimation probablement et approximativement correcte

Par exemple, si ce diviseur est 16, cela signifie qu'il y a probablement dans la suite au moins 16 éléments distincts (sinon on ne serait probablement pas tombé sur un multiple de 16, sauf malchance) et au plus 31 éléments distincts (sinon on serait probablement tombé sur un multiple de 32, sauf malchance). C'est l'idée de base pour une estimation probablement et approximativement correcte.

Par Claire Mathieu, directrice de recherche au CNRS, Institut de recherche en informatique fondamentale (CNRS/université de Paris)

Retrouvez cet article sur sciencesetavenir.fr

A lire aussi

Notre objectif est de créer un endroit sûr et engageant pour que les utilisateurs communiquent entre eux en fonction de leurs centres d’intérêt et de leurs passions. Afin d'améliorer l’expérience dans notre communauté, nous suspendons temporairement les commentaires d'articles