Propriétés des algorithmes randomisés (Monte Carlo, Las Vegas)

Question

Je suis en train d'apprendre les algorithmes de Las Vegas et de Monte Carlo et j'ai deux questions à poser, mais je ne peux pas y répondre, si quelqu'un peut m'aider ... Merci à l'avance

1. Considérons Monte Carlo algorithmes a pour un problème P dont le temps d'exécution attendu est au plus T (n) sur une instance de taille n qui produit une solution correcte avec une probabilité de y (n). Supposons en outre que, étant donné une solution à P, nous pouvons vérifier son exactitude à l'instant t (n). Montrer comment obtenir un algorithme de Las Vegas qui donne toujours une réponse correcte à P et qui s'exécute au maximum dans le temps prévu (T (n) + t (n))/y (n).

2. Soit 0 < ε2 ε1 < < 1. Considérons un algorithme de Monte Carlo qui donne la bonne solution à un problème avec une probabilité d'au moins 1-ε1, quelle que soit l'entrée. Combien d'exécutions indépendantes de cet algorithme suffisent à augmenter la probabilité d'obtenir une solution correcte au moins 1-ε2, quelle que soit l'entrée?

Answer 1

1. répéter l'exécution de votre algorithme et tester le résultat jusqu'à ce que vous obtenez une réponse correcte. Chaque exécution et vérification prend (T (n) + t (n)) unités de temps, et le nombre de courses est une variable aléatoire géométrique avec la moyenne 1/y (n).

2. Quelle est la probabilité de défaillance pour un cycle? Pour deux courses? n s'exécute? Définissez la probabilité d'échec pour n courses égale à e2 et résolvez pour n.