Catalogue des formations

Diplômes intégrant cet élément pédagogique :

• Ingénieur de Polytech Grenoble spécialité Informatique (RICM)

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) : Grenoble
Langue(s) : Français