La calculabilité s’attache à connaître ce qu’on peut résoudre par algorithme quel que soit le temps d’exécution. Or les chercheurs s’intéressent le plus naturellement à l’efficacité des algorithmes c.-à-d. exécuter l'algorithme avec le minimum de ressources. L'analyse de la complexité d'un algorithme traite ainsi l'étude formelle de la quantité de ressources en temps ou/et en espace nécessaire à son exécution.
Le but de ce module est :
1. Introduire les concepts de base de la Complexité Temporelle
et spatiale.
2. Etre capable de différencier entre les problèmes P, NP et
NP complétude.
3. Etre capable de
calculer la complexité d’un algorithme versus d’un problème.
4. Connaitre les problèmes NP-Complets
5. Comprendre la complexité spatiale
- Enseignant: KARIMA BENHAMZA