« INFO704 : Analyse d'algorithmes » : différence entre les versions
Aller à la navigation
Aller à la recherche
| Ligne 32 : | Ligne 32 : | ||
- [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/fct_rec.pdf Théorèmes relatifs à la complexité temporelle des fonctions récursives]. |
- [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/fct_rec.pdf Théorèmes relatifs à la complexité temporelle des fonctions récursives]. |
||
- [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/exo_div_pour_regner.pdf Exercices, complexité des fonctions récursives]. |
- [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/exo_div_pour_regner.pdf Exercices, complexité des fonctions récursives]. |
||
- [http://www.csail.mit.edu/~thies/6.046-web/master.pdf Exercices supplémentaires sur l'application du "Théorème maître" (sur la page de Bill |
- [http://www.csail.mit.edu/~thies/6.046-web/master.pdf Exercices supplémentaires sur l'application du "Théorème maître" (sur la page de Bill Thies, MIT)]. |
||
- [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/distance_min.pdf Problème du calcul de la distance minimum entre deux points]. |
- [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/distance_min.pdf Problème du calcul de la distance minimum entre deux points]. |
||
- [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/distance_min.tgz Programme C++ pour comparer les temps d'exécution entre la méthode naïve et DPR pour le problème de la distance minimum entre deux points]. |
- [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/distance_min.tgz Programme C++ pour comparer les temps d'exécution entre la méthode naïve et DPR pour le problème de la distance minimum entre deux points]. |
||
Version du 26 septembre 2016 à 14:22
Responsable pour 2015--2016: Xavier Provençal
- Xavier Provençal (CM/TD/TP)
Quelques ressources bibliographiques
Ouvrage de référence :
- 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 :
- Wilf, Algorithms and Complexity, (1994). Disponible en ligne
- Garey et Johnson, Computers and intractability a guide to the theory of NP-completeness. (1979).
- Paschos, Complexité et approximation polynomiale, (2004).
- 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 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. - Programme C++ pour comparer les temps d'exécution entre la méthode naïve et DPR pour le problème de la distance minimum entre deux points.
Historique
Ce cours est une refonte de INFO724 Algorithmique avancée, graphes et NP-complétude.