Présentation du cours
L'écriture d'un programme est souvent l'objet
d'un compromis entre son temps d'exécution (efficacité algorithmique
de la solution codée) et son temps de développement
(réflexion,
implémentation et débuggage). Deux attitudes caricaturales
sont :
a) rechercher la solution la plus efficace théoriquement
(c.-à-d. quand n temps
vers l'infini) même si elle est très compliquée à implémenter
ou b) implémenter
la première idée venue.
L'objectif de ce cours est d'essayer de trouver un équilibre
entre ces deux façons d'agir,
idéalement de
développer rapidement et de façon sûre une
solution efficace sans avoir à débugguer. Le choix
de la solution à retenir repose typiquement sur
le temps disponible d'une part et les caractéristiques particulières
des instances à résoudre d'autre part (taille, décomposition
éventuelle,...). Le choix de la structure de données
est également
un paramètre
crucial d'efficacité.
Dans ce cours, nous étudirons
différents
problèmes
(algorithmiques purs) que nous cherchons à résoudre effectivement en écrivant
un programme (dans le langage de votre choix - C/C++/Java/Ocaml/...)
qui sera testé/validé sur des jeux de données.
L'objectif de ce
cours est à la fois d'obtenir une compréhension
profonde des algorithmes classiques et de leurs performances réelles,
et d'apprendre à résoudre efficacement et
effectivement un problème algorithmique.
Le cours se déroulera en salle machine et se décomposera
en essentiellement deux types de sessions:
- Algorithmique avancée et implémentation des algorithmes :
- algorithmes classiques : enveloppe convexe, couplage
parfait, flot, systèmes dans Z/2Z, composantes
fortement connexes, branch-and-bound, algorithme de Gauss,...
- structures de données classiques : différentes
tables de hachage, tables dynamiques, tas, union-find,...
- Résolution effective de problèmes :
- choisir la structure de données, écrire un pseudo-code
lisible, implémenter, éviter d'avoir à débugguer
- en temps limité ou non
Ce cours a également pour but de préparer
trois équipes
d'étudiants (environ) au concours d'algorithmique et programmation
« ACM
International Collegiate Programming Contest », et
dans le cadre de cette préparation, de constituer une
base de données
d'algorithmes écrits de façon lisible et efficace
qui accompagnera nos candidats (un listing de 50 pages de code
est autorisé lors des épreuves).
 The
lectures can be done in english upon request.
L'ouvrage de référence :
Autres ouvrages utiles
- T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction
to Algorithms. MIT Press, 2nde éd. (2001), ISBN:
0-262-03293-7. Traduit en français par
X. Cazin et G.-L. Kocher, Dunod (2002), ISBN: 2-10-003922-9.
Archives 2004-2005
Le cours
Les TPs
Partiel et Examen
Base de données
Liens
Le concours ACM :
|
