921 - Algorithmes de recherche et structures de données associées.2021

Rapport du jury 2019

Le sujet de la leçon concerne essentiellement les algorithmes de recherche pour trouver un élément dans un ensemble : l’intérêt des structures de données proposées et de leur utilisation doivent être argumentés dans ce contexte. Par exemple, la recherche d’une clé dans un dictionnaire donne ainsi l’occasion de définir la structure de données abstraite « dictionnaire », et d’en proposer plusieurs implantations concrètes. $\\$ De la même façon, on peut évoquer la recherche d’un mot dans un lexique : les arbres préfixes(ou digital tries) peuvent alors être présentés. Mais on peut aussi s’intéresser à des domaines plus variés, comme la recherche d’un point dans un nuage (et les quad-trees), et bien d’autres encore.