Algorithmique avancée

Algorithmique avancée
Master InformatiqueParcours Science et ingénierie du logiciel (SIL)

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