« 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 23 : | Ligne 23 : | ||
- Notions d'instance et de problème |
- Notions d'instance et de problème |
||
- Encodage d'une instance |
- Encodage d'une instance |
||
- Feuille de |
- Feuille de rappels et exo [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/grandO.pdf Grand-O]. |
||
- Feuille de |
- Feuille de rappels et exo [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/log_exp.pdf Logarithme et exponentielle]. |
||
- Feuille de |
- Feuille de rappels et exo [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/analyse_algo_base.pdf 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 : [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/graphChrono.tgz Script pour fabriquer une courbes des temps de calcul (utilise gnuplot)]. |
|||
== Historique == |
== Historique == |
||
Version du 19 septembre 2016 à 13:42
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).
Historique
Ce cours est une refonte de INFO724 Algorithmique avancée, graphes et NP-complétude.