Dans ce module, nous abordons les tableaux dynamiques : une façon d'utiliser les tableaux lorsque l'on ne sait pas à l'avance combien d'éléments seront nécessaires. Nous abordons également l'analyse amortie : une méthode permettant de déterminer le coût amorti d'une opération sur une séquence d'opérations. L'analyse amortie est très souvent utilisée pour analyser les performances des algorithmes lorsque l'analyse directe donne des résultats insatisfaisants, mais l'analyse amortie permet de montrer que l'algorithme est réellement efficace. Elle est utilisée à la fois pour l'analyse des tableaux dynamiques et sera également utilisée à la fin de ce cours pour analyser les arbres Splay.

Nous commençons ce module en examinant les files d'attente prioritaires qui sont utilisées pour planifier efficacement des tâches, que ce soit dans le contexte d'un système d'exploitation informatique ou dans la vie réelle, pour trier d'énormes fichiers, ce qui est l'élément de base le plus important pour tout algorithme de traitement des Big Data, et pour calculer efficacement les chemins les plus courts dans les graphes, un sujet que nous aborderons dans notre prochain cours. C'est pourquoi les files d'attente prioritaires ont des implémentations intégrées dans de nombreux langages de programmation, notamment C++, Java et Python. Nous verrons que ces implémentations sont basées sur l'idée géniale de stocker un arbre binaire complet dans un tableau, ce qui permet d'implémenter toutes les méthodes des files d'attente prioritaires en quelques lignes de code seulement. Nous passerons ensuite à la structure de données des ensembles disjoints qui est utilisée, par exemple, dans la connectivité dynamique des graphes et le traitement des images. Nous verrons à nouveau comment des idées simples et naturelles conduisent à une implémentation qui est à la fois facile à coder et très efficace. À l'issue de ce module, vous serez en mesure d'implémenter efficacement ces deux structures de données à partir de zéro.

Dans ce module, vous découvrirez une technique très puissante et largement utilisée, le hachage. Ses applications comprennent la mise en œuvre de langages de programmation, de systèmes de fichiers, la recherche de motifs, le stockage distribué de clés et de valeurs et bien d'autres choses encore. Vous apprendrez à mettre en œuvre des structures de données pour stocker et modifier des ensembles d'objets et des correspondances d'un type d'objet à un autre. Vous verrez que les implémentations naïves consomment d'énormes quantités de mémoire ou sont lentes, puis vous apprendrez à implémenter des tables de hachage qui utilisent une mémoire linéaire et fonctionnent en O(1) en moyenne ! Enfin, vous apprendrez comment les fonctions de hachage sont utilisées dans les systèmes distribués modernes et comment elles sont utilisées pour optimiser le stockage de services tels que Dropbox, Google Drive et Yandex Disk !

Dans ce module, nous étudions les arbres de recherche binaires, qui sont une structure de données permettant d'effectuer des recherches sur des ensembles ordonnés changeant dynamiquement. Vous découvrirez les nombreuses difficultés rencontrées dans l'accomplissement de cette tâche et les moyens de les surmonter. Pour ce faire, vous devrez apprendre la structure de base des arbres de recherche binaires, comment insérer et supprimer sans détruire cette structure, et comment s'assurer que l'arbre reste équilibré.

Dans ce module, nous poursuivons l'étude des arbres de recherche binaires. Nous étudions quelques applications non triviales. Nous étudions ensuite le nouveau type d'arbres de recherche équilibrés - les arbres Splay. Ils s'adaptent dynamiquement aux requêtes et sont optimaux à bien des égards.