navigation

Changer la langue :

Langue / language

Rechercher

 

Probability in modelling, algorithms, and verification

First published : Thursday 27 November 2008 by Sophie Pales

Logical approaches, which have occupied a major place in computer science until the last ten years, have turned out not to scale up well in many cases. Probability, randomness and statistics, which used to be confined to performance evaluations, reliability estimations or machine learning, are now developed in many areas under various forms: given the computation (and storage) power available nowadays, and the number of accessible processors, it is often more efficient to make some well suited random choices than to
perform some systematic explorations.

For similar reasons, it is often necessary to observe, model, analyse very complex computerised systems by probabilistic or statistic approaches.
These ideas are currently the bases of many significant advances in areas such as randomised algorithms, communication protocols, web searching, cryptography, validation and verification...

These approaches raise difficult theoretical issues but are opening extremely promising perspectives.


In Digiteo, there is a variety of works relying on probability, randomness and statistics for attacking diverse problems such as, to cite just a few:


• randomised algorithms, approximations and complexity
• quantum computing
• formal languages (mainly based on process calculi) for modelling stochastic systems
• probabilistic model checking
• model-based random testing
• network modelling and analysis based on game theory
• statistical pattern recognition, statistical learning
• modelling faults as rare events
It is planned to take advantage of this diversity and to explore possible cross-fertilisations and complementarities between the groups involved in the use of probabilistic and statistic approaches.


Although they make intensive use of similar mathematical concepts, the two topics "Uncertainty" and "Probability in modelling, algorithms, and verification" are of different nature: the first one aims at dealing in a controlled way with those inaccuracies that come from external sources such as measurement errors or approximation in modelling (due to high intricacy of the considered phenomena). The second one aims at exploiting approximation and probability in computing methods in order to deal with problems that are known as "hard" by computer scientists.