Les algorithmes efficaces en matière d'E/S, également connus sous le nom d'algorithmes de mémoire externe ou d'algorithmes oublieux de la mémoire cache, sont une classe d'algorithmes conçus pour traiter efficacement les données trop volumineuses pour tenir entièrement dans la mémoire principale (RAM) d'un ordinateur. Ces algorithmes sont particulièrement utiles lorsqu'il s'agit de traiter des ensembles de données massifs, tels que ceux que l'on trouve dans le traitement de données à grande échelle, la gestion de bases de données et les systèmes de fichiers. Les opérations sur les données deviennent plus coûteuses lorsque l'élément de données est situé plus haut dans la hiérarchie de la mémoire. Une opération sur des données contenues dans les registres de l'unité centrale est environ un million de fois plus rapide qu'une opération sur un élément de données situé dans une mémoire externe qui doit d'abord être extraite. Ces recherches de données sont également appelées opérations d'E/S et doivent être prises en compte lors de la conception d'un algorithme. L'objectif de ce cours est de vous familiariser avec les concepts algorithmiques importants et les techniques nécessaires pour traiter efficacement de tels problèmes. Nous travaillerons avec une hiérarchie de mémoire simplifiée, mais les notions s'étendent naturellement à des modèles plus réalistes.

Prérequis : Pour suivre ce cours avec succès, vous devez déjà avoir une connaissance de base des algorithmes et des mathématiques. Voici une courte liste de ce que vous êtes supposé savoir : - O-notation, Ω-notation, Θ-notation ; comment analyser les algorithmes - Calcul de base : manipuler des sommations, résoudre des récurrences, travailler avec des logarithmes, etc. - Théorie des probabilités de base : événements, distributions de probabilités, variables aléatoires, valeurs attendues, etc. - Structures de données de base : listes chaînées, piles, files d'attente, tas - Arbres de recherche binaires (équilibrés) - Algorithmes de tri de base, par exemple MergeSort, InsertionSort, QuickSort - Terminologie des graphes, représentations des graphes (listes d'adjacence et matrice d'adjacence), algorithmes de base des graphes (BFS, DFS, tri topologique, chemins les plus courts) Le matériel de ce cours est basé sur les notes de cours qui peuvent être trouvées sous l'onglet "ressources". Nous ne couvrirons pas tout le contenu des notes de cours. Les notes de cours sont là à la fois pour les étudiants qui n'ont pas bien compris les cours magistraux et pour les étudiants qui souhaitent approfondir les sujets. Les cours vidéo contiennent quelques erreurs mineures. Vous trouverez une liste de ces erreurs dans la section "Ressources". Si vous pensez avoir trouvé une erreur, signalez-la en cliquant sur le drapeau carré en bas du cours ou du quiz où vous avez trouvé l'erreur.