Suivez-nous Twitter de l'UVHCPage facebook de l'UPHF

Unité d'enseignement : Structures de données avancées

» Licence Informatique

Crédits ECTS : 3
Volume horaire : 30 Heures

Langue d'enseignement Français

1. Rappels : pointeurs, S.D. statiques/dynamiques, récursivité, structure de liste simple 2. Structures linéaires : autres types de listes ; piles et files 3. Structures arborescentes : • arbres binaires, ABR¿, tas • arbres binaires équilibrés en hauteur (AVL) ¿ • introduction aux arbres n-aires, B-arbres et graphes 4. Fichiers

Compétences et savoirs enseignés

Maitrise des structures de donnes dynamiques linéaires de types listes, files et piles (rappels et compléments) ; Définition et manipulation de structures dynamiques arborescentes (arbres binaires, arbres équilibrés arbres quelconques, tas) ; Introduction aux structures de graphes. Le langage utilisé est le C, ce module venant en complément des modules d’algorithmique et programmation impérative des semestres précédents.

Références Bibliographiques

• “Types de données et algorithmes”, C. Froidevaux, M.C. Gaudel, M. Soria, ed. McGraw-Hill, coll. Informatique, 1990. • “Algorithmes et structures de données. Cours et exercices corrigés en langage C”, M. Divay, ed. Dunod, 1999.

Pré-requis obligatoires

Connaissance : - des structures compose¿es, - des structures se¿quentielles de donne¿es usuelles, - et d'un langage impe¿ratif tel que Pascal ou C

Activités

DescriptionVolume Horaire
Cours Magistraux

Cours : • Rappels sur les structures dynamiques linéaires • Arbre binaire • Autres structures d’arbres • Table de hachage • Représentation d’un graphe

9.0

Travaux Dirigés

TD : Manipulation de listes, files et piles ; Création d’un arbre binaire ; Calcul de la hauteur d’un arbre ; Ajout/Suppression/Recherche dans un arbre ; Gestion d’un arbre équilibré ; Gestion d’un tas ; Définition et utilisation d’une table de hachage ; Représentation matricielle et par listes d’un graphe.

12.0

Travaux Pratiques

TP : Dans un premier temps, application des exercices vus en TD. Ensuite, des exercices supplémentaires seront traités pour aborder des points touchant plus à l’aspect pratique du langage utilisé (le C).

9.0

Examens

Durée
Autre