« INFO704 : Analyse d'algorithmes » : différence entre les versions
Aller à la navigation
Aller à la recherche
Aucun résumé des modifications |
Aucun résumé des modifications |
||
| Ligne 11 : | Ligne 11 : | ||
# Wilf, Algorithms and Complexity, (1994). [http://www.math.upenn.edu/%7Ewilf/AlgoComp.pdf Disponible en ligne] |
# Wilf, Algorithms and Complexity, (1994). [http://www.math.upenn.edu/%7Ewilf/AlgoComp.pdf Disponible en ligne] |
||
# Garey et Johnson, Computers and intractability a guide to the theory of NP-completeness. (1979). |
# Garey et Johnson, Computers and intractability a guide to the theory of NP-completeness. (1979). |
||
# Paschos, Complexité et approximation polynomiale, (2004). |
<!-- # Paschos, Complexité et approximation polynomiale, (2004). --> |
||
# Hopcroft et Ullman, Introduction to automata theory, languages, and computation, (1979). |
# Hopcroft et Ullman, Introduction to automata theory, languages, and computation, (1979). |
||
== TP == |
== TP == |
||
Version du 12 septembre 2017 à 00:11
Responsable 2017: Sébastien Tavenas
Quelques ressources bibliographiques
Ouvrage de référence :
- 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 :
- Wilf, Algorithms and Complexity, (1994). Disponible en ligne
- Garey et Johnson, Computers and intractability a guide to the theory of NP-completeness. (1979).
- 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.