Structures de données persistantes

L'efficacité d'un logiciel dépend beaucoup de la manière dont il organise les données qu'il manipule en structures algorithmiquement efficaces. La plupart des structures de données connues aujourd'hui sont transientes : les mises à jour de la structure s'effectuent par modification en place, rendant inaccessible l'état de la structure avant modification. Au contraire, les structures de données persistantes conservent l'historique complet des données : tout se passe comme si une mise à jour recréait une nouvelle structure, indépendante de la structure précédente ; cela peut se réaliser de manière efficace en temps et en espace mémoire à condition d'utiliser des algorithmes ingénieux. Ces structures de données persistantes efficaces jouent un rôle crucial pour la programmation purement fonctionnelle, où les programmes prennent la forme de définitions mathématiques sur lesquelles on peut raisonner de manière équationnelle. Le cours présentera les principales structures de données persistantes connues aujourd'hui, certaines implémentées de manière purement fonctionnelle et d'autres à l'aide de modifications impératives cachées, et décrira les principes généraux qui guident la conception de ces structures persistantes ainsi que leur analyse de complexité.