[PDF] Probabilités, simulation et algorithmique (pour TI)

Quel est le modèle de calcul associé aux algorithmes probabilistes ?

En gros, il ajoute au compromis sur l'exactitude de la réponse des algorithmes de Monte-Carlo le compromis sur la complexité du calcul des algorithmes de Las Vegas. Un modèle de calcul associé aux algorithmes probabilistes est la machine de Turing probabiliste.

Pourquoi les algorithmes probabilistes sont-ils étudiés ?

Les algorithmes probabilistes sont étudiés car ils sont souvent plus simples à analyser et très souvent plus rapides 1 . Un algorithme est dit probabiliste si son comportement dépend à la fois des données du problème et de valeurs produites par un générateur de nombres aléatoires .

Quels sont les principes de base des modèles de simulation ?

Principes de base des modèles de simulation La simulation est une technique de résolution de problème. ORIGINE: Statistiques, analyse de systèmes complexes, probabilités, modélisation. ? Objectifs moins bien définis ? Problèmes complexes où les techni- ques standards sont inutilisables. L’ESSOR DE LA SIMULATION EST DÛ PRINCIPALEMENT À L’ORDINATEUR.

Comment créer un algorithme non probabiliste ?

Ensuite, on peut essayer d'obtenir un algorithme non probabiliste avec une complexité semblable en transformant l'algorithme probabiliste. Ce processus de conception est appelé dérandomisation . De façon plus générale, on peut considérer l'aléa comme une ressource (au même titre que le temps ou l' espace ), et essayer de minimiser son utilisation.