Responsable : Nicolas Barnier (  Cette adresse email est protégée contre les robots des spammeurs, vous devez activer Javascript pour la voir. ) – Tel. 05 62 17 42 82  ECTSCOURSTDTP 367%33%   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.  Pré-requis Programmation et algorithmique.  Description 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 logique, 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.  Bibliographie - Garey & Johnson, Computer and Intractability: A Guide to the Theory of NP-Completeness, 1979. - Alliot, Schiex, Brisset & Garcia, Intelligence Artificielle & Informatique Théorique, 2002