« 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 2019: Sébastien Tavenas
Responsable 2019: Sébastien Tavenas
Adresse couriel : sebastien.tavenas@univ-smb.fr
Adresse couriel : sebastien.tavenas@univ-smb.fr

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


== Quelques ressources bibliographiques ==
== Quelques ressources bibliographiques ==
Ligne 17 : Ligne 15 :
== TP ==
== TP ==


Dates provisoires :
- 22/25 septembre
- 9 octobre
- 16 octobre


<!--
TP1 le 25 septembre : Analyser la complexité d'algorithmes
TP1 le 25 septembre : Analyser la complexité d'algorithmes
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP_Analyse/tp1_enonce.pdf Sujet du TP 1]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP_Analyse/tp1_enonce.pdf Sujet du TP 1]
Ligne 70 : Ligne 75 :




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


Ligne 81 : Ligne 86 :
* [https://mycore.core-cloud.net/index.php/s/QUHwEnb8nlkpFxh Graphe-vrai-CHNO.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]
* [https://mycore.core-cloud.net/index.php/s/ItC1deMoQ2dZ1So Graphe-vrai-3C.pdf]
----->
-----
TP3 le 18 octobre : Réductions polynomiales
TP3 le 18 octobre : Réductions polynomiales
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/tp-part-2.pdf Énoncé du TP, deuxième partie].
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/tp-part-2.pdf Énoncé du TP, deuxième partie].
Ligne 97 : Ligne 102 :
* [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/Instances/CS_faux CS-faux]
* [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/Instances/CS_faux CS-faux]


⚫
-->


== Déroulement (2019-2020) ==
== Déroulement (2020) ==


Cours 1 (9 septembre) : Introduction
Cours 1 (7 septembre) : Introduction
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S1Cours/CM1.pdf Introduction]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S1Cours/CM1.pdf 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].-->
- 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].-->
Ligne 109 : Ligne 115 :
-->
-->


TD 1 (13 septembre) : Rappels de mathématiques
Cours 2 (10 septembre) :
<!--
⚫
Algorithmes récursifs (Diviser pour régner)
- Présentation des algorithmes Diviser-pour-régner.
⚫
- [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]
-->

⚫
TD 1 (17 septembre) :
<!--
Rappels de mathématiques
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/exos.pdf Sujet du TD]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/exos.pdf Sujet du TD]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/grandO.pdf Grand-O de la notation de Landau]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S2TD/grandO.pdf Grand-O de la notation de Landau]
- [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]
- [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]
-->

⚫
Cours 3 (18 septembre) :
<!--
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 du rendu de monnaie. [https://mycore.core-cloud.net/index.php/s/taOj7Moq8gDy9vz Rendu monnaie]
⚫
!-- - Complexité en cas moyen.
⚫
- 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].
⚫
- 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-python3.py Code à compléter (Python 3).]
-->


Cours 4 (29 septembre) :
⚫
<!-- Complexité des problèmes
⚫
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S8Cours/presentation1.0.pdf Introduction aux classes de complexité.]
!-- - Complexité d'un problème.
⚫
- Classe P.
⚫
!-- - Types de problèmes ( décision, optimisation, existence ). --
⚫
- Réduction polynomiale.
⚫
- Algorithme de vérification.
⚫
- Classe NP.
-->



TD2 (16 septembre) : Analyse des algorithmes
TD2 (2 octobre) :
<!--
Analyse des algorithmes
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S3TD/ExoAnalyse.pdf Sujet du TD]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S3TD/ExoAnalyse.pdf Sujet du TD]
- Complexité d'éléments basiques : instructions, tests, boucles Pour et TantQue
- Complexité d'éléments basiques : instructions, tests, boucles Pour et TantQue
Ligne 126 : Ligne 172 :
- [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]. -->
-->


⚫
TD 3 (5 octobre) :
⚫
Cours 2 (18 septembre) : Algorithmes récursifs (Diviser pour régner)
- Présentation des algorithmes Diviser-pour-régner.
<!-- 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.]
⚫
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S4Cours/distance_min.pdf distance minimale]

TD 3 (23 septembre) : Algorithmes récursifs (Diviser-pour-régner)
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S5TD/exo_div_pour_regner.pdf Exercice algorithmes récursifs]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S5TD/exo_div_pour_regner.pdf Exercice algorithmes récursifs]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S5TD/Solution-TD_operationsEntiers.pdf Correction des derniers exos de la feuille de TD.]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S5TD/Solution-TD_operationsEntiers.pdf Correction des derniers exos de la feuille de TD.]
<!--
!--
- 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. --
- 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 3 (30 septembre) : Programmation dynamique.
⚫
Cours 5 (13 octobre) :
⚫
<!-- - Problème de la distance minimum dans un nuage de points. [https://mycore.core-cloud.net/index.php/s/fh9C1oJ4HymuJI0 Distance]
<!-- Réductions de NP-complétude
⚫
- Problème du rendu de monnaie. [https://mycore.core-cloud.net/index.php/s/taOj7Moq8gDy9vz Rendu monnaie]
!-- - Complexité en cas moyen.
!-- - Problèmes NP-difficiles et NP-complets.
⚫
- Théorème de Cook-Levin. [https://mycore.core-cloud.net/index.php/s/V9OUMtvnDuezpKl Cook-Levin]
⚫
- Complexité d'un algorithme probabiliste.
⚫
- Preuve de NP-Complétude. !-- : Couverture des arêtes et k-coloriage. --
⚫
- 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].
⚫
- 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-python3.py Code à compléter (Python 3).]
-->
-->



⚫
TD 4 (30 septembre) : Programmation dynamique
TD 4 (14 octobre) :
<!-- Programmation dynamique
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S7TD/TD-prog_dynamique.pdf Énoncé de TD.]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S7TD/TD-prog_dynamique.pdf Énoncé de TD.]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S8Cours/Levenshtein.pdf Correction sur la distance de Levenshtein.]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S8Cours/Levenshtein.pdf Correction sur la distance de Levenshtein.]

⚫
Cours 4 (1 octobre) : Complexité des problèmes
⚫
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S8Cours/presentation1.0.pdf Introduction aux classes de complexité.]
⚫
<!-- - Complexité d'un problème.
⚫
- Classe P.
⚫
!-- - Types de problèmes ( décision, optimisation, existence ). --
⚫
- Réduction polynomiale.
⚫
- Algorithme de vérification.
⚫
- Classe NP.
-->
-->


⚫
Cours 5 (7 octobre) : Réductions de NP-complétude
<!-- - Problèmes NP-difficiles et NP-complets.
⚫
- 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. --
⚫
-->



⚫
TD 5 (15 octobre) : NP-complétude
TD 5 (23 octobre) :
<!-- NP-complétude
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S9Cours/EnonceTD.pdf Énoncé du TD]
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/S9Cours/EnonceTD.pdf Énoncé du TD]
-->


== Annales Examen ==
== Annales Examen ==

Version du 7 septembre 2020 à 10:04

Responsable 2019: Sébastien Tavenas

Adresse couriel : sebastien.tavenas@univ-smb.fr

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

Dates provisoires : 

- 22/25 septembre
- 9 octobre
- 16 octobre


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

Cours 2 (10 septembre) :

TD 1 (17 septembre) :

Cours 3 (18 septembre) :


Cours 4 (29 septembre) :


TD2 (2 octobre) : -->

TD 3 (5 octobre) :


Cours 5 (13 octobre) :


TD 4 (14 octobre) :


TD 5 (23 octobre) :

Annales Examen

Examen 2017

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=12562 »