Algorithmique des structures de données arborescentes

Informations

Langue d'enseignement : Anglais
Crédits ECTS: 6

Programme

  • Heures d'enseignement dispensées à l'étudiant : 48 heures
  • Temps de travail personnel : 102 heures

Objectifs et compétences

Objectifs :
L'objectif principal portera sur les mises en oeuvre statiques ou dynamiques de structures de données arborescentes - arbre binaire avec une loi d'ordre (ABR, AVL, B-arbre), dictionnaire, table de hash, tas et file de priorité.

L'étudiant devra mettre en oeuvre des compétences d'abstraction, de calcul de complexité et de mise en oeuvre d'algorithmes récursifs adaptés.

En partant d'un problème "fil d'Ariane", les étudiants seront amenés à le résoudre successivement à l'aide de plusieurs structures de données. Pour chaque structure de données, une comparaison des constructions statiques et dynamiques, l'étude de la complexité algorithmique associée,et l'écriture d'algorithmes récursifs adaptés seront abordées.

A l'aide des compétences acquises lors du semestre précédent au sein de l'UE "Programmation Fonctionnelle", les étudiants seront amenés à mettre en oeuvre l'implémentation en langage Caml des structures de données abordées.

Les compétences et connaissances acquises lors des UEs "Algorithmique des tableaux" et "Algorithmique des structures de données élémentaires" (ou des UEs équivalentes) sont un pré-requis.

Organisation pédagogique

le mode de fonctionnement de l'UE est présenté au début des enseignements

Contrôle des connaissances

La première session est constituée

> d'une note de contrôle continu (coef. 0.5)

> d'une note d'examen écrit terminal (1h30) (coef. 0.5)

pour l'obtention d'une note = 0.5*Examen écrit terminal + 0.5*Contrôle continu

La seconde session est constituée

> du report de la note de session 1 de contrôle continu

> d'une note d'examen écrit terminal (1h30)

pour l'obtention d'une note finale = 0.5*Examen écrit terminal + 0.5*max(Contrôle continu, Examen écrit terminal)

En seconde session, si l'effectif est faible un oral pourra être proposé.

Lectures recommandées

l'ensemble des références bibliographiques est communiqué au début des enseignements

Responsable de l'unité d'enseignement

- Non défini -

Enseignants

la composition de l'ensemble de l'équipe pédagogique est communiquée au début des enseignements