Enseignant responsable : René LALEMENT

Composition de l'équipe enseignante : Olivier CARTON, Jean-Philippe CHANCELIER, Étienne DURIS, Hervé GRALL, René LALEMENT, Thierry SALSET

Objectif du cours :

Les algorithmes constituent la matière première de l'enseignement de première année. La notion de forme d'algorithme, voisine de celle de pattern (Cf. Objets et patterns), permet d'identifier des méthodes de résolution de problèmes. En ce qui concerne les structures de données, l'accent sera mis sur des structures d'usage courant (ensembles, listes, tables), et leur intérêt en mathématiques discrètes (langages, graphes).

Programme :

• Structures de données
  1. Utiliser les Collections de Java
  2. Langages, analyse lexicale et automates finis
  3. Graphes et réseaux
• Formes d'algorithmes
  4. Programmation dynamique (exemple : Floyd)
  5. Algorithmes gloutons (exemple : Kruskal)
  6. Diviser pour régner (exemple : FFT)
  7. Algorithmes probabilistes (exemple : randomisation)

Modalités :
Petites classes (7 séances de 1h30) et exercices. La mise en oeuvre des algorithmes étudiés utilise le langage Java, dans l'environnement Linux.

Contrôle des connaissances - règles de validation du module :
Examen (portant également sur le module Objets et patterns).

Documents pédagogiques :
Cours polycopié (versions imprimée et en ligne) et notes de TD.

[Poly]
[Séances]
Groupes : [1] [2] [3] [4] [5] [6]
[Objets et patterns]

Last modified: Thu May 3 18:50:46 MET DST 2001