IND235 - Graphes et algorithmes
Ce cours vise à expliquer des notions de la théorie des graphes et des algorithmes qui s’y rattachent.
Au terme de ce cours, l’étudiante ou l’étudiant sera en mesure de : utiliser la théorie des graphes pour représenter et résoudre des problèmes de nature algorithmique ; expliquer la notion de classes de complexité ; choisir la technique algorithmique appropriée en fonction du contexte ; implémenter de manière efficace des algorithmes de la théorie des graphes.
Analyse de la complexité asymptotique. Algorithmes de parcours de graphes, de détection de cycles et de décomposition en composantes fortement connexes. Arbres couvrants. Problèmes classiques de la théorie des graphes. Solutions exactes et approchées. NP-complétude : certificat, réduction polynomiale et théorème de Cook.