Théorie des graphes - Cours de Recherche

Master d'Informatique Fondamentale - ENS Lyon

Présentation

Il s'agit d'un cours avancé de théorie des graphes. Il est accessible à tout étudiant ayant des connaissances de bases sur les graphes et en algorithmique. Pour se faire une idée, une bonne recommandation est la lecture des chapitres sur les graphes du livre “Introduction à l'algorithmique” de Cormen, Leiserson et Rivest. Les notions qui y sont introduites feront juste l'objet de rappels très courts.

Le but du cours est de présenter plusieurs problématiques de théorie des graphes représentatives des questions et des outils qui ont fait l'objet de recherches récentes (étude de classes particulières de graphes, théorèmes et algorithmes de décomposition, théorème des 4 couleurs, théorème des graphes parfaits, théorème des mineurs ...). On s'intéressera aux aspects mathématiques et algorithmiques qui leur sont associées.

Evaluation

Après les premières séances de cours, une liste de sujets de synthèse sera proposée. Votre contribution consistera à rédiger un court mémoire sur l'un de ces sujets, puis à le présenter à l'oral.

D'autre part, un examen aura lieu la dernière semaine. Il portera sur l'ensemble du cours et pourra aussi faire intervenir des notions présentées pendant les différents exposés. La répartition de la note finale du cours sera grosso modo 2/3 sujet de synthèse + 1/3 examen.

Sujets de synthèse

Vous devez chacun choisir un sujet différent dans la liste proposée (ICI !), ainsi qu'une date pour l'exposer (environ 25 min + questions), et écrire un court mémoire sur ce sujet. Vous devez également relire le mémoire de deux autres étudiants et écrire une fiche de lecture. Une fois votre choix fait, inscrivez-vous sur le planning 2006/2007 pour fixer le sujet, la date et les sujets dont vous souhaitez être relecteurs !

Les sujets de synthèse proposés peuvent faire appel à différents documents (articles, livres, exercices) ainsi que vos propres preuves ou algos ! Vous avez une certaine liberté pour aborder chaque sujet du moment que vous répondez à la question centrale. Des pistes sont proposées, vous n'êtes pas obligés de les suivre toutes. La liste des documents suggérés n'est bien sûr pas exhaustive. Le mémoire doit faire entre environ 10 et 15 pages (figures non comprises). Une exigence est qu'il doit présenter au moins un théorème avec sa preuve et/ou un algorithme avec son analyse.

N'hésitez surtout pas à me contacter si vous avez des questions sur le contenu d'un sujet ou sur les documents qui vous sont nécessaires. En particulier, si vous n'arrivez pas à récupérer des articles ou si des livres ne sont plus disponibles à la bibliothèque, dites-le moi.

Le cours précédent celui de l'exposé (généralement la semaine précédente), l'étudiant donne trois exemplaires de son rapport : à moi et aux deux relecteurs. Chaque relecteur fait une fiche critique de relecture (1 ou 2 pages) et me la donne avant l'exposé. On pourra s'inspirer du guide du 'referee' de Ian Parberry (intéressant pour voir comment la communauté des chercheurs fonctionne) :
http://www.eng.unt.edu/ian/guides/postscript/referee.ps
Les relecteurs posent également des questions à celui qui expose. L'exposé dure environ 25mn et est suivi d'une séance de questions. Ne dépassez en aucun cas 40mn tout compris, répétez avant pour connaître la durée de votre exposé --> Créneau réduit à 30 mn au total, soit environ 20 mn d'exposé + 10 mn de questions.

Bibliographie
Me contacter

THIERRY Eric, bureau A4 à l'ISC (Institut des Systèmes Complexes, comment venir ?)
Email: eric.thierry@ens-lyon.fr