Structure de données [T6IS313M]

Structure de données [T6IS313M]

En pratique

Nature
Elément constitutif
Volume horaire de TP
20
Volume horaire de TD
16
Volume horaire de CM
14
Volume horaire de travail personnel
34
Langue d'enseignement
Français

Description du contenu de l'enseignement

Ce module est dédié à l'étude, à la mise en oeuvre et à la comparaison théorique et pratique des principales structures de données utilisées en programmation et mettant en oeuvre les types abstrait Liste, Ensemble et Map comme :

  •  les structures séquentielles : Listes, Files, Piles
  •  les structures arborescentes : les arbres de recherches (ABR, AVL, SplayTrees, BTree)
  •  les tables de hachage

Les algorithmes permettant la gestion de ces structures pouvant être itératifs ou récursifs, on insistera sur la méthodologie employée :

  • pour une approche récursive le cas de base, le cas général et l'hypothèse de récurrence seront explicités ;
  • pour une approche itérative, l'invariant, les conditions initiales, d'arrêt et la progression seront exposés.                                                                                                                                

Dans tous les cas, on s'efforcera de justifier ses propositions.

Organisation

Modalités d'organisation et de suivi

  • Introduction, retour sur la méthodologie à base d'invariant puis de récurrence                                                                                                                              
  • Notion de types abstraits algébriques et retour sur les 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
  • Le type abstrait file de priorités
    • Mise en oeuvre par minimiers binaires
    • Mise en oeuvre par Tas
  • Le type Map et les tables de hachage

 

Informations pédagogiques

Compétences à acquérir

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

Pré-requis recommandés

Algo1 - T5CC023M et Algo2 - T5CC013M

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
Dernière modification : mer, 06/01/2021 - 18:14