« 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 1 : Ligne 1 :
Responsable 2017: [http://www.lama.univ-savoie.fr/~tavenas Sébastien Tavenas]
Responsable 2018: [http://www.lama.univ-savoie.fr/~tavenas Sébastien Tavenas]


<!-- * Xavier Provençal (CM/TD/TP) -->
<!-- * Xavier Provençal (CM/TD/TP) -->
Ligne 15 : Ligne 15 :


== TP ==
== TP ==

TBA
⚫
<!---
TP les 10 octobre et 6 novembre.
TP les 10 octobre et 6 novembre.


- Énoncé du TP, première partie : [https://mycore.core-cloud.net/index.php/s/CmLxKnYRdR3ots9 tp-part-1.pdf]. Plus de détails pour chacuns des trois sujets :
* [https://mycore.core-cloud.net/index.php/s/pGWYh5foa81qWMQ tp-part-1-CHO.pdf]
* [https://mycore.core-cloud.net/index.php/s/28cFgEefXqte4hO tp-part-1-CHNO.pdf]
* [https://mycore.core-cloud.net/index.php/s/qttUkOHtF6Fawel tp-part-1-3C.pdf]
Voici aussi un exemple d'entrée pour chaque sujet :
* [https://mycore.core-cloud.net/index.php/s/0vzGaxLoTG7ILMV Graphe-vrai-CHO.pdf]
* [https://mycore.core-cloud.net/index.php/s/QUHwEnb8nlkpFxh Graphe-vrai-CHNO.pdf]
* [https://mycore.core-cloud.net/index.php/s/ItC1deMoQ2dZ1So Graphe-vrai-3C.pdf]


⚫
<!--
- Énoncé du TP, première partie : [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO704/tp-part-1.pdf tp-part-1.pdf].
⚫
- Énoncé du TP, deuxième partie : [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO704/tp-part-2.pdf tp-part-2.pdf].
⚫
- Programmes pour générer des instances : [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO704/gen3SAT.py gen3SAT.py] [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO704/genCA.py genCA.py] [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO704/3SATtoCA.py 3SATtoCA.py].
⚫
-->


⚫
- Énoncé du TP, deuxième partie : [https://mycore.core-cloud.net/index.php/s/nFTlbPpgCu2ecan tp-part-2.pdf].
⚫
== Déroulement (2017-2018) ==
⚫
!-- - Programmes pour générer des instances : [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO704/gen3SAT.py gen3SAT.py] [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO704/genCA.py genCA.py] [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO704/3SATtoCA.py 3SATtoCA.py].
⚫
--
Documents pour les réductions :
* [https://mycore.core-cloud.net/index.php/s/2kSpPVRP1gIdNEO Avro Chapitre 10]
* [https://mycore.core-cloud.net/index.php/s/YqRGl3CpFvKZbaX Cormen-Leiserson-Rivest-Stein Coloration]
* [https://mycore.core-cloud.net/index.php/s/dnSgmAEoKnN4uPe Cormen-Leiserson-Rivest-Stein HNO] (Attention la figure 34.16 est incorrecte. La remplacer par la figure 34.16 de la [https://mycore.core-cloud.net/index.php/s/EUmxSqxp1GdNdnz Version anglaise])
* [https://mycore.core-cloud.net/index.php/s/jePhTQqlMMehW5M Hon HO] [https://mycore.core-cloud.net/index.php/s/eQ1hJsUxci863kx Version francaise]
* [https://mycore.core-cloud.net/index.php/s/MqkZ7PUiHLUz9ZY Garey-Johnson HNO]
* [https://mycore.core-cloud.net/index.php/s/s8mRmXna8vuMOk5 wiki proof]
Voici des exemples d'entrée pour 3SAT et Couverture par Sommets :
* [https://mycore.core-cloud.net/index.php/s/9LYEjRHq2Dc952o 3SAT-vrai]
* [https://mycore.core-cloud.net/index.php/s/Tj5K5BOFq4KQJLK CS-vrai]
* [https://mycore.core-cloud.net/index.php/s/3yqvTI5K6pZLgIf 3SAT-faux]
* [https://mycore.core-cloud.net/index.php/s/qnn6g6DjkwwAqBM CS-faux]


--->
⚫
Cours 1 et 2 (12 septembre) : Introduction

⚫
- Exemple "Tri lent" <!-- [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO704/tri.tgz Programme C/gtk pour illustrer différents algorithmes de tri].-->
⚫
== Déroulement (2018-2019) ==

⚫
Cours 1 (10 septembre) : Introduction
⚫
- Exemple de différents tris <!-- [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO704/tri.tgz Programme C/gtk pour illustrer différents algorithmes de tri].-->
- Notions d'instance et de problème
- Notions d'instance et de problème
- Notion de complexité asymptotique
- Encodage d'une instance
<!-- - Encodage d'une instance
- 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 : 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 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]. -->

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


Cours 3 (19 septembre) : Analyse de complexité pour des classes d'algorithmes
TD2 (18 septembre) : Analyse des algorithmes
- Complexité d'éléments basiques : instructions, tests, boucles Pour et TantQue
- Algorithmes gloutons
- Présentation des algorithmes Diviser-pour-régner.
- Cas des algorithmes récursifs.
<!-- - [https://mycore.core-cloud.net/index.php/s/j3d7p2BVmcF8um5 Analyse des algorithmes]
<!-- - Retour sur la feuille de rappels et exo "Analyse d'algorithmes, les bases".
!-- - 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].
Ligne 45 : Ligne 73 :
- [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) : Complexité des algorithmes Diviser-pour-régner (suite et fin) + Programmation dynamique.
Cours 2 (21 septembre) : Algorithmes récursifs (Diviser pour régner)

TD 3 (24 septembre) : Algorithmes récursifs (Diviser-pour-régner) + Premiers algorithmes de programmation dynamique
<!-- - Présentation des algorithmes Diviser-pour-régner.
- 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 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) : Probabilités.
Cours 3 (28 septembre) : Programmation dynamique.
<!-- - Problème de la distance minimum dans un nuage de points. [https://mycore.core-cloud.net/index.php/s/fh9C1oJ4HymuJI0 Distance]
⚫
- Complexité en cas moyen.
- Problème du rendu de monnaie. [https://mycore.core-cloud.net/index.php/s/taOj7Moq8gDy9vz Rendu monnaie]
⚫
!-- - 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"
Ligne 62 : Ligne 95 :
-->
-->


Cours 8 et 9 (17 octobre) : Complexité des problèmes
TD 4 (1 octobre) : Programmation dynamique

⚫
- Complexité d'un problème.
Cours 4 (5 octobre) : Complexité des problèmes
⚫
<!-- - Complexité d'un problème.
- Classe P.
- Classe P.
<!-- - Types de problèmes ( décision, optimisation, existence ). -->
!-- - 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) : NP-complétude
Cours 5 (9 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-Levin. [https://mycore.core-cloud.net/index.php/s/V9OUMtvnDuezpKl Cook-Levin]
- 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 5 (19 octobre) : NP-complétude
Cours 12 ( 6 novembre) : Analyse amortie?


== Historique ==
== Historique ==

Version du 18 septembre 2018 à 07:42

Responsable 2018: 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

 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

TD2 (18 septembre) : Analyse des algorithmes 

- Complexité d'éléments basiques : instructions, tests, boucles Pour et TantQue
- Cas des algorithmes récursifs.

Cours 2 (21 septembre) : Algorithmes récursifs (Diviser pour régner)

TD 3 (24 septembre) : Algorithmes récursifs (Diviser-pour-régner) + Premiers algorithmes de programmation dynamique 

- Problème de la multiplication de grands entiers.

Cours 3 (28 septembre) : Programmation dynamique.

TD 4 (1 octobre) : Programmation dynamique

Cours 4 (5 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.

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