2. Diplômes
  3. Licence informatique
  4. Licence 2
  5. Semestre 4
  6. majeure
  7. algorithmique-et-pro
  8. Algorithmique

Algorithmique

Objectifs

Les compétences attendues à la fin de ce cours sont.

  1. Faire la différence entre la description formelle d'un type (TDA) et une implémentation de ce type (type concret manipulé).
  2. Savoir choisir le bon TDA pour représenter des données concrètes suivant des critères de complexité en temps des opérations sur ces données.
  3. Savoir choisir la bonne implémentation d'un TDA suivant des critères de complexité en temps des opérations sur des données concrètes. 
  4. Connaître des implémentations naives de TDAs classiques (pile, file, liste, arborescente). 
  5. Connaître des implémentations efficaces de certains TDAs classiques (pile, file, liste, ABR, tables de hachage). 
  6. Savoir calculer la complexité en temps d'algorithmes séquentiels et de quelques algorithmes récursifs. 

Plan du cours

Ce cours présente des Types de Données Abstraits (TDA) classiques ainsi que des implémentations possibles. Il est constitué de 5 chapitres.

  1. Niveau de description. Ce chapitre présente notre modèle de machine ainsi que le langage de description des structures de données et des opérations associées.  Il présente également la notion de types atomiques et composés. 
  2. Eléments de complexité. Dans ce chapitre on présente les notions de complexité en temps et en espace. On voit également comment on mesure la complexité en temps d'un algorithme en fonction de la taille des entrées. Les notations asymptotiques sont également rappelées. 
  3. TDA. Dans ce chapitre on définit la notion de TDA et la différence entre un type concret et un type abstrait. Nous présenterons ensuite quelques TDAs classiques linéaires (pile, file, liste, ensemble dynamique, etc.).
  4. Types inductifs. Ce chapitre introduit des TDAs arborescents (arbres, ABR, Tas, etc.).  Il présentera également une implémentation efficace d'un ABR.  Ce chapitre introduit également les équations récurrentes et un théorème général de résolution. Une application pour calculer la complexité en temps des algorithmes récursifs est également donnée. 
  5. Tables de Hachage. Ce dernier chapitre présente les tables à adressage ouvert ainsi que quelques fonctions de hachage usuelles. 

Description des TP

Aucun TP

Connaissances requises

Algorithmique de L1 introduisant les tableaux et leur manipulation ainsi que les constructions classiques d'algorithmique (fonctions, procédures, types atomiques, constructions de nouveaux types, variables, branchements itératifs et conditionnels)

RSE (Responsabilité Sociale et Environnementale)

Bibliographie

  1. T. H. Cormen, C. E. Leiserson, R. L. Rivest et C. Stein. Introduction à l'algorithmique. MIT press, 2002.
  2. A. Arnold et I. Guessarian. Mathématiques pour l'informatique. Masson, 1997.
  3. D. E. Knuth. The art of computer programming I: fundamental algorithms. Addison-Wesley, 1973.