Complexité algorithmique

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

Contact(s)

Contact(s) administratif(s)

Bruno DURAND (bruno.durand @ umontpellier.fr)