« 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 145 : | Ligne 145 : | ||
- [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/impression_eq-python3.py Code à compléter (Python 3).] |
- [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/impression_eq-python3.py Code à compléter (Python 3).] |
||
--> |
--> |
||
Cours 4 (29 septembre) : |
Cours 4 (29 septembre) : |
||
| Ligne 157 : | Ligne 156 : | ||
- Classe NP. |
- Classe NP. |
||
--> |
--> |
||
TD2 (2 octobre) : |
TD2 (2 octobre) : |
||
| Ligne 166 : | Ligne 164 : | ||
- Cas des algorithmes récursifs. |
- Cas des algorithmes récursifs. |
||
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S3TD/BasesAnalyse.pdf Analyse des algorithmes] |
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S3TD/BasesAnalyse.pdf Analyse des algorithmes] |
||
!-- - 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)]. |
- 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_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 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]. |
||
--> |
--> |
||
| Ligne 184 : | Ligne 182 : | ||
-- - [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)]. |
-- - [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)]. |
||
--> |
--> |
||
Cours 5 (13 octobre) : |
Cours 5 (13 octobre) : |
||
| Ligne 192 : | Ligne 189 : | ||
- Preuve de NP-Complétude. !-- : Couverture des arêtes et k-coloriage. -- |
- Preuve de NP-Complétude. !-- : Couverture des arêtes et k-coloriage. -- |
||
--> |
--> |
||
TD 4 (14 octobre) : |
TD 4 (14 octobre) : |
||
| Ligne 199 : | Ligne 195 : | ||
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S8Cours/Levenshtein.pdf Correction sur la distance de Levenshtein.] |
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S8Cours/Levenshtein.pdf Correction sur la distance de Levenshtein.] |
||
--> |
--> |
||
TD 5 (23 octobre) : |
TD 5 (23 octobre) : |
||
Version du 7 septembre 2020 à 10:05
Responsable 2019: Sébastien Tavenas
Adresse couriel : sebastien.tavenas@univ-smb.fr
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
Dates provisoires :
- 22/25 septembre - 9 octobre - 16 octobre
Déroulement (2020)
Cours 1 (7 septembre) : Introduction
- Introduction - Exemple de différents tris - Notions d'instance et de problème - Notion de complexité asymptotique
Cours 2 (10 septembre) :
TD 1 (17 septembre) :
Cours 3 (18 septembre) :
Cours 4 (29 septembre) :
TD2 (2 octobre) :
TD 3 (5 octobre) :
Cours 5 (13 octobre) :
TD 4 (14 octobre) :
TD 5 (23 octobre) :
Annales Examen
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.