Composante
Sciences Fondamentales et Appliquées
Description
Dans ce cours, nous traitons des algorithmes opérant sur des structures de données avancées, arbres ou graphes, permettant de réaliser des types de données abstraits élaborés ou de résoudre certains problèmes algorithmiques complexes
* Algorithmes évolués (analyseurs syntaxiques récursifs, algorithmes de backtracking, programmation dynamique, etc.).
* Compléments d'algorithmique sur les arbres (arbres de recherche, files à priorité, tas, etc.)
* Graphes et algorithmes de base sur les graphes (parcours, différents calculs : composantes connexes, composantes fortement connexes, tri topologique, composantes biconnexes, etc.).
Objectifs
* Étudier les algorithmes classiques sur certaines structures d'arbres ou sur les graphes.
* Concevoir et déployer des algorithmes sur ces mêmes structures.
Heures d'enseignement
- CMCM16h
- TDTD34h
Compétences visées
* Choisir ou spécifier un type de données abstrait pour résoudre un problème particulier
* Implémenter des types de données abstraits à partir de structures de données classiques
* Utiliser les graphes pour modéliser des problèmes combinatoires ou d'optimisation
* Appliquer des algorithmes classiques en dehors de leur contexte habituel