« 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 55 : | Ligne 55 : | ||
- Complexité en cas moyen. |
- Complexité en cas moyen. |
||
- Complexité d'un algorithme probabiliste. |
- Complexité d'un algorithme probabiliste. |
||
<-- - Solutions aux exercices du cours précédent : [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/solutionsDPR/dmin.cpp dmin.cpp] [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/solutionsDPR/multGrandsEntiers.cpp multGrandsEntiers.cpp] [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/solutionsDPR/sommeMax.cpp sommeMax.cpp] |
<!-- - Solutions aux exercices du cours précédent : [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/solutionsDPR/dmin.cpp dmin.cpp] [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/solutionsDPR/multGrandsEntiers.cpp multGrandsEntiers.cpp] [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/solutionsDPR/sommeMax.cpp sommeMax.cpp] |
||
- Distance de Levenshtein [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/Levenshtein.py Levenshtein.py] [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/animaux Petite banque de mots]. |
- Distance de Levenshtein [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/Levenshtein.py Levenshtein.py] [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/animaux Petite banque de mots]. |
||
- Devoir "Impression équilibrée" |
- Devoir "Impression équilibrée" |
||
Version du 12 septembre 2017 à 00:25
Responsable 2017: 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
TP les 10 octobre et 6 novembre.
Déroulement (2017-2018)
Cours 1 et 2 (12 septembre) : Introduction
- Exemple "Tri lent" - Notions d'instance et de problème - Encodage d'une instance - Feuille de rappels et exercices : logarithme et ordres de grandeur.
Cours 3 (19 septembre) : Complexité des algorithmes gloutons et Diviser-pour-régner
- Algorithmes gloutons - Présentation des algorithmes Diviser-pour-régner.
Cours 4 et 5 (26 septembre) : Complexité des algorithmes Diviser-pour-régner (suite et fin) + Programmation dynamique.
- Comparaison d'approches naïves VS diviser-pour régner (théorie et implémentation). - Problème de la distance minimum dans un nuage de points. - Problème de la multiplication de grands entiers.
Cours 6 et 7 (3 et 9 octobre) : Probabilités.
- Complexité en cas moyen. - Complexité d'un algorithme probabiliste.
Cours 8 et 9 (17 octobre) : Complexité des problèmes
- Complexité d'un problème. - Classe P. - Réduction polynomiale. - Algorithme de vérification. - Classe NP.
Cours 10 et 11 (24 octobre) : NP-complétude
- Problèmes NP-difficiles et NP-complets. - Théorème de Cook. - Preuve de NP-Complétude.
Cours 12 ( 6 novembre) : Analyse amortie?
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.