Objectifs :
Estimation des temps de calcul et consommation mémoire des algorithmes classiques non-récursifs et récursifs. Caractérisation des problèmes de la classe NP et preuves de NP-complétude, résolution par des méthodes approchées.
La notion de complexité des algorithmes est centrale à l’informatique moderne. Elle permet d’estimer les quantités de ressources (temps, espace) que l’exécution d’un programme utilisera en fonction de la taille des données.
La première partie du cours est consacrée à l’analyse des algorithmes classiques, non-récursifs et récursifs, pour évaluer leur complexité en pire cas ou en moyenne, en temps et en espace :
- comptage de boucles
- arbre d’exécution et de décision
- dénombrement
- méthode Master…
La seconde partie traite de la classe des problèmes NP à partir du modèle de calcul de la machine de Turing. Les problèmes NP-complets sont introduits avec le théorème de Cook et les problèmes classiques de logiques, sur les ensembles, les graphes etc. sont détaillés. La notion fondamentale de réduction polynomiale entre problèmes est alors explorée de manière approfondie. Une topologie des classes de problèmes et de la hiérarchie polynomiale de classes peut alors être dégagée. Enfin, une approche plus pragmatique de la résolution des problèmes d’optimisation « difficiles » est présentée avec les schémas d’approximation polynomiaux, ainsi que la recherche systématique et approchée.
[Couramment dans le parcours « Systèmes répartis et Logiciel critique » du M2R IT, ce cours sera délacé dans le parcours RO]
[Mutualisé avec le cours « Complexité » de la 3e année ENAC]