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 (13 septembre) : Introduction

- Exemple "Tri lent" triLent.sage
- Notions d'instance et de problème
- Rappels sur les graphes (nombres de Ramsey)
    - Programme qui calcule les nombres de Ramsey (les premiers du moins...)
- Encodage d'une instance

Historique

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