Algorithmes et structure des données linéaires

Vous êtes ici :

Algorithmes et structure des données linéairesCode de l'UE : HLIN301

Présentation

Cet enseignement fait suite à l'UE d'introduction à l'algorithmique et à la programmation de 1ère année. On y étudie :

  • L'analyse des algorithmes :
    Preuve d'un algorithme, invariant de boucles,
    Evaluation de la complexité en temps d'un algorithme, ordre de grandeur, principales classes de complexité.
  • Des structures de données élémentaires : listes chaînées, files, piles, files de priorité, arbre binaire.
  • Des algorithmes élémentaires : algorithme de recherche et sélection, de tri, de parcours d'arbre.

Objectifs

  • Savoir écrire des algorithmes de base sur les structures de données linéaires : tableaux, listes chaînées, piles, files
  • Savoir justifier un algorithme : énoncer des arguments attestant son arrêt et sa justesse
  • Savoir évaluer la complexité en temps d'un algorithme
  • Connaître les grandes classes de complexité
  • Savoir appliquer quelques principes de base pour obtenir des algorithmes efficaces :
    tri, dichotomie, diviser pour régner
  • Connaître les définitions élémentaires sur les arbres binaires et savoir écrire des algorithmes très simples opérant sur les arbres.

Pré-requis recommandés

Il est fortement recommandé pour suivre cet enseignement d'avoir validé les UE d'algorithmique et programmation de 1ère année.

Volume horaire

  • CM : 16.5
  • TD : 24
  • TP : 9

Syllabus

Introduction à l'algorithmique
Th CORMEN, Ch LEISERSON, R. RIVEST
Editions Dunod

Diplômes intégrant cette UE

En bref

Crédits ECTS 5

Nombre d'heures 49 HE

Période de l'année
S3

Langue d'enseignement
fr

Contact(s)

Contact(s) administratif(s)

Philippe JANSSEN (philippe.janssen @ umontpellier.fr)