Graphes et algorithmes

1er cycle

Préalable(s) LOG320 Sigle IND235 Responsable Département de génie logiciel et TI Cycle 1 er Crédits 3 Charge de travail Cours (3 h) laboratoire et travaux pratiques (2 h) Plan du cours Site du cours 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.