Date/heure
15 novembre 2023
10:30 - 12:00
Lieu
Salle de conférences Nancy
Oratrice ou orateur
Victor Dubach
Catégorie d'évènement Séminaire des doctorants
Résumé
Comment stocker des données désordonnées ?
Imaginez être gérant.e d’un grand parking, réservé aux voitures abonnées. Une barrière y bloque l’entrée et ne s’ouvre que pour les voitures inscrites. Régulièrement des gens viennent vous voir pour y inscrire leur plaque d’immatriculation, que vous devez noter quelque part. Vous pourriez simplement les écrire les unes à la suite des autres sur une grande feuille, mais ce ne serait pas très malin pour les retrouver après. En effet quand une voiture s’approche de la barrière du parking, il faut vite savoir si sa plaque d’immatriculation est inscrite ou non.
On aimerait donc une manière intelligente de ranger ces numéros de plaques, de sorte à répondre efficacement à ces requêtes. Plus formellement, on cherche une structure informatique dans laquelle insérer des nouvelles données puis les retrouver se fait en temps raisonnable. Ces considérations mènent à la notion d’Arbre Binaire de Recherche (BST). Mon but dans cet exposé sera d’introduire cette structure et de présenter des résultats, classiques et nouveaux, concernant son efficacité.