Algorithmique avancée
Master InformatiqueParcours Science et ingénierie du logiciel (SIL)
ComposanteUFR de mathématique et d'informatique
Description
Étude des principales stratégies algorithmiques : diviser pour régner, méthodes gloutonnes, programmation dynamique, branch and bound.
Trois aspects sont abordés : la formalisation des problèmes, la conception des algorithmes, et l’analyse de leur complexité.
Compétences requises
À l'entrée de cet enseignement, un étudiant devrait savoir :
- Écrire des algorithmes itératifs et récursifs
- Calculer la complexité asymptotique d’un algorithme
- Connaître les algorithmes classiques de tris et les algorithmes sur les graphes.
- Manipuler des structures de données (tableaux, piles, files, listes, arbres)
Compétences visées
À l'issue de cet enseignement un étudiant saura :
- Formaliser des problèmes avant de les résoudre
- Résoudre des problèmes avec ces stratégies
- Étudier la complexité asymptotique des algorithmes
Disciplines
- Informatique
Bibliographie
- Cormen, Leiserson, Rivest et Stein, Introduction à l'algorithmique, Edition Dunod
- Alain Darte, Serge Vaudenay, Algorithmique et optimisation : Exercices corrigés, Edition Dunod