Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Test de propriété
Résumé
En informatique théorique, un test de propriété (ou property testing en anglais) est un test probabiliste qui a pour objectif de déterminer si un objet donné, par exemple un graphe ou une fonction, possède une propriété fixée ou bien s'il est « loin » de l'avoir. Ces algorithmes ont l'avantage d'être très rapides.
Les testeurs de propriété sont notamment utiles pour tester que des grands graphes ont certaines propriétés.
Considérons l'exemple simpliste suivant : on cherche à savoir si un graphe est vide ou relativement loin de l'être. Plus précisément on cherche à savoir si le graphe donné en entrée (dont le nombre de nœud est noté n) n'a aucune arêtes ou bien a au moins arêtes. Le type de requêtes est le suivant : on choisit k sommets et on reçoit le sous-graphe induit par ces k sommets. L'algorithme est simple : choisir au hasard uniformément k sommets, si le sous-graphe induit est vide renvoyé vide sinon renvoyer non vide. Dans le cas de la sortie non vide, l'algorithme ne se trompe pas, alors que dans le cas de vide, il est possible que le graphe soit en fait loin d'être vide. Cependant la probabilité d'erreur est petite pour n allant vers l'infini.
Soit un ensemble, et une distance sur cet ensemble. Soit un sous-ensemble de , qu'on appelle propriété. Un testeur de propriété pour est un algorithme qui prend en entrée un élément et un paramètre de distance , effectue certains types de requêtes (queries) sur , et détermine certaines caractéristiques (par exemple, le -ème bit de , ou bien la valeur d'une certaine fonction fixée a priori).
Les testeurs de propriété sont intéressants lorsqu'ils satisfont des contraintes fortes, par exemple un nombre de requêtes constant (dans le cadre de la complexité en requêtes), ou un temps de calcul sous-linéaire. Dans cette optique on s'intéresse à des algorithmes probabilistes et non déterministes, afin d'obtenir des résultats non-triviaux.
L'algorithme a les propriétés suivantes :
accepte avec une probabilité si ;
rejette avec une probabilité si ;
peut renvoyer n'importe quel résultat avec une probabilité quelconque si .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.