« 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 38 : Ligne 38 :




TP3 le 9 novembre
- Énoncé du TP, deuxième partie : [https://mycore.core-cloud.net/index.php/s/nFTlbPpgCu2ecan tp-part-2.pdf].
- [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/tp-part-2.pdf Énoncé du TP, deuxième partie].
!-- - 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://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/DocsReduction/Avro--Chapter10--ChallengingReductions.pdf Avro Chapitre 10]
⚫
Documents pour les réductions :
⚫
* [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/DocsReduction/Cormen_Coloration.pdf Cormen-Leiserson-Rivest-Stein Coloration]
* [https://mycore.core-cloud.net/index.php/s/2kSpPVRP1gIdNEO Avro Chapitre 10]
⚫
* [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/DocsReduction/Cormen_HNO.pdf Cormen-Leiserson-Rivest-Stein HNO](Attention la figure 34.16 est incorrecte. La remplacer par la figure 34.16 de la [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/DocsReduction/Cormen_HNO_english.pdf Version anglaise])
⚫
* [https://mycore.core-cloud.net/index.php/s/YqRGl3CpFvKZbaX Cormen-Leiserson-Rivest-Stein Coloration]
* [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/DocsReduction/Avro--Chapter10--ChallengingReductions.pdf Avro Chapitre 10]
⚫
* [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://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/DocsReduction/Avro--Chapter10--ChallengingReductions.pdf Avro Chapitre 10]
⚫
* [https://mycore.core-cloud.net/index.php/s/jePhTQqlMMehW5M Hon HO] [https://mycore.core-cloud.net/index.php/s/eQ1hJsUxci863kx Version francaise]
* [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/DocsReduction/Avro--Chapter10--ChallengingReductions.pdf Avro Chapitre 10]
* [https://mycore.core-cloud.net/index.php/s/MqkZ7PUiHLUz9ZY Garey-Johnson HNO]

* [https://mycore.core-cloud.net/index.php/s/s8mRmXna8vuMOk5 wiki proof]
⚫
* [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/DocsReduction/Cours_Hon_HO2.pdf Hon HO] [https://mycore.core-cloud.net/index.php/s/eQ1hJsUxci863kx Version francaise]
* [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/DocsReduction/garey-HNO.pdf Garey-Johnson HNO]
* [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/DocsReduction/wiki_proof.pdf wiki proof]
Voici des exemples d'entrée pour 3SAT et Couverture par Sommets :
Voici des exemples d'entrée pour 3SAT et Couverture par Sommets :
* [https://mycore.core-cloud.net/index.php/s/9LYEjRHq2Dc952o 3SAT-vrai]
* [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/Instances/3sat_vrai 3SAT-vrai]
* [https://mycore.core-cloud.net/index.php/s/Tj5K5BOFq4KQJLK CS-vrai]
* [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/Instances/CS_vrai CS-vrai]
* [https://mycore.core-cloud.net/index.php/s/3yqvTI5K6pZLgIf 3SAT-faux]
* [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/Instances/3sat_faux 3SAT-faux]
* [https://mycore.core-cloud.net/index.php/s/qnn6g6DjkwwAqBM CS-faux]
* [https://www.lama.univ-savoie.fr/pagesmembres/tavenas/info704/TP3/Instances/CS_faux CS-faux]


--->


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

Version du 9 novembre 2018 à 12:19

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

TP1 le 17 octobre 

Seuls les deux premiers problèmes suffisent pour avoir la note maximale!!!
- Énoncé du TP
- Fichiers relatifs au TP1

TP2 le 19 octobre 

- Fichiers relatifs au TP2

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

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