Phénomènes aléatoires pour la simulation

DEA Informatique Fondamentale et Applications 2002-2003

L'introduction de méthodes aléatoires dans des algorithmes géométriques a pour objectif de diminuer de manière importante les temps d'exécution. Le cours introduira des exemples dont la complexité algorithmique dans les cadres déterministe et probabiliste sont de nature très différente. On commencera par introduire et discuter la génération de suites de nombres pseudo-aléatoires, simulation et chaînes de Markov discrètes. On donnera ensuite des applications à des méthodes randomisées d'élimination des surfaces cachées.

Livres de référence :

The Art of computer Programming, vol 2 (seminumerical algorithms)
D. Knuth, Addison Wesley, 1969.

Randomized Algorithms
R. Motwani et P. Raghavan, Cambridge University Press, 1995.

Probabilités de l'ingénieur
N. Bouleau, Hermann 1986.

Experimental stochastic
Otto Moeschlin, Springer 1998.

Autres références :

Computational Geometry: An Introduction through Randomized Algorithms

Randomized Algorithms: ( Bruno R. Preiss, P.Eng)
Generating Random Numbers
Random Variables
Monte Carlo Methods

Randomized algorithms and combinatorial optimization: (Shang-Hua Teng)

Geometry in action: (David Eppstein)

Randomized Algorithms: (David Karger)

Linear congruential generator: LCG:

PLAB:  "A Server on the Theory and Practice of Random Number Generation. This server is maintained by a team of mathematicians and computer scientists led by Peter Hellekalek at the University of Salzburg's Mathematics Department (an unmoderated but richer collection of network-resources on random number generators is located on this server as part of the WWW Virtual Library)."

The www virtual library on random numbers and Monte Carlo methods:

DEA Informatique Fondamentale et Applications:   Institut d'électronique et d'informatique Gaspard-Monge.