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.
Sciences du logiciel - Xavier Leroy