« INFO704 : Analyse d'algorithmes » : différence entre les versions

De Wiki du LAMA (UMR 5127)
Aller à la navigation Aller à la recherche
Aucun résumé des modifications
Aucun résumé des modifications
Ligne 31 : Ligne 31 :
- Notions d'instance et de problème
- Notions d'instance et de problème
- Encodage d'une instance
- Encodage d'une instance
- Feuille de rappels et exo <!-- [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/grandO.pdf Grand-O].
- Feuille de rappels et exercices : logarithme et ordres de grandeur. <!-- [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/grandO.pdf Grand-O].
- Feuille de rappels et exo [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/log_exp.pdf Logarithme et exponentielle].
- Feuille de rappels et exo [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/log_exp.pdf Logarithme et exponentielle].
- Feuille de rappels et exo [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/analyse_algo_base.pdf Analyse d'algorithmes, les bases]. -->
- Feuille de rappels et exo [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/analyse_algo_base.pdf Analyse d'algorithmes, les bases]. -->


Cours 3 (19 septembre) : Complexité temporelle des fonctions simples
Cours 3 (19 septembre) : Complexité des algorithmes gloutons et Diviser-pour-régner
- Algorithmes gloutons
⚫
- Retour sur la feuille de rappels et exo "Analyse d'algorithmes, les bases".
- Présentation des algorithmes Diviser-pour-régner.
⚫
<!-- - 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]. -->


Cours 4 et 5 (26 septembre) : Diviser-pour-régner (suite et fin).
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).
- 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 distance minimum dans un nuage de points.
- Problème du sous-tableau de somme maximale.
<!-- - Problème du sous-tableau de somme maximale. -->
- Problème de la multiplication de grands entiers.
- 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)].
<!-- - [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 6 et 7 (3 et 9 octobre) : Programmation dynamique.
Cours 6 et 7 (3 et 9 octobre) : Probabilités.
- Complexité en cas moyen.
⚫
- 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]
- 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]
- 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"
- [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/impression_eq.py Code à compléter (Python 2).]
- [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/impression_eq.py Code à compléter (Python 2).]
- [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 8 et 9 (17 octobre) :
Cours 8 et 9 (17 octobre) : Complexité des problèmes
- Algorithmes de type "Retour sur bande".
- Cycle Eulérien VS Cycle Hamiltonien.
- Complexité d'un problème.
- Complexité d'un problème.
- Classe P.
- Classe P.
- Types de problèmes ( décision, optimisation, existance ).
<!-- - Types de problèmes ( décision, optimisation, existence ). -->
- Réduction polynomiale.
- Réduction polynomiale.
- Algorithme de vérification.
- Algorithme de vérification.
- Classe NP.
- Classe NP.


Cours 10 et 11 (24 octobre) :
Cours 10 et 11 (24 octobre) : NP-complétude
- Problèmes NP-difficiles et NP-complets.
- Problèmes NP-difficiles et NP-complets.
- Théorème de Cook.
- Théorème de Cook.
- Preuve de NP-Complétude : Couverture des arêtes et k-coloriage.
- Preuve de NP-Complétude. <!-- : Couverture des arêtes et k-coloriage. -->


Cours 12 ( 6 novembre) :
Cours 12 ( 6 novembre) : Analyse amortie?


== Historique ==
== Historique ==

Version du 12 septembre 2017 à 00:24

Responsable 2017: Sébastien Tavenas


Quelques ressources bibliographiques

Ouvrage de référence :

  1. 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 :

  1. Wilf, Algorithms and Complexity, (1994). Disponible en ligne
  2. Garey et Johnson, Computers and intractability a guide to the theory of NP-completeness. (1979).
  3. 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.

<-- - Solutions aux exercices du cours précédent : dmin.cpp multGrandsEntiers.cpp sommeMax.cpp 

- Distance de Levenshtein Levenshtein.py Petite banque de mots.
- Devoir "Impression équilibrée"
  - Code à compléter (Python 2).
  - Code à compléter (Python 3).

-->

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.

Récupérée de « http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=INFO704_:_Analyse_d%27algorithmes&oldid=10180 »