INFO704 : Analyse d'algorithmes

Responsable 2017: Sébastien Tavenas

<?-- * 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é "Introduction à 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

<?--
- Énoncé du TP, première partie : tp-part-1.pdf.
- Énoncé du TP, deuxième partie : tp-part-2.pdf.
- Programmes pour générer des instances : gen3SAT.py genCA.py 3SATtoCA.py.
-->

Déroulement (2016-2017)

Cours 1 et 2 (12 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.

Cours 5 et 6 (27 septembre) : Diviser-pour-régner (suite et fin).

- Comparaison d'approches naïves VS diviser-pour régner (théorie et implémentation).
- Problème de la distance minimum dans un nuage de points.
- Problème du sous-tableau de somme maximale.
- Problème de la multiplication de grands entiers.
- Deuxième version du script graphChrono.py pour fabriquer une courbes des temps de calcul (utilise gnuplot).

Cours 7 et 8 (4 octobre) : Programmation dynamique.

- Solutions aux exercices du cours précédent : dmin.cpp  multGrandsEntiers.cpp  sommeMax.cpp
- Distance de Levenshtein Levenshtein.py Petite banque de mots.

Cours 9 et 10 (18 octobre) :

- Algorithmes de type "Retour sur bande".
- Cycle Eulérien VS Cycle Hamiltonien.
- Complexité d'un problème.
- Classe P.
- Types de problèmes ( décision, optimisation, existance ).
- Réduction polynomiale.
- Algorithme de vérification.
- Classe NP.

Cours 11 et 12 (25 octobre) :

- Problèmes NP-difficiles et NP-complets.
- Théorème de Cook.
- Preuve de NP-Complétude : Couverture des arêtes et k-coloriage.

Historique

Ce cours était donné précédemment par Xavier Provençal. Ce cours est une refonte de INFO724 Algorithmique avancée, graphes et NP-complétude.