Algorithmique avancée

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

Discipline(s)

• Informatique

Bibliographie

• Cormen, Leiserson, Rivest et Stein, Introduction à l'algorithmique, Edition Dunod
• Alain Darte, Serge Vaudenay, Algorithmique et optimisation : Exercices corrigés, Edition Dunod