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 d'illustration des tris
- 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.

Historique

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