« INFO704 : Analyse d'algorithmes » : différence entre les versions
Aller à la navigation
Aller à la recherche
| Ligne 34 : | Ligne 34 : | ||
- [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://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]. |
|||
Cours 5 et 6 (27 septembre) : Diviser-pour-régner (suite et fin). |
|||
- Comparaison d'approches naïves VS diviser-pour régner. |
|||
- 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. |
|||
- [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/graphChrono.tgz Deuxième version du script graphChrono.py pour fabriquer une courbes des temps de calcul (utilise gnuplot)]. |
|||
== Historique == |
== Historique == |
||
Version du 27 septembre 2016 à 08:49
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.
Cours 5 et 6 (27 septembre) : Diviser-pour-régner (suite et fin).
- Comparaison d'approches naïves VS diviser-pour régner. - 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).
Historique
Ce cours est une refonte de INFO724 Algorithmique avancée, graphes et NP-complétude.