Contenu
Critères de choix d'une solution algorithmique de problèmes, complexité d'algorithme versus performance de l'implantation, complexité en pire cas et en moyenne. Principaux types d'algorithmes, leurs qualités et défauts: algorithmes voraces, diviser pour régner, retour arrière, «branch and bound», programmation dynamique; exemples de problèmes résolus par des algorithmes de chaque type et leur analyse. Méthodes d'exploitation des graphes et leurs applications. Bornes inférieures de performance des algorithmes. Problèmes polynomiaux et intraitables, problèmes NP-complets, heuristiques, solutions approximatives. Ce cours comporte des séances obligatoires de travaux dirigés (TD) de deux heures par semaine.