ELE440 - Algorithmes

Ce cours vise à analyser et à concevoir des algorithmes.

Au terme de ce cours, la personne étudiante sera en mesure de :

• analyser un algorithme pour en caractériser la performance en termes de temps de calcul et de consommation de mémoire en termes asymptotiques;
• choisir de façon éclairée parmi différents algorithmes et structures de données en fonction des caractéristiques d'une application donnée;
• adapter les algorithmes classiques de tri, de recherche par valeur et d'optimisation sur les graphes à des applications spécifiques;
• décrire plusieurs problèmes d'optimisation combinatoire classiques;
• concevoir des algorithmes pour la résolution de problèmes d'optimisation combinatoires basés sur différentes techniques classiques et modernes;
• mettre en œuvre différents algorithmes pour un problème donné à l'aide d'un langage de programmation et en évaluer l'optimalité et/ou la performance empiriquement.

Éléments de contenu : notation asymptotique et calcul asymptotique. Méthode des baromètres pour l'analyse du temps de calcul des algorithmes. Résolution d'équations de récurrence pour l'analyse d'algorithmes récursifs. Analyse de la consommation de mémoire des algorithmes. Algorithmes de tri. Algorithmes de recherche par valeur. Structures de données. Problèmes de plus court de chemin. Arbres minimalement couvrants. Problèmes d'optimisation combinatoire. Algorithmes gloutons. Programmation dynamique. Algorithmes de retour en arrière. Approche « branch-and-bound». Euristiques, métaeuristiques et algorithmes génétiques. Algorithmes non déterministes.