Algorithmique

Code APOGÉE : MA4AY030 | 3 ECTS | Enseignants : Hervé Fournier et Bertrand Gentou
Volume horaire : 3h CM + 4h TD/TP pendant 4 semaines puis 1h TP pendant 8 semaines
Validation : CC + examen | Mutualisé avec : M1 mathématiques (MFA), M1 Mathématiques et Informatique, M1 MIC

Consolidation des connaissances en algorithmique, connaissance des rudiments de la complexité et des approches algorithmiques classiques.

Le cours est en partie mutualisé avec le master Math-Info :

• Les étudiants du M1 mathématiques suivent les deux parties du cours (sur 12 semaines)
• Les étudiants du M1 mathématiques-informatique suivent la seconde partie du cours (sur les 8 dernières semaines). Les étudiants de cette filière peuvent néanmoins suivre la première partie s’ils le désirent.

Programme

• Algorithmes (tris, …) et méthodes algorithmiques (diviser pour régner, recherche exhaustive, programmation dynamique, algorithmes gloutons) de base
• Structures de données classiques : liste, file, pile, arbre, graphes, table de hachage
• Graphes, algorithmes classiques de base : parcours, recherche de cycle, tri topologique, arbre de recouvrement, décomposition en composantes connexes, plus courts chemins
• Maîtrise d’un langage de programmation impératif

Bibliographie

• Arora, S. & Barak, B. (2009). Computational complexity: a modern approach. Cambridge : Cambridge University Press.
• Dasgupta, S., Papadimitriou, C. H. & Vazirani, U. V. (2008). Algorithms. New York : McGraw-Hill.
• Manber, U. (1989). Introduction to algorithms: a creative approach. Reading, MA : Addison-Wesley.