Quelques études de l'aléatoire en informatique

Abstract

L'objectif de cette presentation est de montrer le role central de l'aleatoire dans des domaines de recherche en combinatoire, algorithmique et complexite. Nous verrons egalement qu'il intervient dans des domaines d'application comme la cryptographie, le tatouage et la biometrie. Selon les etudes proposees, ce sont des aspects differents de l'aleatoire qui entrent en jeu comme la modelisation aleatoire et le calcul de probabilites asymptotiques, la generation aleatoire ou encore l'extraction de l'aleatoire des donnees. Une premiere partie sera consacree a l'etude des noyaux dans les graphes aleatoires. Un noyau est un ensemble de sommets qui verifie deux proprietes tres connues en theorie des graphes : la stabilite et la dominance, ces deux proprietes s'opposent et limitent les tailles possibles des noyaux. Nous verrons comment modifier ces tailles soit en proposant des variantes de la propriete de noyau (resultats de contrexemples de lois 0-1 en theorie des modeles finis et en logiques modales, obtention de transitions de phase), soit en changeant la distribution de probabilites (graphes sans circuit, graphes creux, graphes denses). Nous verrons quel impact que cela entraine sur la complexite des algorithmes de recherche de noyau. La seconde partie porte sur les classes de fonctions booleennes definies selon des proprietes utiles pour la cryptographie symetrique. L'objectif est l'enumeration et la generation aleatoire uniforme de ces classes de fonctions. Nous verrons qu'il est possible d'enumerer et generer efficacement les fonctions 1-resilientes jusqu'a 8 variables. L'originalite de notre methode -- a la fois combinatoire et algorithmique -- que nous avons appelee methode des classes, a ete de classifier l'ensemble des fonctions booleennes en fonction de leur ecart avec les fonctions 1-resilientes. Nous nous interessons dans la troisieme partie a l'etude de l'aleatoire des donnees, ce travail s'inscrit dans des co-encadrements de these. Il s'agit d'eviter une modelisation aleatoire difficile et peu fidele et de determiner les parties aleatoires de ses donnees. La these de Cyril Bazin (soutenue en 2010) propose une methode de tatouage de donnees geographiques vectorielles qui est rapide, aveugle et robuste a la rotation et a la translation. La methode consiste a introduire un biais statistique sur des petites parties du document appeles sites. Les theses de Zhigang Yao (soutenue en 2015) et Benoit Vibert (en cours) portent sur des donnees biometriques --les empreintes digitales-- plus precisement sur les minuties extraites de ces empreintes. Nous verrons comment mesurer la qualite d'une empreinte et comment selectionner les minuties les plus pertinentes. Nous proposerons finalement un projet de recherche sur la quantification et la classification de l'aleatoire des donnees provenant de transactions numeriques.

Locations

• HAL (Le Centre pour la Communication Scientifique Directe) - View - PDF