Diplômes intégrant cet élément pédagogique :
Descriptif
L'objectif de ce cours est de présenter les algorithmes de base pour les structures de type arbre et graphes. Différents types d'arbres seront étudiées (ABR, AVL, A234). Plusieurs types de graphes seront également étudiés (orientés, pondérés). Certains de ces algorithmes seront mis en œuvre sur 3 TP. Ces TP sur ces structures de données permettent aux étudiants de se familiariser avec les mécanismes dynamiques d'allocation mémoire.
- Arbre ABR
- Arbre AVL
- Arbre 234
- Arbres bicolore
- Introduction aux graphes
- Parcours en largeur et en profondeur
- Tri topologique
- Algorithme du plus court chemin
- Composantes connexes
The course presents the basic algorithms for tree and graph structures. Different types of trees will be studied (ABR, AVL, A234). Several types of graphs will also be studied (oriented, weighted). Some of these algorithms will be implemented on 3 PWs. These PWs on these data structures allow students to become familiar with the dynamic mechanisms of memory allocation.
- ABR tree
- AVL tree
- Tree 234
- Two-color trees
- Introduction to graphs
- Width and depth traversal
- Topological sorting algorithm
- Shortest path algorithm
- Strongly connected components
Pré-requis recommandés
Bases de l'algorithmique et de la programmation impérative
Basics on algorithmics and imperative programming
Bibliographie
- D. Beauquier, J. Berstel, P. Chrétienne Eléments d'algorithmique, Masson, 2005
- T. Cormen, C. Leicerson, R. Rivalst Algorithmique, éditions Dunod, 2013
Informations complémentaires
Lieu(x) : GrenobleLangue(s) : Français