Résumé de séminaire

Résumé :

Le séminaire à pour but de vous familiariser avec certains activités de l'équipe MoVe du LIF dans le domaine de l'algorithmique de l'analyse exhaustive (recherche d'états accessibles) de systèmes complexes. Les algorithmes étudiés ont deux domaines d'applications principaux : la recherche de fautes (souvent appelée "vérification"), et la planification (l'ordonnancement).

Nous poursuivons dans ce cadre l'amélioration heuristique des algorithmes de base, qui sont pour l'essentiel des algorithmes de graphe (tel que la recherche en profondeur etc). Bien que les problèmes et algorithmes sont très simples, l'analyse échoue souvent à la complexité, c'est à dire à la taille des graphes en question. Ces graphes, construits à partir de modèles des systèmes analysés, depassent souvent la capacité de nos ordinateurs, mais disposent typiquement d'une structure assez régulière. La recherche naïve se perd dans la redondance de ces graphes. Le but des améliorations heuristiques des algorithmes de recherche que nous étudions -- en pluspart sous le titre des "Méthodes d'Ordres Partiels" -- est de mieux guider la recherche en exploitant ces propriétés structurelles.

Le séminaire commencera avec une introduction des domaines d'application et des approches de modélisation courantes, expliquera en détail l'approche "ordres partiels" et indiquera certains de nos découvertes récentes.

Références :

Home page : http://www.cmi.univ-mrs.fr/~niebert