« INFO704 : Analyse d'algorithmes » : différence entre les versions
Aller à la navigation
Aller à la recherche
(Page créée avec « Responsable pour 2015--2016: [http://www.lama.univ-savoie.fr/~provencal Xavier Provençal] * Xavier Provençal (CM/TD/TP) == Quelques ressources bibliographiques == Ouv... ») |
Aucun résumé des modifications |
||
| Ligne 22 : | Ligne 22 : | ||
- Exemple "Tri lent" [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO724/triLent.sage triLent.sage] |
- Exemple "Tri lent" [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO724/triLent.sage triLent.sage] |
||
- Notions d'instance et de problème |
- Notions d'instance et de problème |
||
- Rappels sur les graphes (nombres de Ramsey) |
|||
- [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO724/Ramsey.sage Programme qui calcule les nombres de Ramsey] (les premiers du moins...) |
|||
- Encodage d'une instance |
- Encodage d'une instance |
||
- Feuille de rappel et exo [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/grandO.pdf Grand-O]. |
|||
- Feuille de rappel et exo [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/log_exp.pdf Logarithme et exponentielle]. |
|||
- Feuille de rappel et exo [http://lama.univ-savoie.fr/~provencal/enseignement/INFO704/analyse_algo_base.pdf Analyse d'algorithmes, les bases]. |
|||
Version du 13 septembre 2016 à 09:39
Responsable pour 2015--2016: Xavier Provençal
- Xavier Provençal (CM/TD/TP)
Quelques ressources bibliographiques
Ouvrage de référence :
- Cormen, Leiserson, Rivest et Stein, Algorithmique, 3e edition (2009). ( Aussi appelé "Introductino à 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).
- Paschos, Complexité et approximation polynomiale, (2004).
- Hopcroft et Ullman, Introduction to automata theory, languages, and computation, (1979).
TP
À venir.
Déroulement (2016-2017)
Cours 1 (13 septembre) : Introduction
- Exemple "Tri lent" triLent.sage - Notions d'instance et de problème - Encodage d'une instance - Feuille de rappel et exo Grand-O. - Feuille de rappel et exo Logarithme et exponentielle. - Feuille de rappel et exo Analyse d'algorithmes, les bases.
Historique
Ce cours est une refonte de INFO724 Algorithmique avancée, graphes et NP-complétude.