« 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 75 : | Ligne 75 : | ||
Cours 2 (21 septembre) : Algorithmes récursifs (Diviser pour régner) |
Cours 2 (21 septembre) : Algorithmes récursifs (Diviser pour régner) |
||
| ⚫ | |||
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S4Cours/fct_rec.pdf Théorème général.] |
|||
TD 3 (24 septembre) : Algorithmes récursifs (Diviser-pour-régner) |
TD 3 (24 septembre) : Algorithmes récursifs (Diviser-pour-régner) |
||
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S5TD/Solution-TD.pdf Correction des derniers exos de la feuille de TD.] |
|||
| ⚫ | |||
<!-- |
|||
- Théorème général. [https://mycore.core-cloud.net/index.php/s/dX35SwoTqMaDskG Théorème général] |
|||
- Comparaison d'approches naïves VS diviser-pour régner (théorie et implémentation). |
- Comparaison d'approches naïves VS diviser-pour régner (théorie et implémentation). |
||
!-- - Problème du sous-tableau de somme maximale. --> |
!-- - Problème du sous-tableau de somme maximale. --> |
||
| Ligne 84 : | Ligne 86 : | ||
<!-- - [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 3 ( |
Cours 3 (1 octobre) : Fin correction "Diviser pour régner" + Début programmation dynamique. |
||
<!-- - Problème de la distance minimum dans un nuage de points. [https://mycore.core-cloud.net/index.php/s/fh9C1oJ4HymuJI0 Distance] |
<!-- - Problème de la distance minimum dans un nuage de points. [https://mycore.core-cloud.net/index.php/s/fh9C1oJ4HymuJI0 Distance] |
||
- Problème du rendu de monnaie. [https://mycore.core-cloud.net/index.php/s/taOj7Moq8gDy9vz Rendu monnaie] |
- Problème du rendu de monnaie. [https://mycore.core-cloud.net/index.php/s/taOj7Moq8gDy9vz Rendu monnaie] |
||
| Ligne 96 : | Ligne 98 : | ||
--> |
--> |
||
TD 4 ( |
TD 4 (5 octobre) : Programmation dynamique |
||
Cours 4 ( |
Cours 4 (8 octobre) : Complexité des problèmes |
||
<!-- - Complexité d'un problème. |
<!-- - Complexité d'un problème. |
||
- Classe P. |
- Classe P. |
||
Version du 5 octobre 2018 à 14:47
Responsable 2018: Sébastien Tavenas
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
TBA
Déroulement (2018-2019)
Cours 1 (10 septembre) : Introduction
- Exemple de différents tris - Notions d'instance et de problème - Notion de complexité asymptotique
TD 1 (14 septembre) : Rappels de mathématiques
- Grand-O de la notation de Landau - Fonctions mathématiques de base : polynômes, exponentielles et logarithmes - Correction des questions 2 et 3 du TD
TD2 (18 septembre) : Analyse des algorithmes
- Complexité d'éléments basiques : instructions, tests, boucles Pour et TantQue - Cas des algorithmes récursifs. - Analyse des algorithmes
Cours 2 (21 septembre) : Algorithmes récursifs (Diviser pour régner)
- Présentation des algorithmes Diviser-pour-régner. - Théorème général.
TD 3 (24 septembre) : Algorithmes récursifs (Diviser-pour-régner)
- Correction des derniers exos de la feuille de TD. - Problème de la multiplication de grands entiers.
Cours 3 (1 octobre) : Fin correction "Diviser pour régner" + Début programmation dynamique.
TD 4 (5 octobre) : Programmation dynamique
Cours 4 (8 octobre) : Complexité des problèmes
Cours 5 (9 octobre) : NP-complétude
TD 5 (19 octobre) : NP-complétude
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.