BD 3

Test de propriété

Comment approximer une propriété (vraie ou fausse)?
- Las-Vegas et Monte-Carlo
  - Comment réduire l'erreur dans un algorithme de Monte-Carlo ?
- ε-testeur, comment faire un très faible nombre de requêtes? Par exemple O(1/ε) indépendant de n, la taille des données?

Préliminaires
- distance entre objets: edit distance, hamming distance, ...
- dist(x,y) < ε
- dist (x,L)= Min _{y in L} dist(x,y) < ε
Exemples:
- Mots:
  - Tester si deux mots sont proches
  - Tester si un mot w est proche d'une expression régulière (a*.b* par exemple).
- Arbres
  - Tester si deux arbres sont proches
  - Tester si un arbre T est proche d'une DTD (par exemple).
- Graphes
  - Tester si deux graphes sont proches ?
  - Tester si un graphe G est 3 coloriable.
- Tables
  - Tester si une requête OLAP est proche d'une distribution fixe

UP2