Algorithmique et structures de données
Objectifs
Le cours présente des structures de données avancées utilisées en programmation et montre leurs intérêts et les algorithmes les mettant en œuvre.
Plan du cours
Chapitre 1 : tables de hachage
Chapitre 2 : récursivité (entiers et listes)
Chapitre 3 : arbres (parcours, ABR, AVL, arbres rouge-noir, B-arbres)
Chapitre 4 : preuves et tris (sélection du maximum, tri rapide, tri fusion)
Description des TP
Les TP permettent la mise en oeuvre des concepts vus en cours au semestre 2 principalement.
- TP 1 : rappel sur les listes
- TP 2 : tables de hachage
- plusieurs TP sur les arbres
- plusieurs TP sur les tris
Les TPs sont réalisés en langage C.
Connaissances requises
Les éléments vus au semestre 1 : notions de base d'algorithmique (variables, fonctions, boucles, tableaux), listes
RSE (Responsabilité Sociale et Environnementale)
-
Thèmes:
Économie d'énergie (complexité algorithmique, optimisation)
- Nombre d'heures: 2
Bibliographie
1. « Introduction to Algorithms » par Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, 3ème édition, 2009, 978-0262033848.
2. « Algorithms », par Robert Sedgewick et Kevin Wayne. 4ème édition, 2011, 978-0321573513.