Composante
Polytech Grenoble - INP, UGA
Description
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
Heures d'enseignement
- Algorithmique avancée / Advanced Algorithms (AA) - CMTDCours magistral - Travaux dirigés27h
Pré-requis recommandés
Bases de l'algorithmique et de la programmation impérative
Basics on algorithmics and imperative programming
Période
Semestre 6
Évaluation initiale / Session principale - Épreuves
Libellé | Nature de l'enseignement | Type d'évaluation | Nature de l'épreuve | Durée (en minutes) | Nombre d'épreuves | Coefficient de l'épreuve | Remarques |
---|---|---|---|---|---|---|---|
35/100 |
Bibliographie
- D. Beauquier, J. Berstel, P. Chrétienne Eléments d'algorithmique, Masson, 2005
- T. Cormen, C. Leicerson, R. Rivalst Algorithmique, éditions Dunod, 2013