TD/TP : Eric Thierry & Alexandre Talon & Paul Iannetta

Présentation

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, implantation 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.
Le but de ce module est de s’entraîner à la résolution effective de problèmes algorithmiques. Pour cela,
il faudra trouver un équilibre entre ces deux façons d’agir.
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 module, nous étudierons différents problèmes (algorithmiques purs) que nous cherchons à résoudre effectivement
en écrivant un programme (en C, C++, Java…) qui sera testé/validé sur des jeux de données.
Les objectifs sont les suivants :
– Mieux comprendre comment se comportent en pratique les algorithmes classiques (de graphes, arithmétique, géométrie…)
– S’exercer à écrire des programmes rapidement, mais surtout éviter au maximum d’avoir à déboguer (notamment en écrivant d’abord un pseudo-code)
– Enfin, pour ceux qui le souhaitent, se préparer au concours de programmation ACM-ICPC. La première étape de ce
concours a lieu chaque année fin octobre, en général deux équipes de 3 personnes y participent à l’ENS Lyon.
Le module aura lieu au second semestre, sous la forme de TD en salle machine (2h par semaine).
Plan
Voici à titre indicatif une liste des sujets qui seront abordés :
– Graphes : plus courts chemins, composantes fortement connexes, flots, couplages, union-find
– Géométrie : enveloppe convexe, algorithmes de balayage, tests d’inclusion
– Arithmétique : tests de primalité
Références
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms (Second Edition).
Site du concours ACM-ICPC : http://icpc.baylor.edu/

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, implantation et débuggage). Deux attitudes caricaturales sont :

  1. 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
  2. implémenter la première idée venue.

Le but de ce module est de s’entraîner à la résolution effective de problèmes algorithmiques. Pour cela, il faudra trouver un équilibre entre ces deux façons d’agir.

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 module, nous étudierons différents problèmes (algorithmiques purs) que nous cherchons à résoudre effectivement en écrivant un programme (en C, C++, Java…) qui sera testé/validé sur des jeux de données.

Les objectifs sont les suivants :

  • Mieux comprendre comment se comportent en pratique les algorithmes classiques (de graphes, arithmétique, géométrie…)
  • S’exercer à écrire des programmes rapidement, mais surtout éviter au maximum d’avoir à déboguer (notamment en écrivant d’abord un pseudo-code)
  • Enfin, pour ceux qui le souhaitent, se préparer au concours de programmation ACM-ICPC. La première étape de ce concours a lieu chaque année fin octobre, en général deux équipes de 3 personnes y participent à l’ENS Lyon.

Le module aura lieu au second semestre, sous la forme de TD/TP en salle machine (3h par semaine).

Plan

Voici à titre indicatif une liste des sujets qui seront abordés :

  • Graphes : plus courts chemins, composantes fortement connexes, flots, couplages, union-find
  • Géométrie : enveloppe convexe, algorithmes de balayage, tests d’inclusion
  • Arithmétique : tests de primalité

Références

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms (Second Edition).
  • Site du concours ACM-ICPC : http://icpc.baylor.edu/