|
 Objectifs
Introduction aux limites théoriques à la réalisation informatique de problèmes. Développement de techniques d'analyse mathématique de complexité d'algorithmes. Application à diverses classes de problèmes et à différents modèles de calcul, y compris de calcul parallèle.
Cahier des charges
1. Théorie
- complexité et problèmes irréalisables
- théorie de la NP-complétude
- exemples de problèmes NP-complets
- analyse de problèmes par la NP-complétude
- comment traiter les problèmes NP-complets
- autres classes de problèmes
2. Méthodes d'analyse d'algorithmes et applications
- approximation axymptotique
- récurrences
- méthodes statistiques
- autres méthodes
- applications (algorithmes de tris, recherche, traitement de chaînes de caractères,...)
- analyse d'algorithmes parallèles
|
