Outils logiciels pour les cours Paris II

Cours Paris II

edit SideBar

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