« 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 24 : | Ligne 24 : | ||
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP1/tp1_enonce.pdf Sujet du TP 1] |
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP1/tp1_enonce.pdf Sujet du TP 1] |
||
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP1/fichiersTP1/ Fichiers pour le TP] |
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP1/fichiersTP1/ Fichiers pour le TP] |
||
<!-- |
<!-- |
||
| Ligne 104 : | Ligne 102 : | ||
- Feuille de rappels : logarithme [https://mycore.core-cloud.net/index.php/s/yjRYKWTIvp6VXgy Logarithme.pdf], ordres de grandeur [https://mycore.core-cloud.net/index.php/s/EDOsgVW03uaTrVH Grand-O.pdf] et correction partielle [https://mycore.core-cloud.net/index.php/s/IJVyy3hokrZIMSw Correction.pdf]. |
- Feuille de rappels : logarithme [https://mycore.core-cloud.net/index.php/s/yjRYKWTIvp6VXgy Logarithme.pdf], ordres de grandeur [https://mycore.core-cloud.net/index.php/s/EDOsgVW03uaTrVH Grand-O.pdf] et correction partielle [https://mycore.core-cloud.net/index.php/s/IJVyy3hokrZIMSw Correction.pdf]. |
||
--> |
--> |
||
TD 1 (10 septembre) : |
TD 1 (10 septembre) : |
||
| Ligne 110 : | Ligne 109 : | ||
<!-- - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/Correction_exercices_2et3.pdf Correction des questions 1 et 2 du TD] --> |
<!-- - [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/Correction_exercices_2et3.pdf Correction des questions 1 et 2 du TD] --> |
||
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/rappelsLog.pdf Fonctions mathématiques de base : polynômes, exponentielles et logarithmes] |
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/rappelsLog.pdf Fonctions mathématiques de base : polynômes, exponentielles et logarithmes] |
||
| Ligne 118 : | Ligne 116 : | ||
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S4Cours/fct_rec.pdf Théorème général.] |
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S4Cours/fct_rec.pdf Théorème général.] |
||
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S4Cours/distance_min.pdf distance minimale] |
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S4Cours/distance_min.pdf distance minimale] |
||
<!-- |
<!-- |
||
| Ligne 145 : | Ligne 142 : | ||
- Classe NP. |
- Classe NP. |
||
--> |
--> |
||
Cours 3 (2 octobre) : |
Cours 3 (2 octobre) : |
||
Version du 29 septembre 2020 à 12:31
Responsable 2020: 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
TP1 les 22/25 septembre : Analyser la complexité d'algorithmes
- Sujet du TP 1 - Fichiers pour le TP
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 - Grand-O de la notation de Landau
TD 1 (10 septembre) :
Analyses d'algorithmes
- Sujet du TD - Fonctions mathématiques de base : polynômes, exponentielles et logarithmes
Cours 2 (17 septembre) :
Algorithmes récursifs (Diviser pour régner)
- Présentation des algorithmes Diviser-pour-régner. - Théorème général. - distance minimale
TD 2 (29 septembre) : Exercices d'analyse pour des algos récursifs ("Master Theorem")
- Exercices, complexité des fonctions récursives.
Cours 3 (2 octobre) :
TD 3 (5 octobre) :
Cours 4 (13 octobre) :
TD 4 (14 octobre) :
Cours 5 (23 octobre, matin) :
TD 5 (23 octobre, après-midi) :
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.