Xavier Leroy
Collège de France
Science du logiciel
Année 2022-2023
Structures de données persistantes
Concilier amortissement et persistance : de l'importance de la paresse
L'amortissement est un principe de conception de structures de données qui vise à garantir un coût moyen par opération sur toute séquence d'opérations, le coût élevé de certaines opérations étant amorti par le coût faible d'opérations précédentes. Après un rappel des principes de l'amortissement et de l'analyse en temps amorti, le cours montrera des exemples de structures de données persistantes qui ont une complexité O(1) à condition d'être utilisées de manière linéaire. Nous étudierons ensuite l'approche d'Okasaki pour concilier amortissement et persistance générale (non linéaire), utilisant l'évaluation paresseuse (à la demande) de certains calculs.
Sciences du logiciel - Xavier Leroy