Structures de Données et Algorithmes Avancés
Cours de structures de données et algorithmes avancés (M1, DMI/FST/UCAD) : types abstraits, analyse de complexité, tables de hachage, arbres et tas, séance par séance.
Niveau : M1 · Domaine : Programmation, Web & Mobile
Objectifs
- Distinguer un type abstrait de données de son implémentation
- Analyser la complexité d’un algorithme et la justifier
- Choisir la structure de données adaptée à un problème
- Implémenter tables de hachage, arbres et tas en Java
Prérequis
- Java (classes, héritage, interfaces)
- Algorithmique de base
Ce cours prépare à
Ressources du cours
- TP · TP 1 — Mise en place de l’environnement (319 Ko)
Séances
| Séance | Contenu | Format |
|---|---|---|
| ADTs et interfaces Java | types abstraits de données, interfaces Java, et la séparation du contrat et de l’implémentation. | TP (325 Ko) |
| Analyse algorithmique | compter les opérations, notations O, Oméga et Thêta, analyse de cas et théorème principal. | TP (348 Ko) |
| Tables de hachage | fonction de hachage, collisions, chaînage, sondage linéaire et redimensionnement. | TP (422 Ko) |
| Arbres et tas | arbres binaires de recherche, rotations AVL, tas binaires et file de priorité. |