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.
Offrez à votre carrière le cadeau de Coursera Plus avec $160 de réduction, facturé annuellement. Économisez aujourd’hui.
(60 avis)
Détails à connaître
Ajouter à votre profil LinkedIn
6 devoirs
Découvrez comment les employés des entreprises prestigieuses maîtrisent des compétences recherchées
Obtenez un certificat professionnel
Ajoutez cette qualification à votre profil LinkedIn ou à votre CV
Partagez-le sur les réseaux sociaux et dans votre évaluation de performance
Il y a 6 modules dans ce cours
Dans ce module, nous donnons une introduction au cours sur les algorithmes efficaces en matière d'entrées-sorties. Nous discutons du modèle E/S, qui consiste en une mémoire interne de taille limitée, une mémoire externe de taille illimitée et où le transfert de données entre les deux se fait par blocs d'une taille donnée. Nous donnons un exemple simple montrant que le temps d'exécution réel d'un algorithme travaillant sur des données en mémoire externe est fortement influencé par son comportement en matière d'E/S. Enfin, nous discutons des bases de l'analyse des algorithmes dans le modèle E/S.
Inclus
5 vidéos1 lecture1 devoir
Dans ce module, nous discutons de deux techniques pour concevoir des algorithmes efficaces en termes d'E/S, en utilisant le problème de transposition de matrice comme exemple courant. La première technique est une approche "basée sur les tuiles" et conduit à un algorithme sensible à la mémoire cache. La seconde technique utilise une approche récursive et conduit à un algorithme qui ne dépend pas de la mémoire cache.
Inclus
3 vidéos1 lecture1 devoir
Lorsque nous voulons lire quelque chose dans la mémoire externe alors que la mémoire interne est pleine, nous devons faire de la place en expulsant un bloc de la mémoire interne. Le bloc à expulser est déterminé par la politique de remplacement. Dans ce module, nous présentons LRU et d'autres politiques de remplacement bien connues, et nous étudions l'efficacité en E/S de LRU par rapport à une politique de remplacement optimale.
Inclus
1 vidéo1 lecture1 devoir
Dans ce module, nous analysons l'efficacité des E/S de MergeSort et discutons de la manière de l'adapter pour la rendre plus efficace.
Inclus
2 vidéos1 lecture1 devoir
Dans ce module, nous présentons quelques structures de données efficaces en termes d'entrées-sorties : Les arbres B et les arbres tampons, ainsi qu'une file d'attente prioritaire efficace en E/S basée sur les arbres tampons.
Inclus
3 vidéos1 lecture1 devoir
Dans ce module, nous abordons le traitement en amont, une technique qui peut être utilisée pour évaluer des fonctions dites locales sur un graphe acyclique orienté.
Inclus
4 vidéos1 lecture1 devoir
Instructeur
Offert par
Recommandé si vous êtes intéressé(e) par Algorithmes
Birla Institute of Technology & Science, Pilani
University of Washington
University of Copenhagen
Stanford University
Pour quelles raisons les étudiants sur Coursera nous choisissent-ils pour leur carrière ?
Avis des étudiants
Affichage de 3 sur 60
60 avis
- 5 stars
70 %
- 4 stars
23,33 %
- 3 stars
5 %
- 2 stars
1,66 %
- 1 star
0 %
Ouvrez de nouvelles portes avec Coursera Plus
Accès illimité à plus de 7 000 cours de renommée internationale, à des projets pratiques et à des programmes de certificats reconnus sur le marché du travail, tous inclus dans votre abonnement
Faites progresser votre carrière avec un diplôme en ligne
Obtenez un diplôme auprès d’universités de renommée mondiale - 100 % en ligne
Rejoignez plus de 3 400 entreprises mondiales qui ont choisi Coursera pour les affaires
Améliorez les compétences de vos employés pour exceller dans l’économie numérique
Foire Aux Questions
L'accès aux cours et aux devoirs dépend de votre type d'inscription. Si vous suivez un cours en mode audit, vous pourrez consulter gratuitement la plupart des supports de cours. Pour accéder aux devoirs notés et obtenir un certificat, vous devrez acheter l'expérience de certificat, pendant ou après votre audit. Si vous ne voyez pas l'option d'audit :
Il se peut que le cours ne propose pas d'option d'audit. Vous pouvez essayer un essai gratuit ou demander une aide financière.
Le cours peut proposer l'option "Cours complet, pas de certificat" à la place. Cette option vous permet de consulter tous les supports de cours, de soumettre les évaluations requises et d'obtenir une note finale. Cela signifie également que vous ne pourrez pas acheter un certificat d'expérience.
Lorsque vous vous inscrivez au cours, vous avez accès à tous les cours de la Specializations, et vous obtenez un certificat lorsque vous terminez le travail. Votre certificat électronique sera ajouté à votre page de réalisations - de là, vous pouvez imprimer votre certificat ou l'ajouter à votre profil LinkedIn. Si vous souhaitez uniquement lire et visualiser le contenu du cours, vous pouvez auditer le cours gratuitement.
Si vous vous êtes abonné, vous bénéficiez d'une période d'essai gratuite de 7 jours pendant laquelle vous pouvez annuler votre abonnement sans pénalité. Après cette période, nous ne remboursons pas, mais vous pouvez résilier votre abonnement à tout moment. Consultez notre politique de remboursement complète.