« 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 31 : | Ligne 31 : | ||
- Tests empiriques de la complexité des fonctions récursives : [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/graphChrono.tgz Script pour fabriquer une courbes des temps de calcul (utilise gnuplot)]. |
- Tests empiriques de la complexité des fonctions récursives : [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/graphChrono.tgz Script pour fabriquer une courbes des temps de calcul (utilise gnuplot)]. |
||
- [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_regner.pdf Exercices, complexité des fonctions récursives]. |
|||
== Historique == |
== Historique == |
||
Version du 19 septembre 2016 à 14:07
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 d'illustration des tris - 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.
Historique
Ce cours est une refonte de INFO724 Algorithmique avancée, graphes et NP-complétude.