Filière étudiant » 3ème année » Dépt informatique » Programme

Programme 2017-2018

 

Module c2i4-1: Algorithmique des graphes

 

Volume horaire : 12 h de cours, 12 h de TD.

 

Responsable

Emmanuelle Frenoux

 

Objectifs

L'objectif de ce cours est de sensibiliser l'étudiant aux différents choix possibles de structures de données en s'appuyant sur l'étude de complexité en temps et en espace des algorithmes.

 

Prérequis

Connaissance des instructions de base d'un langage de programmation.

 

Contenu

Les structures de données de base sont présentées dans ce cours, ainsi que les algorithmes de recherche, d'adjonction et de suppression d'items dans ces structures. Les étudiants apprennent ainsi l'implémentation et la manipulation des structures suivantes : tableaux, listes chaînées, arbres binaires, arbres équilibrés et graphes. Les algorithmes et structures sont également étudiés du point de vue de la complexité en espace et en temps.
La notion de récursivité est introduite et utilisée pour traiter facilement les structures de données définies de façon récursive. Les différentes techniques de hachage sont abordées.
Quelques méthodes de tri sont étudiées et leurs complexités sont comparées, ainsi qu'une introduction au calcul de parcours optimum de certaines de ces structures. Le cours et ses exemples font appel à un langage algorithmique, détaché de tout langage de programmation, tandis que les travaux pratiques sont réalisés en langage C.

 

Evaluation (à titre indicatif seulement)

Contrôle continu : 2 contrôles de connaissance et un examen final.

 

Bibliographie

- Types de données et algorithmes de C.Froidevaux, MC Gaudel et M.Soria chez Mc Graw-Hill
- Introduction à l'algorithmique de T.Cormen, C. Leiserson et R.Rivest chez Dunod