« INFO704 : Analyse d'algorithmes » : différence entre les versions
Aucun résumé des modifications |
Aucun résumé des modifications |
||
| Ligne 18 : | Ligne 18 : | ||
TP1 le 25 septembre : Analyser la complexité d'algorithmes |
TP1 le 25 septembre : Analyser la complexité d'algorithmes |
||
[https://www.dropbox.com/l/scl/AAAtj6rrfWhzr8X-YdsiHSPi3LGJJxM1BnE Sujet du TP 1] |
|||
Fichiers pour le TP : |
|||
[https://www.dropbox.com/l/scl/AACME272lzeyEQ9LEuKnu-ZBoWA8GseGpuI Fichiers pour GraphChrono] |
|||
[https://www.dropbox.com/l/scl/AACSu8BYicEpbGAzpwD6d-cHwb72VvO7pO4 Fichiers pour Problème 2] |
|||
[https://www.dropbox.com/l/scl/AACTY6YG6l4NFzuE2tqf_JpcNL2agqzNFws Fichiers pour Problème 3] |
|||
<!-- |
<!-- |
||
'''Seuls les deux premiers problèmes suffisent pour avoir la note maximale!!!''' |
'''Seuls les deux premiers problèmes suffisent pour avoir la note maximale!!!''' |
||
| Ligne 88 : | Ligne 94 : | ||
- Présentation des algorithmes 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/fct_rec.pdf Théorème général.] |
||
- [https://www.dropbox.com/l/scl/AAD1Upa8Gmg4hPC83wBGxE2bsETd_I22wLw Problème distance minimale] |
|||
TD 3 (23 septembre) : Algorithmes récursifs (Diviser-pour-régner) |
TD 3 (23 septembre) : Algorithmes récursifs (Diviser-pour-régner) |
||
Version du 25 septembre 2019 à 05:57
Responsable 2019: Sébastien Tavenas
Adresse couriel : sebastien.tavenas@univ-smb.fr
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
TP1 le 25 septembre : Analyser la complexité d'algorithmes Sujet du TP 1 Fichiers pour le TP : Fichiers pour GraphChrono Fichiers pour Problème 2 Fichiers pour Problème 3
TP2 le 9 octobre : Problème NP-complet
TP3 le 18 octobre : Réductions polynomiales
Déroulement (2019-2020)
Cours 1 (9 septembre) : Introduction
- Introduction - Exemple de différents tris - Notions d'instance et de problème - Notion de complexité asymptotique
TD 1 (13 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 1 et 2 du TD
TD2 (16 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 (18 septembre) : Algorithmes récursifs (Diviser pour régner)
- Présentation des algorithmes Diviser-pour-régner. - Théorème général. - Problème distance minimale
TD 3 (23 septembre) : Algorithmes récursifs (Diviser-pour-régner)
- Exercice algorithmes récursifs
Cours 3 (30 septembre) : Programmation dynamique.
TD 4 (30 septembre) : Programmation dynamique
Cours 4 (1 octobre) : Complexité des problèmes
Cours 5 (7 octobre) : Réductions de NP-complétude
TD 5 (15 octobre) : NP-complétude
Annales Examen
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.