Quelques algorithmes numériques



Méthode de Monte-Carlo

Les méthodes Monte Carlo consistent en des simulations expérimentales ou informatiques de problèmes. Elle sont basées sur le tirage de nombres aléatoires. Pour obtenir des résultats statistiquement fiables, il est nécessaire d'évaluer des centaines de structures, typiquement un millier. Ce nombre est bien sûr d'autant plus grand que le nombre de variables à évaluer est élevé. Le grand avantage de ces méthodes est leur simplicité.
En Maple, la fonction rand permet d'obtenir un nombre aléatoire ou une procédure.
Appel:
rand(expression)

Paramètres:
expression - (optionnel) un entier ou un intervalle :

  • si l'expression est absente, le résultat sera un nombre à 12 digits
  • si l'expression est un entier n, le résultat sera une procédure permettant de générer aléatoirement des nombres entre entier entre 0 et n-1
  • si l'expression est un intervalle a..b, le résultat sera une procédure permettant de générer aléatoirement des nombres entre entier entre a et b

Exemples

> rand();
                427419669081
>rand();
                321110693270
>die := rand(1..6):
>die();
                     4
>die();
                     6

Dichotomie

La dichotomie consiste pour un objet de taille N à exécuter un algorithme de façon à réduire la recherche à un objet de taille n/2. On répète l'algorithme de réduction sur ce dernier objet. Ce type d'algorithme est souvent implémenté de manière récursive. Lorsque cette technique est utilisable, elle conduit à un algorithme très efficace et très lisible.