Xavier Leroy

Collège de France

Science du logiciel

Année 2022-2023

Structures de données persistantes

À la recherche du vecteur perdu : limites théoriques et conclusions

Jusqu'à quel point une structure de données persistante peut être efficace ? Y a-t-il forcément un surcoût par rapport à une structure transiente ? Le dernier cours essaiera de répondre à ces questions, d'abord en passant en revue les meilleures implémentations connues des tableaux persistants, purement fonctionnelles ou non, puis en étudiant les bornes inférieures sur l'efficacité des modèles de calcul « LISP pur » et « LISP impur » établies par Ben-Armarm, Galil, et Pippenger.