!
Algorithmique avancée
INF550
: Algorithmique avancée
Gilles Schaeffer au LIX
Présentation du cours
Dans le catalogue...
Organisation indicative du cours
La page officielle du cours est maintenant sur le moodle. Cette page n'est plus mise à jour.
Chacun des 9 blocs du cours est constitué d'1h45 en amphi,
consacrées au cours, suivies de 2 heures 15 en petite classe, consacrées
à la mise en pratique sous forme d'exercices en petits groupes.
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).
- mercredi 10 septembre 2014: Cours 13h30-15h.
Flots, coupes et couplages, les transparents du cours : pour visionner, pour imprimer.
- mercredi 17 septembre 2014: Cours 13h30-15h;
Programmation linéaire, les transparents du cours : pour visionner, pour imprimer.
- mercredi 1 octobre 2014: Cours 13h30-15h;
NP-complétude et hypothèse de temps exponentiel, les transparents du cours : pour visionner, pour imprimer.
- mercredi 8 octobre 2014; Cours 13h30-15h;
Complexité paramétrique, les transparents du cours : pour visionner, pour imprimer.
- mercredi 15 octobre 2014; Cours 13h30-15h; Largueur arborescente, les transparents du cours : pour visionner, pour imprimer.
- mercredi 22 octobre 2014; Cours 13h30-15h; Algorithmique des solveurs SAT, les transparents du cours : pour visionner, pour imprimer.
- mercredi 5 novembre 2014; Cours 13h30-15h; Algorithmes approchés, les transparents du cours : pour visionner, pour imprimer.
- mercredi 19 novembre 2014; Cours 13h30-15h; Algorithmes online, les transparents du cours : pour visionner, pour imprimer.
- mercredi 26 novembre 2014; Cours 13h30-15h; Recherche locale, les transparents du cours : pour visionner, pour imprimer.
- mercredi 3 décembre 2014, Examen final: Controle écrit (3 heures).
Polycopié, transparents du cours, corrigés de PC et notes manuscrites autorisées.
L'énoncé peut etre disponible en anglais sur demande préalable. Il est permis de répondre en anglais.
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.