SDA

Structures de Données et Algorithmes

Description : Ce cours d’introduction présente des algorithmes et des structures de données fondamentaux, ainsi que des méthodes de résolution génériques pour résoudre efficacement des problèmes computationnels. Après une introduction générale sur les algorithmes et la notion de complexité, certaines structures de données sont présentées pour leur utilité, comme les tables de hachage, les arbres, en particulier les arbres de recherche, les graphes, les tas, etc. Des méthodes de résolution génériques sont ensuite introduites à travers différents exemples, comme le principe diviser pour régner, la programmation dynamique et la classe des algorithmes gloutons. Des algorithmes de références sur les graphes (Prim, Ford Fulkerson, Dijkstra, etc) sont présentés dans ce contexte. La suite du cours traite de la résolution des problèmes NP-difficiles avec des techniques de résolution exacte (backtracking, branch-and-bound) comme approchée (schémas d’approximation en temps polynomial). Le cours se termine sur la classe NPC et la conjecture P=NP. Les TD viennent compléter les différents chapitres du cours, en se concentrant sur des problèmes particuliers. Le TP porte sur un projet de conception d’un logiciel de navigation routière réparti sur 4 séances, s’appuyant sur l’ensemble des chapîtres du cours.

Acquis d’apprentissage : A l’issue de ce cours, les élèves sauront identifier les complexités temporelle et spatiale d’un algorithme et les situer dans une hiérarchie de classes de complexité pour en évaluer l’efficacité. Ils sauront mettre en oeuvre différentes techniques génériques (programmation dynamique, algorithme glouton, diviser pour régner, etc) pour concevoir un algorithme de résolution efficace du point de vue de la complexité. Enfin ils sauront reconnaître les difficultés intrinsèques aux problèmes NP-difficiles et le cas échéant, recourir à des algorithmes d’approximation plutôt que de vouloir une résolution exacte.

Modalités d’évaluation : Examen écrit de 3h, rattrapable.

Compétences évaluées :

• Développement
• Modélisation

Responsable de cours : Nicolas Jozefowiez

Identifiant Geode : SPM-INF-009