INF550 : Algorithmique avancée

Gilles Schaeffer au LIX

Présentation du cours

Dans le catalogue...

Organisation du cours pour l'année 2014/2015


Chacun des 9 blocs du cours est constitué d'1h30 en amphi, consacrées au cours, suivies de 2 heures en petite classe, consacrées à la mise en pratique sous forme d'exercices en petits groupes.

Les cours et petites classes sont assurés par Gilles Schaeffer, assisté de Thibault Manneville.


Les transparents du cours seront mis en ligne sur cette page au fur et à mesure des séances (autant que possible quelques jours à l'avance).

Les notions et algorithmes suivants sont supposées acquises: les manipulations d'arbres et de graphes (parcours en profondeur, en largeur, structures de données), les algorithmes gloutons (Kruskal, Prims), l'approche diviser pour régner (par exemple le tri fusion), la programmation dynamique. Ces notions figurent notamment au programme du cours INF431. On pourra aussi consulter les chapitres correspondants des livres cités ci-dessous.

Planning 2014 (en cas de doute, ce sont les infos de la scola qui font foi).

Les petites classes se déroulent de 15h15 a 17h15, dans l'amphi Curie. Les énoncés et corrigés de petites classes seront ajoutés au fur et à mesure sur cette page:

Supports de cours

Le polycopié des années précédentes au format pdf. Les chapitres 1 et 2 ne sont plus traités, leur contenu est supposé acquis. Au contraire le chapitre 7 n'est plus au programme (voir INF554: utilisation du hasard en algorithmique). Les chapitres 8 et 9 fournissent des illustrations des notions vues dans les autres chapitres, mais ne sont plus explicitement traitées en cours.

A défaut du nouveau poly, je vous suggère d'utiliser comme support des cours 6 et 7 le chapitre 2 du polycopié du professeur Cyril Gavoille. Il s'agit d'un enseignement de M2, dont les quelques développements plus approfondis sortent du programme de notre cours, mais vous y retrouverez facilement les notions que j'utilise. Ce texte sera autorisé à l'examen.

If french is not so easy for you, I suggest the following two textbooks: Algorithms by Dagupta, Papadimitriou and Vazirani, and Algorithm Design by Kleinberg and Tardos.

Annales

Les sujets de 2006, 2007, 2008, 2008/2009, 2009, 2010, 2011 , 2012, 2013, et leur correction 2006, 2007, 2008, 2008/2009, 2009, 2010, 2011, 2012, 2013.