Cours donnés par des enseignants d'autres sections
ALGORITHMIQUE
12X001
A. CASTEIGTS · F. RAYNAUD
Semestre d’automne
- Crédits ECTS
- 6
- Pré-requis
- complexité et calculabilité
- Évaluation
- examen écrit
- Sessions d’examen
- février - septembre
Volume d’enseignement
| Période | Cours | Exercices | TP | Total |
|---|---|---|---|---|
| Par semaine | 2 | 2 | None | 4 |
| Par semestre | 28 | 28 | None | 56 |
Cours
2par semaine
28par semestre
Exercices
2par semaine
28par semestre
TP
Nonepar semaine
Nonepar semestre
Total
4par semaine
56par semestre
Objectifs
Ce cours est un approfondissement aux concepts et techniques de l’algorithmique.
Contenu
On étudie les mécanismes utilisés par un ordinateur pour résoudre un problème donné, pour mesurer l’efficacité d’un algorithme proposé et pour comparer cet algorithme à d’autres solutions possibles. De nombreux algorithmes et techniques sont présentés et étudiés, de façon à bien comprendre leur conception et leur analyse.
Les sujets suivants seront abordés :
- Structures de données avancées.
- Algorithmes gloutons.
- Diviser pour conquérir.
- Programmation dynamique.
- Backtracking.
- Branch and bound.
- Algorithmes d’approximation.
Documentation : « Computer Algorithms », Computer ScienceS Press, 1998 – E. Horowitz, S. Sahni, S. Rajasekaran.