INFO704 : Analyse d'algorithmes

Responsable 2017: Sébastien Tavenas

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. Hopcroft et Ullman, Introduction to automata theory, languages, and computation, (1979).

TP

TP les 10 octobre et 6 novembre.

Déroulement (2017-2018)

Cours 1 et 2 (12 septembre) : Introduction

- Exemple "Tri lent" 
- Notions d'instance et de problème
- Encodage d'une instance
- Feuille de rappels et exo 

Cours 3 (19 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 4 et 5 (26 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 6 et 7 (3 et 9 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 8 et 9 (17 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 10 et 11 (24 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.

Cours 12 ( 6 novembre) :

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.