Vous êtes ici

  1. Accueil
  2. Structure de données

Structure de données

Structure de données

En pratique :

Volume horaire de cours : 12
Volume horaire global de TD : 18
Volume horaire global de TP : 20
Langue principale : français

Compétences à acquérir

Ce cours présente des structures de données linéaires et arborescentes permettant notamment la mise en œuvre des ensembles et des files de priorité ainsi que les opérations qui leur sont associées. Ces structures étant principalement de nature inductive, la preuve de la correction des algorithmes reposera sur le principe de preuve par induction.
Plus précisément, les compétences visées sont les suivantes :

  • Connaître les structures de données et les complexités des opérations
  • Savoir définir une structure indépendamment de sa mise en œuvre
  • Savoir comparer les structures de données
  • Identifier les contextes d'utilisation des différentes structures de données
  • Savoir montrer la correction des algorithmes

Modalités d’organisation et de suivi

Description

  • Introduction, méthodologie à base d'induction et définitions des types abstraits algébriques
  • Types abstraits algébriques linéaires - Mises en œuvre basiques et complexité des opérations
  • Le type abstrait Ensemble et mises en œuvre arborescentes
      Les ABR
  • Les AVL
  • Les BTree
  • Les tables de hachage (TP)
  • Les files de priorités
      Les Tas
  • Les minimiers binaires

Bibliographie, lectures recommandées

Introduction à l’algorithme, T. Cormen, C. Leiserson, R. Rivest, C. Stein, Ed. Dunod
Conception d'algorithmes, P. Bosc, M. Guyomard, L. Miclet, Ed Eyrolles
Types de données et algorithmes, C. Froidevaux, M-C. Gaudel, M. Soria, Ediscience
Structures de données et méthodes formelles, M. Guyomard, Springer


Pré-requis

Pré-requis obligatoires

Cours Algorithmique 1 et 2 : T5IC013M
Cours Analyse continue et discrète : T6CS021M