03 - Structures de données persistantes : Concilier amortissement et persistance : de l'importance de la paresse

Xavier LeroyCollège de FranceScience du logicielAnnée 2022-2023Structures de données persistantesConcilier amortissement et persistance : de l'importance de la paresseL'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.