Algorithmique avancée - 4MM1AA

Objectif(s)

Approfondir les notions introduites en première année en algorithmique.
Aborder la programmation efficace en nombre d'opérations et en mémoire (défauts de cache).
Appliquer à la résolution de problèmes difficiles en particulier par les techniques d'énumération implicites.
Introduction aux algorithmes d'approximation, aux algorithmes probabilistes et aux preuves interactives.

Responsable(s)

Jean-Louis ROCH

Contenu(s)

1. révisions et approfondissements autour des algorithmes diviser pour régner et de l'analyse de cout (pire des cas et analyse en moyenne).
2. Algorithmique pour les caches
3. Programmation dynamique
4. Branch&Bound (séparation-évaluation)
5. Complexité (hiérarchie polynomiale: P, NP, PSPACE)
6. Algorithmes d'approximation
7. Algorithmes probabilistes (hachage parfait). Preuves interactives (IP=PSPACE)

• • Ce cours est donné en Période(s) Académique(s) 4 **

Cours de L3 en algorithmique: structures de base (tableaux non bornés, piles, arbres, files de priorité, hachage) et algorithmes (parcours de graphes, diviser pour régner, recherche et tri)
Bonne expérience de la programmation (en python par exemple) et connaissance de C; écriture de programmes itératifs et récursifs.
Connaissances de base en recherche opérationnelle (programmation linéaire) et en probabilités (Bernoulli law, inégalité de Markov).

Contrôle des connaissances

Evaluation : Examen écrit (3h)

Rattrapage : Examen oral (exposé, soutenance, etc..) (30 min à 1h)

Session 1
Examen écrit de 3h, Documents manuscrits autorisés
TPs (TPs en salle machine, à compléter à la maison et à rendre sur teide).
Session 2
Examen Oral, préparé à partir d'un sujet.
30mn à 1h de préparation.

Calendrier

Le cours est programmé dans ces filières :

• Cursus ingénieur - Alternance - Alternance période 4 (2A)

Informations complémentaires

Code de l'enseignement : 4MM1AA
Langue(s) d'enseignement :

Le cours est rattaché aux structures d'enseignement suivantes :

• Equipe Programmation-logiciel
• Equipe Algorithmique-Mathématiques discrètes

Vous pouvez retrouver ce cours dans la liste de tous les cours.

Bibliographie

Cormen, Leiserson, Stein, Rivest, Introduction à l'algorithmique, Dunod, 2004