| |
La dimension paramétrique des modèles,
le nombre de données, les contraintes à respecter,
sont des sources de problèmes algorithmiques qui peuvent
être déterminants. Modéliser devient un compromis
entre la pertinence et la faisabilité algorithmique. Le
problème se retrouve dans de nombreuses situations, par
exemple :
- Calcul du maximum de vraisemblance dans des "gros"
modèles, spatialisés, bayésiens, associant
variables continues et discrètes, etc.,
- Optimisation de décision dans des espaces de décision
très vastes,
- Recherche de motifs semblables dans des séquences nucléotidiques.
La difficulté essentielle de ces problèmes réside
dans la grande dimension des espaces explorés qui conduit
habituellement à des algorithmes de complexité temporelle
exponentielle. La recherche d'algorithmes efficaces et rapides,
et d'approximations raisonnables et calculables est donc un thème
de recherche actif et permanent dans les communautés mathématiques
et informatiques. Les communautés scientifiques sont fortement
structurées par les formalismes mathématiques utilisés
pour modéliser le problème (réseaux bayésiens
et modèles graphiques, réseaux de contraintes, processus
décisionnel de Markov, programmation linéaire en
nombres entiers, etc.) mais aussi par la nature des problèmes
traités (continus, discrets, optimisation, intégration,
…) menant à l'utilisation de techniques variées.
Pour tous ces problèmes, la théorie de la complexité
montre bien que le point bloquant réside dans le caractère
exponentiel (en temps et parfois en espace) des algorithmes. Cette
théorie montre toutefois qu'il y a peu d'espoir de voir
apparaître un jour une méthode exacte et générale
permettant de résoudre toutes ces questions. Les lents
et tenaces travaux de recherche permettent de grignoter lentement
la courbe de la dimensionnalité et de rendre traitable
des problèmes de plus en plus larges avec des modèles
de plus en plus réalistes.
|
