BAC-L0-FOUND-102
Structures de données et coût des opérations
Tableaux, tables de hachage, arbres : ce que chaque structure rend rapide et ce qu'elle rend cher. Le socle de tout raisonnement ultérieur sur le stockage d'une chaîne.
- Niveau
- L0 — Fondation
- Durée
- 3 h
- Piste
- Fondation
- Mainteneur
- Architecte du curriculum développeur
Objectifs pédagogiques
- 01Comparer le coût des opérations de recherche, d'insertion et de parcours
- 02Choisir une structure à partir du profil d'accès attendu
- 03Mesurer un coût réel plutôt que de l'estimer
Laboratoire guidé
Implémenter une table de hachage et un arbre de recherche, puis mesurer les deux sur le même jeu de données.
Laboratoire autonome
Reprendre la mesure sur un jeu de données cent fois plus grand et expliquer l'écart observé.
Volet sécurité
Collision volontaire dans une table de hachage : comment une entrée choisie par un attaquant dégrade un service.
Évaluation
Rapport de mesure avec justification du choix de structure.