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

Version du 18 septembre 2018 à 07:43

Responsable 2018: Sébastien Tavenas

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

TBA

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.
- Analyse des algorithmes

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

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.

@@ Ligne 65 : / Ligne 65 : @@
  - Complexité d'éléments basiques : instructions, tests, boucles Pour et TantQue
  - Cas des algorithmes récursifs.
-<!-- - [https://mycore.core-cloud.net/index.php/s/j3d7p2BVmcF8um5 Analyse des algorithmes]
+ - [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)].
  - [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/fct_rec.pdf Théorèmes relatifs à la complexité temporelle des fonctions récursives].