Complexité algorithmiqueCode de l'UE : HMIN117M
Présentation
Le cours présentera les fondements des notions de complexité des algorithmes. On s’intéressera à mesurer la complexité en temps et en espace sur un modèle de calcul, et on montrera que les modèles de calcul usuels sont polynomialement équivalents. Ensuite, on étudiera la complexité dans le pire des cas et en moyenne sur divers problèmes algorithmiques, en espace et en temps. La notion de réduction entre problèmes sera présentée afin d’établir les hiérarchies de la complexité classique. La NP-complétude sera abordée en détails afin que tout étudiant sache montrer la NP-complétude d’un problème élémentaire. Les exemples seront pris dans le domaine des graphes, dans celui des pavages, et de façon générale en algorithmique élémentaire. Enfin les jeux algorithmiques de type Arthur-Merlin et les preuves interactives seront abordées pour conclure sur le théorème IP=Pspace.
Volume horaire
- CM : 16.5
- TD : 33
- TP : 0
Diplômes intégrant cette UE
En bref
Crédits ECTS 5
Période de l'année
premierSemestre
Langue d'enseignement
fr