Bourses d’excellence Ampère

Depuis 2004, le programme de bourses d’excellence Ampère de l’ENS de Lyon, en partenariat avec le Ministère de l’Enseignement Supérieur et de la Recherche, propose des bourses aux étudiants internationaux de master en sciences.

Ces bourses de 1000€ par mois, pour une ou deux années universitaires, permettent d’étudier à l’ENS de Lyon, dans un master de sciences.

Pour pouvoir candidater, les étudiants doivent :

  • être de nationalité étrangère

  • avoir débuté leur cursus universitaire hors de France

  • être actuellement en dernière année de licence ou équivalent (les étudiants qui ont déjà commencé leur master sont également éligibles)

  • déposer leur dossier avant la date limite

Tous les pays sont éligibles.

Des informations plus détaillées peuvent être trouvées sur www.ens-lyon.fr > rubrique Internationale.

Il existe également des bourses de Master proposées par le Labex MILYON.

ALGO1 – Algorithmique (1er semestre, 6 ECTS)

Cours : Yves Robert

TD : Marc De Visme & Laureline Pinault

Ce cours propose une introduction approfondie aux concepts et techniques pour concevoir des algorithmes efficaces.

Cette introduction fait suite à la formation de base dispensée dans l’option Informatique des classes préparatoires et dans les L1 et L2 d’informatique. Ce module suppose donc une familiarité élémentaire avec les concepts de base: notion d’algorithme, de complexité, de correction; structures de données de base (tableaux, listes, arbres, etc.); algorithmes classiques de recherche et de tri, etc. Il s’agit d’une formation résolument orientée vers les concepts fondamentaux et non pas vers l’applications de techniques toutes faites.

Le cours est indépendant du cours de Théorie de la Programmation et du Projet Programmation. Les travaux dirigés font l’objet d’exercices « papier & crayon », et il n’y a aucune implémentation sur machine. On peut donc le suivre en le considérant comme un cours de mathématiques discrètes … mais ce serait dommage ! Les paradigmes algorithmiques prennent tout leur sens quand on les met en oeuvre. Nous conseillons donc vivement de suivre en parallèle le Projet Programmation où seront implémentées les techniques vues en cours d’Algorithmique.

Plan

Quelques sujets abordés dans ce module:

  • Paradigmes: diviser-pour-régner, programmation dynamique, algorithmes gloutons;
  • Complexité: coûts en temps et en espace, complexité pire cas, complexité en moyenne, analyse amortie;
  • NP-complétude: les problèmes NP-complets, les réductions, les méthodes de résolution heuristiques;
  • Grands thèmes: algorithmes de recherche & de tri, calcul matriciel (eh oui, des surprises!), systèmes cryptographiques, géométrie algorithmique, reconnaissance de motifs, etc…

Le cours se prolonge au second semestre par le cours Algorithmique Avancée.

Organisation

Le cours est organisé selon le schéma hebdomadaire suivant:

  • 2h de cours;
  • 2h de travaux dirigés.

La note de contrôle continu est obtenue à partir de plusieurs devoirs à la maison et d’un partiel organisé en milieu de semestre. Un examen final est organisé en fin de semestre.

Bibliographie

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, The MIT Press, 1990. Version française: Introduction à l’Algorithmique, 2e édition, Dunod, 2004.
  2. G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation: Combinatorial optimization problems and their approximability properties, Springer Verlag, ISBN 3-540-65431-3.
  3. Voir aussi la liste des problèmes d’optimisation NP tenue à jour par Pierluigi Crescenzi et Viggo Kann
  4. Herbert S. Wilf,Algorithms and Complexity , A K Peters Ltd, ISBN: 9781568811789. La première édition est accessible en ligne.
  5. La page wikipedia est claire et concise : http://fr.wikipedia.org/wiki/Théorème_de_Cook
  6. Jon Kleinberg & Éva Tardos, Algorithm Design, Addison-Wesley, ISBN-10: 0321295358
  7. M. R. Garey & D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN-10: 0716710455
  8. D. Knuth, The Art of Computer Programming, Volumes 1-3, Addison-Wesley, ISBN-10: 0201485419
  9. Polycopié du cours des années précédentes (largement repris dans le plan du cours de cette année).

ASR2 – Système & Réseaux (2ème semestre, 6 ECTS)

Cours : Michaël Rao

TD : Guilhem Gamard & Rémy Grunblatt & Etienne Moutot

Objectif

L’objectif de ce cours est d’apprendre à programmer des applications interagissant avec le système, et implicitement de comprendre le fonctionnement du système d’exploitation.

Nous aborderons les points suivants : la gestion des entrée/sorties, des fichiers, des processus, de la mémoire, des communications réseau. Il y aura également une sensibilisation aux problèmes de sécurité. Le système choisi est Linux et le langage le C/C++. Mais comme le cours suivra au plus près la norme POSIX, les connaissances acquises seront aisément transportables aux autres systèmes.

Bibliographie

  •  Jean-Marie Rifflet et Jean-Baptiste Yunès, « UNIX : programmation et communication », Dunod, 2003.
  •  Andrew S. Tanenbaum et Herbert Bos, « Modern Operating Systems, 4th Ed »,Pearson 2015..

Cours pour non spécialistes

Bonjour à tous,

Dans le cadre de sa démarche d’interdisciplinarité, l’ENS de Lyon propose aux étudiants, enseignants et chercheurs une palette de cours pour non spécialistes d’un semestre, pour acquérir des compétences dans une discipline qui leur est étrangère et les outils indispensables à l’interdisciplinarité.

Plus que des conférences de sensibilisation, ces cours de base, qui peuvent être validés dans le cadre du Diplôme de l’ENS, permettent de comprendre les concepts et d’intégrer le langage et la culture d’une autre discipline.

Vous trouverez tous les détails pour les inscriptions et les programmes sur : http://www.ens-lyon.fr/cours-pour-non-specialistes/

Au programme de ce premier semestre par exemple , des cours sur le cancer et les maladies virales, la modélisation mathématique, les principes économiques fondamentaux ou encore l’utilisation des cartes géographiques… Inventez-vous votre propre parcours !

Ces cours ont lieu le lundi de 16h30 à 18h30.

Catherine Hänni
Chargée de mission pour l’interdisciplinarité à l’ENS de Lyon

Séminaires SIESTE 2012/2013

Voici les résumés des séminaires SIESTE 2012/2013:

9 octobre 2012. Damien Stehlé. Manipuler les réseaux euclidiens. slides

Résumé: Un réseau est l’ensemble des combinaisons linéaires entières de vecteurs linéairement indépendants. Visuellement, le réseau forme une grille infinie de points régulièrement espacés. Les réseaux ont de
nombreuses applications en informatique. Entre autres, ils
apparaissent fréquemment en calcul formel, par exemple pour factoriser
les polynômes à coefficients rationnels, et en cryptographie, aussi
bien pour cryptanalyser que pour concevoir des protocoles.

L’algorithme LLL, du nom de ses auteurs Arjen Lenstra, Hendriz Lenstra
et László Lovász, permet de calculer une bonne représentation, ou
base, d’un réseau donné. Cette représentation fournit de
l’information intrinsèque sur le réseau manipulé. De nombreuses
applications ont suivi la publication de l’algorithme LLL, et, du fait
de ce succès, plusieurs accélérations algorithmiques ont par la suite
été proposées. L’approche la plus efficace aujourd’hui repose, en
interne, sur des calculs flottants en faible précision, donnant lieu à
un algorithme hybride numérique-algébrique.

Dans cet exosé, après une introduction du domaine, je décrirai
l’algorithme LLL et le principe de l’accélération numérique-algébrique.

16 octobre 2012.Louis Esperet. Utiliser la compression d’entropie pour rendre constructives des preuves existentielles.

Résumé: Le Lemme Local de Lovász (l’autre LLL ndlr) est un outil puissant qui permet de montrer
de manière très simple l’existence d’objets combinatoires avec
certaines propriétés. Il affirme que si un certain nombre
d’événements ont tous une petite probabilité et que ceux-ci ne sont
pas trop interdépendants, la probabilité qu’aucun événement n’arrive
est non nulle.
Le problème était (jusqu’à une date récente) que cet outil n’était pas
constructif. J’expliquerai les idées (très jolies et étonnamment
simples) basées sur la compression d’entropie qui ont permis à Robin Moser
d’obtenir une version algorithmique de ce lemme. Je donnerai deux
exemples :

1) Si on a une suite de listes L_1, L_2, L_3, … à quatre éléments on
peut trouver (efficacement) dans chaque liste L_i un élément a_i tel
que le mot a_1 a_2 a_3 … n’a pas de carré (i.e. de sous-mot de la
forme x1 x2 … x_k x_1 x_2 … x_k).

2) Toute instance de k-SAT dans laquelle chaque clause a des variables
en commun avec au plus 2^(k-2) autres clauses est satisfiable (et on
peut trouver une bonne assignation vrai/faux aux variables de manière
efficace).

27 novembre 2012.Manuel Bodirsky. A Short Introduction to Constraint Satisfaction Problems.

Résumé: Many computational problems originating in various areas in theoretical computer science
can be formulated as constraint satisfaction problems (CSPs). In such problems,
we are given a finite set of variables and a finite set of constraints on those variables,
and the task is to find an assignment to the variables that satisfies all constraints.
Depending on the choice of the possible constraints, such problems might
be computationally hard, or feasible.
In recent years, a fascinating theory starts to emerge that provides strong
criteria implying hardness, or the existence of polynomial-time algorithms for such problems.
Questions that are motivated by this line of research are of central interest in finite model theory,
structural combinatorics, and universal algebra. I will give a short introduction to current
research on CSPs that directly leads to some of the outstanding open questions of the field.

4 décembre 2012.Jade Alglave. Reasoning about Weak Memory.

Résumé: Multiprocessors are now prominent, but provide execution models that are quite
subtle. To write correct concurrent programs, we need formal models describing
the behaviours that a multiprocessor allows or not. In this talk, I will
present a class of relaxed memory models, defined in the Coq proof assistant,
parameterised by the chosen permitted local reorderings of reads and writes,
and the visibility of inter- and intra-processor communications through memory
(e.g. store atomicity relaxation). We prove results on the required behaviour
and placement of memory fences to restore a given model (such as Sequential
Consistency) from a weaker one. Based on this class of models we develop a
tool, diy, that systematically and automatically generates and runs litmus
tests to determine properties of processor implementations. We detail the
results of our experiments on Power and the model we base on them. This work
identified a rare implementation error in Power 5 memory barriers.

Réforme de l’agrégation

La réforme en cours du concours de l’agrégation pose de nombreuses questions et amène les ENS à reconsidérer les cursus de leurs élèves, notamment dans les filières de lettres et sciences humaines. A ce jour, et même si la situation doit encore évoluer, nous disposons déjà d’un certain nombre de réponses :

  • Reports de stage : Les reports de stage après la réussite à l’agrégation restent automatiques pour les élèves en scolarité dans une ENS, ainsi que pour les bénéficiaires d’un Contrat Doctoral.
  • Validation de l’agrégation dans le supérieur : cette validation restera possible à condition d’effectuer 128 heures d’enseignement réparties sur deux ans. Il est donc essentiel que les agrégés qui obtiennent un Contrat Doctoral puissent bénéficier d’une mission d’enseignement leur permettant de valider leur concours.
  • Session 2010 : année transitoire, c’est la dernière année où il est possible de s’inscrire à l’agrégation en étant titulaire d’un M1. A partir de la session 2011, un M2 validé sera requis pour s’inscrire au concours de l’agrégation.
  • Session 2011 : on risque de connaître une baisse des effectifs puisqu’il faudra désormais détenir un M2 pour s’inscrire à l’agrégation. L’ENS de Lyon affirme néanmoins sa volonté de maintenir l’ouverture de ses préparations à l’agrégation, tout en maintenant un degré de sélection suffisant pour en assurer le niveau.

Pour toute question sur l’option informatique, contactez le responsable de l’option.