II.3513 - ALGORITHMIQUE AVANCEE (5 CREDITS)

Pré-requis : II.1102
Niveau : Avancé
Responsable du module : Matthieu Manceny
Déroulement : cours/conférences -18 h ; cours/TD - 24 h ; Projet
Nbre d’heures : 42 h
Evaluation : examen et projet

Contexte

De nombreux problèmes, pour la plupart d’une grande importance pratique (routage dans un réseau, ordonnancement optimal de tâche, chemin le plus court), font appel à des notions avancées en modélisation et en algorithmique. En effet, la résolution de tels problèmes demande à la fois d’analyser les données à manipuler pour en choisir la meilleure représentation, et également de concevoir les algorithmes les plus adaptés. Il faut alors être capable d’estimer les complexités de ces algorithmes pour pourvoir les comparer, voire les optimiser.

Objectifs

Compétences

Le module Algorithmique avancée  vise à préparer l’élève-ingénieur à acquérir des compétences dans un large spectre de domaines où l’algorithmique et la modélisation jouent un rôle prépondérant. Le module s'intéresse plus particulièrement à introduire les grands thèmes des domaines considérés (notamment théorie des graphes et optimisation) ainsi qu’à l'acquisition des techniques, méthodes pratiques et algorithmes fondamentaux de ces domaines.
L’ensemble de cet enseignement permet d’élaborer les concepts et  savoir-faire  suivants.

Concepts

• Classes de complexité
• Heuristique et algorithmes d’approximation de solutions
• Programmation linéaire et recherche d’optimums
• Théorie des graphes (problèmes de flux, logistiques, plus court chemin, …)
• Algorithmes génétiques, Algorithmes probabilistes
• Fouille de données et classification
• Réseaux de neurones

Savoir-faire

• Estimer et comparer les complexités d’algorithmes
• Appliquer des algorithmes classiques de recherche opérationnelle (Simplex, problème du sac à dos)
• Modéliser un problème sous forme de graphe, et choisir les bons algorithmes  pour le résoudre (ex. : algorithmes de Prim ou Kruskal pour l’arbre couvrant, Dijkstra pour le plus court chemin, Ford-Fulkerson pour les problèmes de flots, …)
• Analyser des données et déterminer les critères pour les classifier
• Concevoir un réseau de neurones ou un algorithme génétique, et analyser l’influence des paramètres sur leurs comportements. 

Approche pédagogique

Le module se découpe en deux parties. Les six premières séances sont consacrées à des conférences sur des domaines précis et pointus (algorithmes génétiques et probabilistes, réseaux de neurones, fouille de données) et donnent lieu à plusieurs sujets de projets. Les huit séances de la seconde partie se déroulent suivant un schéma cours/TD et introduisent des concepts fondamentaux en algorithmique (complexité, optimisation) et en théorie des graphes ; les concepts et savoir-faire acquis sont évalués par un examen.

Bibliographie

• Support de cours
• Ouvrages
• Liens internet