INFO704 : Analyse d'algorithmes

Responsable pour 2015--2016: Xavier Provençal

• Xavier Provençal (CM/TD/TP)

Quelques ressources bibliographiques

Ouvrage de référence :

1. Cormen, Leiserson, Rivest et Stein, Algorithmique, 3e edition (2009). ( Aussi appelé "Introductino à l'algorithmique" pour les deux premières éditions )

Autres références bibliographiques :

1. Wilf, Algorithms and Complexity, (1994). Disponible en ligne
2. Garey et Johnson, Computers and intractability a guide to the theory of NP-completeness. (1979).
3. Paschos, Complexité et approximation polynomiale, (2004).
4. Hopcroft et Ullman, Introduction to automata theory, languages, and computation, (1979).

TP

À venir.

Déroulement (2016-2017)

Cours 1 et 2 (13 septembre) : Introduction

- Exemple "Tri lent" Programme C/gtk pour illustrer différents algorithmes de tri.
- Notions d'instance et de problème
- Encodage d'une instance
- Feuille de rappels et exo Grand-O.
- Feuille de rappels et exo Logarithme et exponentielle.
- Feuille de rappels et exo Analyse d'algorithmes, les bases.

Cours 3 et 4 (20 septembre) : Complexité temporelle des fonctions simples

- Retour sur la feuille de rappels et exo "Analyse d'algorithmes, les bases".
- Tests empiriques de la complexité des fonctions récursives : Script pour fabriquer une courbes des temps de calcul (utilise gnuplot).
- Théorèmes relatifs à la complexité temporelle des fonctions récursives.
- Exercices, complexité des fonctions récursives.
- Exercices supplémentaires sur l'application du "Théorème maître" (sur la page de Bill thies, MIT).
- Problème du calcul de la distance minimum entre deux points.
- Programme C++ pour comparer les temps d'exécution entre la méthode naïve et DPR pour le problème de la distance minimum entre deux points.

Historique

Ce cours est une refonte de INFO724 Algorithmique avancée, graphes et NP-complétude.