1. Les études d'informatique à l'ENS et le diplôme de l'École normale supérieure

1.1. Présentation du diplôme de l'École normale supérieure

Suite à la mise en place du système universitaire européen LMD (Licence, Master, Doctorat), l'École normale supérieure a créé en 2005 un diplôme d'établissement intitulé diplôme de l'École normale supérieure, qui complète le cursus universitaire. Sa finalité est d'offrir une variété de parcours conjuguant une formation d'excellence dans une discipline principale avec une ouverture à la fois souple et ambitieuse dans d'autres disciplines.

Le diplôme est ouvert à des étudiants issus des classes préparatoires aux grandes écoles et des universités françaises ou étrangères désireux de recevoir la même formation que les élèves normaliens (fonctionnaires stagiaires ou boursiers de la section internationale). Les étudiants font l'objet d'une procédure de sélection spécifique (cf. Conditions d'admission).

Le diplôme de l'ENS est délivré au terme d'une scolarité d'une durée de trois ans (en règle générale1) pendant laquelle chaque étudiant fait valider :

• un cursus universitaire de haut niveau sanctionné par l'obtention d'un master dans une discipline qui constitue la spécialité principale du diplôme. En règle générale1, ce cursus comprend une troisième année de licence (L3) et les deux années du master (M1 et M2), chacune des trois années correspondant à la validation d'un total de 60 unités ECTS (European Credit Transfer System) ;

• des formations supplémentaires validées par 36 unités ECTS au minimum sur l'ensemble des trois années. Celles-ci peuvent (i) relever de la spécialité principale (enseignements suivis dans la discipline du master), (ii) constituer la spécialité secondaire du diplôme (enseignements coordonnés dans une autre discipline) ou (iii) exploiter toute la diversité de l'offre pédagogique proposée par l'ENS aux étudiants.

1.2. L'informatique dans le diplôme de l'École normale supérieure

Dans le cadre du diplôme de l'ENS, les études d'informatique prennent deux formes distinctes selon que cette discipline constitue ou non la spécialité principale de l'étudiant :

• Élèves et étudiants informaticiens : le Département d'informatique est la structure pédagogique et scientifique à laquelle sont rattachés tous ceux qui envisagent l'informatique comme discipline principale. Les étudiants inscrits auprès du Département d'informatique suivent la filière informatique du diplôme de l'ENS, qui constitue une formation spécifique de haut niveau comprenant notamment une troisième année de licence (L3) et les deux années d'un master (M1 et M2).

• Élèves et étudiants relevant d'un autre département scientifique : le Département d'informatique propose également une offre de formation aux étudiants inscrits dans d'autres disciplines auprès des différents départements de l'ENS. Il peut s'agir, soit d'un ensemble cohérent d'enseignements en informatique ayant vocation à constituer la spécialité secondaire de l'étudiant, soit de formations ponctuelles que l'étudiant fait valider pour son diplôme en accord avec son tuteur et les responsables de ces enseignements.

Des passerelles existent entre les différents départements de l'ENS. Sous réserve de l'accord des directions des études concernées, une réorientation peut être envisagée en cours de scolarité pour les élèves de la filière informatique, soit vers d'autres disciplines au sein du diplôme de l'ENS, soit vers d'autres formations universitaires en dehors de ce cadre.

2. Responsables de la formation

Directeur des études :

Patrick Cousot

Directeur des enseignements :

Jean Vuillemin

    Secrétariat :

Isabelle Delais

École normale supérieure

Département d'informatique

45, rue d'Ulm - 75230 Paris cedex 05

Tél : +33 (0) 1 44 32 20 45

Fax : +33 (0) 1 44 32 20 75

Mél : diplome@(trap)di.ens.fr ou isabelle.delais@(trap)ens.fr

Bureau : B10 aile Rataud

Page d'accueil : http://diplome.di.ens.fr

3. Objectifs et débouchés

3.1. Objectifs de la filière informatique du diplôme de l'ENS

Les étudiants inscrits dans la filière informatique du diplôme sont rattachés statutairement au Département d'informatique de l'ENS. Celui-ci leur propose, au titre de leur spécialité principale, un parcours de type universitaire aux effectifs réduits (une vingtaine d'étudiants par promotion, en incluant les élèves normaliens et les boursiers de la section internationale) dans lequel est dispensée une formation originale d'informaticiens possédant une bonne connaissance générale des mathématiques pures et appliquées dans des secteurs variés. Un encadrement renforcé permet un rythme plus rapide et une réflexion plus approfondie que dans d'autres formations. Les enseignements sont complétés par des stages de recherche obligatoires.

Objectifs des études en informatique à l'ENS :

• l'intégration, dans un cursus d'excellence en informatique, des élèves normaliens, des boursiers de la section internationale et des étudiants retenus par le Département d'informatique pour suivre leurs études dans le cadre du diplôme de l'ENS (cf. Conditions d'admission) ;

• une formation à et par la recherche, visant à assurer une professionnalisation exigeante, qui se traduit par un enseignement d'un très haut niveau scientifique. Les stages à l'étranger, ciblés et obligatoires, permettent en outre une ouverture internationale dans les domaines choisis ;

• une orientation de chaque élève ou étudiant, respectueuse de la diversité des profils et des choix personnels, rendue possible par une structure aussi flexible que possible. À cette fin, chaque étudiant de la filière informatique est suivi par un tuteur, à titre individuel, tout au long de son parcours ; il est invité à suivre également quelques enseignements d'ouverture à d'autres disciplines qui personnalisent ce parcours de formation.

3.2. Débouchés de la filière informatique du diplôme de l'ENS

Tout étudiant titulaire du diplôme de l'ENS aura acquis un master recherche. Un étudiant qui a suivi la filière informatique du diplôme peut donc commencer une thèse de doctorat en mathématiques ou en informatique, qu'il achèvera en principe au terme de deux ou trois années de travail de recherche à l'issue de la scolarité. Il peut également commencer immédiatement une carrière non académique.

À moyen terme, une fois la thèse de doctorat éventuelle achevée, les débouchés possibles après 1, 2 ou 3 ans sont les suivants :

• chercheur en informatique dans un grand organisme de recherche publique (CNRS, CEA, INRIA, ONERA, CNES, etc.) ;

• enseignant-chercheur à l'université en France ou à l'étranger ;

• chercheur en informatique dans l'industrie (France Telecom, EADS, etc.) ;

• ingénieur informaticien dans l'industrie en France ou à l'étranger ;

• enseignant dans les classes préparatoires aux grandes écoles, plus généralement, dans l'enseignement post-baccalauréat (IUT, CNAM, etc.).

4. Conditions et procédure d'admission

4.1. Les élèves de l'ENS et boursiers de la section internationale

Ayant acquis 120 unités ECTS (niveau L2) en classes préparatoires aux grandes écoles et réussi le concours d'entrée à l'ENS, les élèves normaliens désireux de suivre un cursus en informatique commencent leurs études en informatique à l'ENS en s'inscrivant en première année de scolarité (L3).

Les boursiers de la section internationale accèdent également aux études en informatique à l'ENS, soit au niveau L3, soit directement au niveau M1 selon les études effectuées au préalable dans leur université d'origine.

4.2. Les étudiants du diplôme de l'ENS

Tout étudiant issu, soit d'une classe préparatoire aux grandes écoles, soit d'une université française ou d'un établissement universitaire étranger, justifiant directement ou par équivalence de 120 unités ECTS (niveau L2) ou 180 unités ECTS (niveau L3) est autorisé à se porter candidat au diplôme de l'ENS pour y effectuer des études en informatique.

Pour la filière informatique comme dans les autres disciplines représentées au sein du diplôme de l'ENS, la règle générale est de recruter les étudiants au niveau de la troisième année de licence (L3). L'intégration peut toutefois s'effectuer au niveau du master (M1), notamment pour les étudiants issus des universités étrangères.

4.3. Dossier de candidature à la filière informatique du diplôme de l'ENS

Le dossier et les modalités de candidature sont accessibles à l'URL suivante :

http://diplome.di.ens.fr/Candidature.html

N.B. Bourses et Hébergement :
Les possibilités d'hébergement à l'ENS pour les étudiants admis à préparer le Diplôme de l'ENS sont extrêmement réduites. Les candidats doivent s'en préocupper sans attendre les résultats des jurys.
Les demandes de bourse et d'hébergement du Crous doivent être effectuées avant le 30 avril environ chaque année.
Les étudiants de 1ere année en informatique à l'ENS seront inscrits en L3 d'informatique à l'université de Paris 7.
Les étudiants de 2ème année en informatqiue à l'ENS seront inscrits en M1 d'informatique à l'ENS de Paris.

5. Inscriptions, turorat et programmes d'études

 A la mi-septembre, les étudiants admis à préparer le diplôme de l'ENS en informatique et les élèves qui souhaitent faire des études en informatique se présentent au secrétariat d'enseignement du département d'informatique pour procéder aux inscriptions administratives et pédagogiques et pour qu'un tuteur leur soit affecté.

5.1. Inscriptions administratives et pédagogiques

Les  élèves/étudiants de la filière informatique du diplôme doivent s'acquitter, pendant chacune des trois années de leur scolarité, d'une double inscription (i) au diplôme universitaire correspondant au cursus de l'année en cours et (ii) au diplôme d'établissement qu'est le diplôme de l'ENS :

Cursus universitaire : après leur admission à suivre les études en informatique à l'ENS, les élèves/étudiants s'inscrivent - via le secrétariat du département d'informatique - en licence (L3) à l'université Paris 7 qui leur délivre le diplôme de licence à l'issue de la première année de scolarité.

Au cours des deux années suivantes, les élèves/étudiants s'inscrivent au Master parisien de recherche en informatique (M.P.R.I.) à l'ENS qui leur délivre le diplôme de master au terme de leur scolarité. Il est également possible de s'inscrire dans un autre master (comme le master recherche spécialité "Mathématiques appliquées - mathématiques/vision/apprentissage" de l'École normale supérieure de Cachan).

Diplôme de l'ENS : l'élève/étudiant s'inscrit au "diplôme de l'École normale supérieure" au bureau des inscriptions du service de la scolarité. Le secrétariat du département d'informatique fournit la liste des documents nécessaires. 

5.2. Tutorat

Un tuteur, enseignant ou chercheur au département d'informatique, est affecté à chaque élève/étudiant. Le rôle du tuteur est d'aider l'élève/étudiant dans l'organisation de ses études, de le conseiller pour ses stages, ses recherches et son orientation.
Il est recommandé de rencontrer régulièrement son tuteur et pas seulement au moment des programmes d'études et des bilans.
L'élève/étudiant peut demander à changer de tuteur.

5.3. Programmes d'études

Chaque année, l'élève/étudiant s'engage sur un programme d'études (ou contrat d'études) annuel qui est déposé auprès de la direction des études de l'ENS après signature du tuteur et du directeur des études du Département d'informatique. Ce document contient les enseignements obligatoires du cursus choisi mais aussi les cours et les activités qui pourront être comptabilisés pour le diplôme, les stages, etc.
Le département d'informatique peut aussi demander des programmes d'études complémentaires.

6. Organisation de la formation pédagogique

Les études en informatique dispensées dans le cadre du diplôme de l'ENS sont organisées sur trois années, correspondant aux années universitaires L3 (Licence), M1 et M2 (Master). L'obtention des diplômes universitaires requiert la validation de 60 ECTS par année. Au terme de ses trois années d'études, l'étudiant qui a obtenu son master et fait valider, par ailleurs, des enseignements supplémentaires à hauteur de 36 unités ECTS se voit décerner le diplôme de l'École normale supérieure. On rappelle qu'aucun enseignement validé dans le cadre d'un diplôme universitaire national (licence ou master) ne peut l'être une seconde fois dans le cadre des enseignements supplémentaires du diplôme de l'ENS.

Les enseignements supplémentaires du diplôme de l'ENS se répartissent en trois catégories :

• un module de langue (3 ECTS). Il existe à l'ENS une structure, intitulée ECLA (Espace des cultures et langues d'ailleurs), spécialisée dans l'enseignement des langues vivantes permettant de valider ce module en première, deuxième ou troisième année du diplôme. Des modules d'anglais pour scientifiques sont également proposés. L'élève peut être dispensé de ce module de langue s'il a effectué un stage de 6 mois ou plus dans un pays non francophone pendant la durée du diplôme ;

• les modules obligatoires de la filière informatique, qui représentent un total de 12 unités ECTS. Ces deux modules sont à choisir parmi les modules de niveau M1 ou M2 du diplôme qui n'ont pas été déjà retenus pour valider le M.P.R.I., ou parmi les modules de mathématiques de niveau M1 ou plus ;

• des modules laissés au libre choix de l'étudiant, dont 12 ECTS au minimum hors informatique. Ces modules sont choisis dans l'offre de formation du Département d'informatique ou d'autres départements de l'ENS, mais aussi dans d'autres formations universitaires, avec l'accord de leurs responsables pédagogiques, sous le contrôle du tuteur et du directeur des études du Département d'informatique.

Il est très fortement recommandé aux étudiants de valider chaque année 12 ECTS d'enseignements supplémentaires.

6.1. Première année

La validation de la licence (L3) d'informatique, dans le cadre du partenariat avec l'université Paris 7, nécessite l'obtention de 60 ECTS, répartis en 48 ECTS de cours de niveau L3 (premier et deuxième semestre) et M1 (deuxième semestre) et 12 ECTS de stage. Ces enseignements sont organisés et donnés à l'ENS. Ils sont régulièrement renouvelés pour suivre de près l'actualité scientifique. La diversité des sujets traités et celle de l'origine des enseignants permettent une grande variété de débouchés potentiels.

Les  élèves/étudiants valident également des enseignements supplémentaires pour le diplôme de l'ENS (au moins 12 ECTS recommandés par année). Des enseignements supplémentaires en informatique de niveau M1 sont proposés au deuxième semestre.

Un stage en laboratoire (universitaire et industriel) est prévu en fin de première année, avec une priorité donnée à la province. À la fin de la première année, la commission des études, en partenariat avec l'université Paris 7, statue sur l'obtention par l'élève/étudiant du diplôme de licence et sur son admission en seconde année du diplôme de l'ENS.

Depuis septembre 2010, une filière mathématiques-informatique est proposée en première année. Les élèves qui la choisiront seront inscrits en L3 de Mathématiques et en L3 d'Informatique et devront valider 120 ECTS (cf. 7.1.4 Filière mathématiques-informatique de 1ère année).

6.2. Deuxième année

La deuxième année est constituée, au premier semestre, de cours de niveau M2 pour 30 ECTS, et au second semestre d'un stage de recherche de 5 mois environ, en laboratoire à l'étranger, comptant 30 ECTS.

En parallèle sont proposés des mini-cours de niveau recherche assurés par des spécialistes (le plus souvent par des professeurs étrangers invités à l'ENS). Les élèves/étudiants valident également des enseignements supplémentaires pour le diplôme de l'ENS (au moins 12 ECTS recommandés par année).

La commission des études se réunit à nouveau en fin de seconde année pour statuer sur la validation par l'élève/étudiant de la première année du master (M1) et sur son admission en troisième année du diplôme de l'ENS.

6.3. Troisième année

Durant cette troisième année, l'élève/étudiant achève son master en suivant au premier semestre des cours de niveau M2 pour 30 ECTS, et effectue au second semestre un stage de recherche de 5 mois minimum, en France ou à l'étranger, validant 30 ECTS. Les élèves/étudiants valident également des enseignements supplémentaires pour le diplôme de l'ENS (au moins 12 ECTS recommandés par année).

L'année se termine le plus fréquemment par le choix d'un directeur et d'un sujet de thèse de doctorat. À ce niveau, les élèves/étudiants s'intègrent progressivement dans un laboratoire de recherche. Afin de faciliter l'insertion dans le milieu de la recherche, il est souvent judicieux de passer tout ou partie de cette année dans un laboratoire de province ou d'un autre pays européen.

La commission des études du Master statue en fin d'année sur l'obtention du diplôme de master par l'élève/'étudiant qui est alors proposé pour l'obtention du diplôme à la direction des études de l'ENS. Si l'étudiant s'est acquitté, en outre, de la validation d'enseignements supplémentaires à hauteur de 36 unités ECTS sur l'ensemble de sa scolarité, l'ENS lui délivre le "diplôme de l'École normale supérieure" avec une spécialité principale qui correspond à celle de son master et, le cas échéant, une spécialité secondaire dans une autre discipline (cf. Présentation du diplôme de l'ENS).

6.3. Stages

Outre les stages obligatoires de L3, M1 et M2, il est possible à partir de la 2ème année de scolarité de la filière informatique de faire une année de stage à l'étranger.

N. B. Il est nécessaire de préparer les stages plusieurs mois à l'avance pour obtenir l'accord des directeurs des études, effectuer les démarches d'obtention de visa, obtenir la signature des conventions de stage, des ordres de mission et parfois obtenir une année de césure (étudiants) ou un congé sans traitement (élèves).

7. Cours de l'année universitaire 2011-2012

Pour chaque cours dans la liste ci-dessous, sont indiqués le nom du professeur responsable et le nombre d'ECTS (European Credit Transfer System).

NB. Cliquez sur le titre pour obtenir une description plus détaillée du cours.

7.1. Première année : licence (L3)

7.1.1 Premier semestre de la licence (L3) d'informatique

 Les 4 cours suivants sont obligatoires :

- Algorithmique et programmation

Jacques Stern, Charles Bouillaguet, Damien Vergnaud

(6 ECTS)

- Langages de programmation et compilation

Jean-Christophe Filliâtre, Louis Mandel

(6 ECTS)

- Langages formels, calculabilité et complexité

Eugène Asarin, Anne Bouillard

(6 ECTS)

- Système digital: de l'algorithme au circuit

Jean Vuillemin, Cédric Pasteur

(6 ECTS)

L'étudiant doit suivre et valider 2 cours  de mathématiques en 1^ère année.

Par conséquent au 1^er semestre, l'étudiant doit choisir et valider au moins 1 cours parmi les 4 cours de mathématiques ou cours communs aux mathématiques et à l'informatique suivants :

- Algèbre 1

Olivier Biquard

(12 ECTS)

- Intégration et probabilités

Zhan SHI

(12 ECTS)

- Logique

Martin Hils

(12 ECTS)

- Structures et algorithmes aleatoires

François Baccelli, Pierre Bremaud, Anne Bouillard

(6 ECTS)

7.1.2 Deuxième semestre de la licence (L3) d'informatique

L' élève/étudiant qui n'aura validé qu'1 cours de maths au 1^er semestre devra suivre et valider 1 des 2 cours de maths suivants :

- Analyse complexe et harmonique

Wendelin Werner

(12 ECTS)

- Apprentissage statistique

 Gilles Stoltz

(12 ECTS)

Cours spécifique à la filière maths-informatique 

Le cours d'informatique suivant est obligatoire :

- Systèmes et réseaux

Marc Pouzet, Louis Mandel

(6 ECTS)

L'élève/étudiant doit choisir et valider au moins 2 cours d'informatique, de niveau M1, parmi les cours suivants. 
     L'un de ces cours peut-être remplacé par un cours de mathématiques de niveau M1.

- Bases de données

Serge Abiteboul

(6 ECTS)

(Ce cours a lieu à l'ENS de Cachan)

- Bases géométriques de l'informatique

Michel  Pocchiola, Jean Ponce

(6 ECTS)

- Génie logiciel et cloud computing

Joannes Vermorel

(6 ECTS)

- L'Informatique scientifique par la pratique

David Naccache

(6 ECTS)

- Initiation à la cryptologie

Jacques Stern, Damien Vergnaud

(6 ECTS)

- Logique informatique

Jean Goubault-Larrecq

(6 ECTS)

(Ce cours a lieu à l'ENS de Cachan)

- Réseaux de Communication

François Baccelli, Anne Bouillard, Anna Busic

(6 ECTS)          

- Théorie de l'information et codage

Marc Lelarge

(6 ECTS)

7.1.3 Stage

L'étudiant doit effectuer un stage d'initiation à la recherche en informatique de 2 à 3 mois dans un laboratoire de recherche public ou privé, en France (de préférence en province) ou en Europe, entre début juin et fin août 2012.

Le stage (qui comprend aussi la rédaction d'un rapport et une soutenance) comptera 12 ECTS pour la licence (L3).

Les stages de L3 des dernières années :  http://www.di.ens.fr/~vergnaud/stages.html

7.1.4 Filière Mathématiques-Informatique de 1^ère année

Les élèves normaliens ou de la sélection internationale qui choisissent cette filière seront inscrits en L3 de mathématiques et en L3 d'informatique.

La filière mathématiques-informatique est organisée conjointement par la FIMFA et le Département d'informatique de l'ENS.

Elle permet :

- aux élèves motivés de poursuivre une doubel formation en mathématique et en informatique. 

- aux élèves encore indécis de repousser d'une année le choix entre ces deux disciplines. 

L'obtention de la licence de mathématiques (60 ECTS) nécessite de valider:

- 4 cours de mathématiques de niveau licence, soit 48 ECTS :

-- Logique (1^er semestre) + Analyse complexe et harmonique (2^ème semestre) sont obligatoires

+ 2 cours au choix parmi les 4 ci-dessous : 

• Intégration et probabilités (1^er semestre)
• Algèbre I  (1^er semestre)
• Algèbre II   (2^ème semestre)
• Processus aléatoires  (2^ème semestre)

- 1 cours spécifique à la filière : Apprentissage statistique (12 ECTS)

L'obtention de la licence d'informatique (60 ECTS) nécessite de valider :

  - 6 cours d'informatique de niveau licence, soit 36 ECTS :

-- Au 1^er semestre, les 4 cours suivants  sont obligatoires : 

Langages formels, Algorithmique et programmation, Langages de programmation et compilation, Structures et algorithmes aléatoires

-- Au 2^ème semestre, choisir 2 cours parmi : 

• Bases géométriques de l'informatique
• Initiation à la cryptologie
• Logique informatique
• Théorie de l'information et codage

- Stage (12 ECTS) et Exposé du cursus maths-informatique (12 ECTS)

Ce travail personnel bi-disciplinaire, encadré par un enseignant de chaque discipline, consiste en : 

- un travail bibliographique comparable à l'exposé de première année du cursus Mathématiques au cours du second semestre, sous la houlette d'un enseignant de mathématiques et/ou d'un enseignant d'informatique, sur un sujet relié à celui du stage,

- un stage niveau L3 dans un laboratoire d'informatique,

- la rédaction d'un mémoire en deux parties et une soutenance en présence d'enseignants des deux disciplines. 

A la fin de la première année, l'élève s'oriente soit vers les mathématiques soit vers l'informatique et rejoint le département de son choix pour la deuxième année. 

7.2. Deuxième année : master (M1)

7.2.1 Premier semestre

Dans le cadre de son diplôme de master M1, l'élève/étudiant doit valider 30 ECTS de cours de niveau M2, à choisir dans la liste suivante ou dans les cours du MPRI (Master Parisien de Recherche en Informatique). Il est également possible, avec l'accord du tuteur et du directeur des études, de choisir les cours dans d'autres masters comme par exemple le master MVA (Mathématiques, Vision, Apprentissage) de l'ENS de Cachan.

Les élèves/étudiants sont fortement encouragés à choisir un ou deux cours supplémentaires dans cette liste, dans le cadre des enseignements à valider pour le diplôme de l'ENS.

- Algorithmes arithmétiques pour la cryptologie

François Morain

(Cours MPRI 2-12-2 : 3 ECTS)

- Algorithmique distribuée pour les réseaux

Pierre Fraigniaud

(Cours MPRI 2-18-1 : 3 ECTS)

- Catégories, lambda-calculs

Paul André Melliès

(Cours Info : 6 ECTS)

- Complexité avancée

Jean Goubault-Larrecq

(Cours Info MPRI 1-17 : 6 ECTS)

- Cryptanalyse : nouvelles tendances en cryptographie - Chiffrement acvancé

 Michel Abdalla, Phong Nguyen, Vadim Lyubashevsky

(Cours MPRI 2-12-1 : 3 ECTS)

- Fondements sur la modélisation des réseaux

François  Baccelli, Alain Jean-Marie & Jean Mairesse

(Cours MPRI 2-17-1 : 3 ECTS)

- Géométrie, Algorithmes et Combinatoire

Michel Pocchiola, Éric Colin de Verdière

(Cours Info : 3 ECTS)

- Initiation à la modélisation et à la simulation numérique

Benoist Desjardin, Thierry Goudon

(Cours Maths : 12 ECTS)

- Interprétation Abstraite : Application à la Vérification et à l'Analyse Statique

Patrick Cousot, Radhia Cousot

(Cours MPRI 2-6 : 6 ECTS)

- Introduction à la vision artificielle 

Jean Ponce

(Cours Info : 4 ECTS)

- Méthodes mathématiques pour les neurosciences

Olivier Faugeras, Grégory Faye, Jonathan Touboul

(Cours Info & MVA : 4 ECTS & Cours UMPC Maths et Applications)

- Planification de mouvement en robotique et en animation graphique : du continu au combinatoire via la commandabilité des sytèmes

Jean-Paul Laumond

(Cours Info : 6 ECTS)

- Protocoles cryptographiques: preuves formelles et calculatoires

Bruno Blanchet, Stéphanie Delaune

(Cours MPRI 2-30 : 6 ECTS)

- Reconnaissance d'objets et vision artificielle

 Ivan Laptev, Jean  Ponce, Josef Sivic, Cordelia Schmid

(Cours Info et MVA : 4 ECTS)

- Statistique

Gérard Biau

(Cours Maths : 12 ECTS)

- Systèmes synchrones

Marc  Pouzet, Jean Vuillemin

(Cours MPRI 2-23-1 : 3 ECTS)

7.2.2 Deuxième semestre : stage

L' élève/étudiant doit effectuer un stage de 5 mois environ à l'étranger pour valider 30 ECTS dans le cadre de son diplôme M1.

7.3. Troisième année : master (M2)

7.3.1 Premier semestre

L’étudiant doit valider 30 ECTS de cours du MPRI de niveau M2. Il est possible de valider certains cours d’une autre formation universitaire, avec l’accord de son tuteur et l’accord de Pierre-Alain Fouque qui représente l’ENS de Paris auprès de la commission des études du MPRI.

A la place du M2 du MPRI, l’élève/étudiant peut préparer et valider le M2 du Master MVA (Mathématiques, Vision, Apprentissage) de l’ENS Cachan avec l’accord de son tuteur et l’accord du directeur des études du département d’informatique.

L' élève/étudiant doit également valider des enseignements supplémentaires pour valider le diplôme de l'ENS, s'il n'a pas déjà acquis les 36 ECTS requis.

7.3.2 Deuxième semestre : stage

Pour le M2 du MPRI, l’étudiant doit effectuer un stage d’environ 5 mois, en France ou à l’étranger, qui comptera 30 ECTS.

Pourle M2 du MVA, le stage obligatoire est d’environ 4 mois et a lieu entre avril et septembre.

8. Enseignements d'informatique du diplôme de l'ENS (hors filière informatique)

8.1. L'informatique comme "spécialité secondaire" du diplôme de l'ENS

Un élève/étudiant inscrit dans une autre filière du diplôme que la filière informatique (et donc rattaché à un autre département de l'ENS que le Département d'informatique) peut choisir de valider un ensemble cohérent d'enseignements d'informatique pouvant constituer la spécialité secondaire de son diplôme. Cet ensemble cohérent d'enseignements doit représenter un total d'au moins 24 ECTS.

8.3. L'informatique dans le diplôme de l'ENS

Les étudiants possédant déjà des notions de base en informatique peuvent suivre des cours de L3 au premier semestre.

Le Département d'Informatique propose également un cours d'initiation à la programmation au deuxième semestre, ouvert à tous :

- Initiation à la programmation pour pour non-informaticiens

Damien Vergnaud

(3 ECTS)

(Cours enseigné au 2ème semestre)

Ce cours est ouvert aux élèves/étudiants de toutes les disciplines, littéraires comme scientifiques. Aucune connaissance préalable en programmation n'est requise. Le cours n'est pas orienté à priori vers une application particulière. Il s'adaptera aux besoins des élèves. Il sera utile au non informaticien qui aura un jour à programmer rapidement une simulation, mais aussi à toute personne souhaitant comprendre comment sont faits les programmes informatiques.

9. Programme des cours de l'année 2011/2012

Algèbre 1

(Olivier Biquard)

1. Groupes, action d'un groupe sur un ensemble. Groupe symétrique. Sous-groupes distingués et groupes quotients, produit semi-directs de groupes et extensions de groupes.
   Groupes des éléments inversibles d'un groupe cyclique et applications arithmétiques.

2. Groupes et géométrie : groupe linéaire, groupe orthogonal, groupes classiques. Formes quadratiques. Formes hermitiennes et formes alternées.

3. Algèbre multilinéaire : produit tensoriel, algèbre tensorielle, algèbre symétrique, algèbre extérieure, algèbre enveloppante. 

4. Eléments de théorie des représentations : algèbres semi-simples, théorème de Burnside, de Wedderburn, du bicommutant. Dualité de Schur-Weyl.

(Cours de Maths : 12 ECTS)

Voir la page de ce cours : http://www.math.ens.fr/enseignement/fiche_cours.html?cours=1

Algèbre 2

(Olivier Debarre)

(Cours de Maths : 12 ECTS)

Voir la page de ce cours : http://www.math.ens.fr/enseignement/fiche_cours.html?cours=11

Algorithmes arithmétiques pour la cryptologie

(François Morain)

L'objectif du cours est de présenter aux étudiants les concepts et les outils de la cryptologie moderne à clefs publiques, dont les briques de bases mathématiques se trouvent dans les corps finis, et, de plus en plus, dans les courbes algébriques (elliptiques ou hyperelliptiques). Le cours se propose de présenter la théorie algorithmique des nombres, alliance de la théorie des nombres classique et de la théorie de la complexité, avec pour objectifs les applications à la cryptologie. Ce cours se veut comme présentant également les fondements mathématiques du cours 2-12-1. Il forme un tout cohérent avec les autres cours du MPRI traitant de cryptographie, comme par exemple les cours 2-30, 2-13-1 et 2-13-2.

Le cours est découpé en 3 parties:

- Algorithmique des entiers et des polynômes -- 6 heures (François Morain)

Cette partie débutera par une étude de l'algorithmique des anneaux Z/NZ et des corps finis. On étudiera brièvement le problème de la primalité, via l'angle des tests de composition.

- Factorisation et logarithme discret -- 9 heures (Emmanuel Thomé)

Dans cette partie, on étudiera les deux problèmes algorithmiques fondamentaux soulevés par l'étude de deux des principales primitives asymétriques : la factorisation des entiers et le logarithme discret. Cette étude permettra d'identifier des clés faibles et d'estimer la sécurité correspondant à une taille de clé donnée au vu des connaissances contemporaines.

- Courbes elliptiques et hyperelliptiques - 9 heures (Ben Smith)

Le but de cette partie est de donner les définitions et les propriétés des courbes sur les corps finis qui sont utiles pour construire un cryptosystème à base de courbes. Nous étudierons les diverses problématiques soulevées par la construction d'un tel système : arithmétique efficace, cardinalité, difficulté du problème du logarithmet discret, dans le cas des courbes elliptiques et des jacobiennes de courbes hyperelliptiques de genre 2.

Une seance sera consacrée aux couplages, abordera leur calcul et leur sécurité, et presentera une application aux cryptosystèmes fondés sur l'identité.

Prérequis spécifiques

Nous attendons que les élèves aient déjà suivis un cours d'introduction à la cryptologie. Les principes généraux de la cryptologie (intégrité, authenticité, confidentialité) devront être connus ainsi que les techniques artisanales (Vigénère). On supposera que les étudiants ont déjà quelques notions sur les PKI, sur les canaux sécurisés (avec un exemple comme SSL), et sur les preuves de connaissances.

Les résultats de base sur les corps finis, sur l'arithmétique des entiers et sur la structure des entiers modulaires devront être connus ainsi que quelques résultats sur les polynômes (algorithme de Berlekamp).

De même, les primitives asymétriques classiques (RSA et Diffie-Hellman) devront être connues.

Remarque: Aucune connaissance préalable n'est demandée sur les courbes algébriques.

Prérequis généraux

Ces prérequis ne sont pas spécifiques à la cryptologie et sont déjà essentiellement inclus dans la liste générale.

On aura besoin des notions de classes de complexité, de machine de Turing, de problèmes NP. Un minimum de connaissance en algèbre et en probabilité sera aussi requis. Enfin les outils algorithmiques de base doivent être maîtrisés.

Bibliographie

• H. Cohen, A course in algorithmic algebraic number theory, Springer Verlag, 2000.

• J. von zur Gathen, J. Gerhard, Modern Computer Algebra, Cambridge University Press, 2003.

• R. Crandall, C. Pomerance, Primes -- A Computational Perspective, Springer Verlag, 2005.

• A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography, CRC Press.

• V. Shoup, A computational introduction to number theory and algebra, Cambridge University Press, 2008.

Algorithmique distribuée pour les réseaux

(Pierre Fraigniaud)

Algorithmique et programmation

(Jacques Stern)

Le cours présente les bases sur les structures de données et les principes de conception des algorithmes ainsi qu'un certain nombre de développements plus avancés. On attend des étudiants un minimum de connaissances algorithmiques. Chaque séance est organisée en deux parties, la première consacrée aux connaissances de base et la seconde à un résultat plus avancé (ou exceptionnellement plusieurs).

Algorithmes : conception et évaluation

• cours de base : terminaison, complexité, stratégies de programmation,

• cours avancé : bin packing, allocation dynamique de mémoire.

Première partie : algorithmique des structures de données

• Tri et hachage

  • cours de base : exemples de tris, hachage, collisions, hachage ouvert,

  • cours avancé : tri Shell.

• Recherche de motifs

  • cours de base : Rabin-Karp, Knuth-Morris-Pratt,

  • cours avancé : algorithmes de bio-informatique.

• Arbres

  • cours de base : arbres de recherche, exemples,

  • cours avancé : tas fusionnables (tas binomiaux, tas de Fibonacci).

• Graphes

  • cours de base : Fermeture transitive, composantes connexes, plus courts chemins,

  • cours avancé : valeurs propres et graphe d'expansion.

• Flots

  • cours de base : Ford-Fulkerson, Edmonds-Karp,

  • cours avancé : Flots unitaires, Dinic, couplages maximaux

Deuxième partie : algorithmique numérique et symbolique

• Entiers

  • cours de base : multiplication, exponentiation,

  • cours avancé : tests de primalité.

• Transformation de Fourier rapide

  • cours de base : FFT, complexité,

  • cours avancé : multiplication rapide.

• Programmation linéaire

  • cours de base : simplexe, complexité,

  • cours avancé : méthode de l'ellipsoïde.

• Algèbre linéaire et géométrie des nombres

  • cours de base : décomposition LUP, moindres carrés,

  • cours avancé : réseaux à coordonnées entières; algorithme LLL.

• Factorisation des Polynômes

  • cours de base : polynômes à coefficients entiers, pgcd, polynômes binaires,

  • cours avancé : algorithme de Berlekamp, Cantor-Zassenhaus.

• Systèmes d'équations polynomiales

  • cours de base : algorithmes de base standard,

  • cours avancé : complexité exp-space.

(Cours Info : 6 ECTS)

 Page web du cours :  http://www.di.ens.fr/~bouillaguet/teaching.html

Analyse complexe et harmonique

(Wendelin Werner)

•  Fonctions harmoniques discrètes, fonctions harmonqiues, problème de Dirichlet, Noyau de Poisson, fonctions harmoniques conjuguées, principe de réflexion.
  
•  Définition et premières propiétés des fonctions analytiques, exemples.
  
•  Transformations conformes : Théorème de Riemann, exemples.
  
•  Formule de Cauchy et applications, fonctions méromorphes, résidus.
  
•  Quelques considérations sur la fonction zeta et sur les fonctions elliptiques.
  

L.V. Ahlfors, Complex analysis, 3rd Ed., McGraw-Hill

(Cours de Maths : 12 ECTS)

Voir la page de ce cours : http://www.math.ens.fr/enseignement/fiche_cours.html?cours=7

Apprentissage statistique

(Sylvain Arlot, Francis Bach, Olivier Catoni, Guillaume Obozinski, Gilles Stoltz)

Cours spécifique à la filière maths-informatique

L'apprentissage est un domaine à la frontière entre mathématiques appliquées (statistique et optimisation) et informatique. On y considère un environnement incertain, produisant des variables observées (dites explicatives et qui sont souvent quantitatives)auxquelles sont associées des variables inconnues (qui peuvent être qualitatives ou quantitatives).

Ce type d’environnement est bien décrit par un modèle aléatoire, précisant la loi jointe des variables observées et inconnues.La théorie des probabilités et la statistique en déterminent le choix et les procédures d’estimation. Cependant, la théorie de l’apprentissage a un objectif plus simple et plus concret : il s’agit surtout de bien prédire les variables inconnues à partir des variables observées. (En clair, on s’intéresse surtout aux lois conditionnelles des variables inconnues étant données les variables observées.)
Par ailleurs, on tâchera de faire les hypothèses les plus faibles possibles sur la loi jointe de l’environnement. On parle d’apprentissage statistique.

Le lien avec l’informatique se fait à travers la recherche de méthodes si possible efficaces à mettre en oeuvre (du point de vue de la complexité computationnelle et/ou mémoire).
On vise également l'obtention de procédures les plus automatiquement possibles, qui se calibrent elles-mêmes et sachent s'adapter à l'environnement, même si celui-ci change : c'est pourquoi on parle d'apprentissage automatique ("machine learning"), puisque l'on veut que l'homme, hormis la construction initiale de la méthode, intervienne le moins possible.

Il sera impossible, dans le cadre de ce cours, de dresser un panorama exhaustif de ce dommaine déjà vaste et encore en expansion rapide.
Les thèmes applicatifs suivants seront privilégiés  :
- Classification (affectation d'une étiquette à des données)
- Débruitage d'un signal (à la fois pour des petites ou des grands nombres de variables explicatives)
- Apprentissage avec données séquentielles
On étudiera les concepts théoriques et algorithmiques qui les motivent et les justifient et on présentera des implémentations et illustrations de ces méthodes sur données réelles ou simulées.

Les seuls pré-requis sont d'être familier avec les fondements de la théorie des probabilités (notion de variables aléatoires, théorèmes de convergence, espérance condtionnelle), ceux vus au cours d'intégration et probabuilités du premier semestre ;  il n'est pas nécessaire de suivre le cours de processus aléatoires du second semestre. En revanche, quelques nouveaux outils probabilistes (et notamment, des inégalités de concentration) seront introduits.

Page de ce cours  : http://www.math.ens.fr/cours-apprentissage/

Bases de données

(Serge Abiteboul)

1. Introduction: Bases de données et SGBD
2. Modèle relationnel: Algèbre et calcul relationnels, théorème d'équivalence
3. Langages utilisés en pratique, SQL
4. Gestion de fichiers, structures d'accès: Arbres B, hachage
5. Optimisation de requêtes
6. Concurrence et transactions: Sérialisabilité, verrouillage à deux phases, estampillage et pannes
7. Gestion de données distribuées
8. Contraintes d'intégrité

Descriptif de ce cours mis à jour sur : http://www.dptinfo.ens-cachan.fr/L3/contenu.php#bd

Page web du cours: http://www-rocq.inria.fr/~abitebou/DBCOURSE/

Page web du cours 2011-2012 (Cachan et Collège de France) : http://www.abiteboul.com/2011/DBCOURSE/

Bibliographie :

• Database Management Systems by Raghu Ramakrishnan and Johannes Gehrke. McGraw-Hill.

• Database System Implementation by H. Garcia-Molina, J.D. Ullman and J. Widom. Prentice-Hall.

Bases géométriques de l'Informatique

(Michel Pocchiola et Jean Ponce)

Ce cours introduit les bases géométriques et algorithmiques des domaines de l'informatique où la géométrie joue un rôle fondamental, en particulier la géométrie algorithmique et la vision artificielle.

La première partie du cours est consacrée à la géométrie discrète et aux objets, techniques et applications de la géométrie algorithmique. On y développe en particulier l'étude des polyèdres convexes, des arrangements d'hyperplans et des techniques de randomisation. La seconde partie du cours est consacrée à une présentation concrète de notions élémentaires de géométrie projective et de géométrie différentielle et de leur application à la modélisation de systèmes de caméras en vision artificielle.

1. Cônes, polyèdres et polytopes, treillis des faces d'un polyèdre, polytopes cycliques et théorème de la borne supérieure, diagrammes de Voronoi, algorithmes et applications.

2. Arrangements d'hyperplans, niveaux, théorème de la zone, cuttings, algorithmes et applications.

3. Hypergraphes géométriques, théorie des epsilon-nets, algorithmes et applications.

4. Caméras euclidiennes, affines, et projectives : perspective centrale et projection parallèle ; éléments de géométrie affine et projective ; projection et projection inverse de points et de droites.

5. Ensembles de caméras : géométrie épipolaire ; tenseur trifocal ; étalonnage projectif ; mouvement affine ou projectif; étalonnage euclidien : la conique absolue de Chasles et ses cousines.

6. Les surfaces euclidiennes lisses et leurs silhouettes : éléments de géométrie différentielle descriptive ; le théorème de Koenderink; les graphes d'aspects.

Bibliographie :

[1] M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin,Germany, 2nd edition, 2000.

[2] D.A. Forsyth and J. Ponce. Computer Vision: A Modern Approach.Prentice Hall, 2003.

[3] J. E. Goodman and J. O'Rourke, editors. Handbook of Discrete and Computational Geometry. CRC Press, 2nd edition, 2004.

[4] J. Matousek. Lectures on Discrete Geometry. Number 212 in Graduate texts in Mathematics. Springer-Verlag, 2002.

[5] K. Mulmuley. Computational Geometry: An Introduction Through RandomizedAlgorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.

(Cours Info : 6 ECTS)

Catégories, lambda-calculs

(Paul-André Melliès)

Ce cours s'intéresse à la syntaxe et à la sémantique des langages de programmation, à partir du lambda-calcul. On rappellera les principaux théorèmes syntaxiques du lambda-calcul: confluence, standardisation, résultats de terminaison. Puis on étudiera les modèles du lambda-calcul : pour ce faire, le langage de la théorie des catégories sera utilisé.

Plus généralement, les catégories servent à interpréter bien des extensions du lambda-calcul (avec références, exceptions, etc.), ainsi qu'à comprendre et structurer des notions de concurrence (notamment la notion de bisimulation). Le cours fournit une introduction assez générale et complète au formalisme catégorique, et l'applique à la sémantique des langages de programmation.

Interpréter un langage dans un modèle s'apparente à une compilation, et les modèles offrent ainsi des occasions de retour sur la syntaxe : machines abstraites pour l'exécution des programmes, preuves de propriétés de programmes. Dans le même ordre d'idées, ce sont des observations sur un modèle du lambda-calcul qui ont conduit Girard à la logique linéaire, munie de connecteurs exprimant un contrôle sur l'usage des hypothèses vues comme ressources, ou bien plus récemment Thomas Ehrhard au lambda-calcul différentiel, qui relie de manière originale substitution et... formule de Taylor.

Support de cours :

- Domains and Lambda-calculi. R. Amadio et P.-L. Curien. Cambridge University Press, 1998.

- Categorical semantics of linear logic. P.-A. Melliès. Paru dans la collection Panorama et Synthèse, Société Mathématique de France, 2009.

Et aussi :

- Semantics of programming languages. C. Gunter. MIT Press, 1992.

- Categories, types and structures. A. Asperti and G. Longo. MIT Press, 1991 (épuisé, mais disponible sur la page web de G. Longo (di.ens.fr).

- Theories of programming languages. J. Reynolds. Cambridge University Press, 1992.

Pour le lambda-calcul :

- The Lambda-calculus. H. Barendregt. North Holland, 1984.

- Lambda-calcul, types et modèles. J.-L. Krivine. Masson, 1990.

Pour les catégories, lire les premiers chapitres d'un livre tel que:

- Toposes, Triples and Theories. M. Barr and C. Wells. Springer, 1985.

- Sheaves in Geometry and Logic: a first introduction to topos theory. S. Mac Lane and Ieke Moerdjik. Springer, 1992.

Complexité avancée

(Jean Goubault-Larrecq)

La théorie de la complexité va bien au-delà de celle de la NP-complétude. Le but de ce cours est d'aller regarder un certain nombre d'autres constructions fondamentales de la théorie de la complexité: complexité en espace, notions de machines alternantes, ou randomisées. On y verra quelques théorèmes fascinants: l'équivalence du temps alternant et de l'espace déterministe par exemple, ou le théorème IP=PSPACE de Shamir.

Description du cours

Pré-requis

On s'attend à ce que les étudiants aient une certaine familiarité avec la notion de Machine de Turing, la classe P (temps polynomial déterministe), la classe NP (temps polynomial non-déterministe), les notions de réductions en temps polynomial, le théorème de Cook (SAT est NP-complet) même si toutes ses notions seront rapidement revues au début du cours.

Bibliographie

Livres:

• Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.

• Sanjeev Arora and Boaz Barak. Computational Complexity. Cambridge University Press, 2009. (une pré-version est gracieusement disponible ici http://www.cs.princeton.edu/theory/complexity/)

Polycopiés:

• http://www.lsv.ens-cachan.fr/~goubault/Complexite/nl.pdf

• http://www.pps.jussieu.fr/~treinen/teaching/stic/complexite

Cryptanalyse : nouvelles tendances en cryptographie - chiffrement avancé

(Michel Abdalla, Phong Nguyen, Vadim Lyubashevsky)

L'objectif de ce cours est d'amener les élèves à la frontière de la recherche actuelle en cryptographie à clé publique et sur le calcul sur des données chiffrées.

Pré-requis  :

• Pré-requis spécifiques

Les étudiants sont censés avoir suivi un cours d'initiation à la cryptologie. Les principes généraux de la cryptologie (intégrité, authenticité, confidentialité) devront être connus ainsi que les  résultats de base de la théorie des nombres et de l'algèbre linéaire

• Pré-requis généraux

Ces pré-requis ne sont pas spécifiques à la cryptologie et sont déjà essentiellement inclus dans la liste générale du MPRI.

Un minimum de connaissance en algèbre et en probabilité sera aussi requis. Enfin les outils algorithmiques de base doivent être maîtrisés.

(Cours MPRI 2-12-1 : 3 ECTS)

Pour plus de renseignements sur ce cours, consulter sa page sur le site du MPRI : http://mpri.master.univ-paris7.fr/

Fondements sur la modélisation des réseaux

(François Baccelli,  Jean Mairesse)

Le but de ce cours est double :

* proposer des modèles mathématiques pertinents pour les réseaux de communications;

* donner les bases théoriques permettant de mener a bien l'analyse de la dynamique de ces modèles.

Le cours est structuré en thèmes, pouvant être plus ou moins développés suivant les années.

* Réseaux de files d'attente et modélisation markovienne (réseaux à commutation de paquets, réseaux à commutation de circuits).

* Dynamique des systèmes à événements discrets temporisés (semi-anneau max plus, inf convolutions, fonctions topicales, réseaux de Petri temporisés, modèles d'empilements de pièces, etc.).

* Contrôle de flux dans les réseaux de communication (TCP, contrôle de flux et de congestion, régulation, network calculus, ordonnancement etc.).

* Graphes aléatoires (à la Erdos-Renyi, géométriques) et modèles de percolation.

Pré-requis

Une familiarité avec les probabilités discrètes et les chaînes de Markov, est préférable.

Bibliographie

• * Reversibility and Stochastic Networks, Wiley, 1979.

  * Synchronization and Linearity, F. Baccelli, G. Cohen, G.J. Olsder and J.P. Quadrat, Wiley 1992.

  * Data networks, D. Bertsekas and R. Gallager, Prentice Hall, 1992.

  * Performance Guarantees in Communication Networks, C.S. Chang, Springer, 1999.)

Génie logiciel et cloud computing

(Joannès Vermorel)

Ce cours présente les concepts fondamentaux du génie logiciel, avec un intérêt pour les systèmes complexes / distribués, notamment dans le cadre du "cloud computing".

Le cours est associé à un projet de développement logiciel. Chaque séance inclut un cours magistral suivi d'un bilan collectif sur l'avancement du projet.

Pré-requis: Ce cours ne forme pas à la programmation. On attend des élèves qu'ils soient déjà familiers avec un ou plusieurs langages de programmation.

Sans être indispensable, la participation préalable aux cours "Algorithmique et programmation" et "Système digital: de l'algorithme au circuit" lors du premier semestre est un plus.

Le génie logiciel est l'étude de l'activité de production de logiciels en tant qu'activité économique, où les ressources matérielles/humaines (ainsi que les délais) sont limitées.

Les avancées de la dernière décennie dans ce domaine ont permis des gains de productivité très importants.

On s'attachera à comprendre comment des pratiques associées à des avancées technologiques influencent (en bien ou en mal) la productivité dans le domaine logiciel.

Les systèmes informatiques distribués, notamment le "cloud computing", seront intégrés au cours comme objet d'étude, mais aussi comme projet en équipe par les élèves.

La motivation de ce choix est double: l'évolution du matériel informatique tend aujourd'hui vers le "tout-distribué"; par ailleurs les systèmes distribués sont redoutablement difficiles à développer et à debugger.

Notes de cours : http://www.vermorel.com/softeng.html

Bibliographie:

- AntiPatterns by William J. Brown, Raphael C. Malveau, Hays W. "Skip" McCormick, Thomas J. Mowbray

- Joel on Software: And on Diverse and Occasionally Related Matters That Will Prove of Interest to Software Developers, Designers, and Managers, and to Those Who, Whether by Good Fortune or Ill Luck, Work with Them in Some Capacity by Joel Spolsky

- Design Patterns: Elements of Reusable Object-Oriented Software by Erich Gamma, Richard Helm, Ralph Johnson, John M. Vlissides

Géométrie, Algorithmes et Combinatoire

(Michel Pocchiola, Éric Colin de Verdière)

L'objectif du cours est de donner aux étudiants les connaissances de base pour aborder, sur des sujets de recherche bien délimités et d'actualité, la littérature récente du domaine de la géométrie discrète et algorithmique.

1. Arrangements (12h, Michel Pocchiola)

• arrangements de droites, complexité de sous-structures, algorithmes

• arrangements de pseudodroites et plans projectifs géométriques,

• arrangements de double pseudodroites, algorithmique des graphes de visibilité

• arrangements d'hyperplans, matroides orientés, théorème de Folkman & Lawrence

• Graphes planaires : définitions et algorithmes

• Surfaces : classification et modèle algorithmique

• Calcul de plus courts cycles non triviaux sur une surface

• Calcul de plus courtes décompositions de surfaces

• Algorithmes de raccourcissement de courbes à homotopie fixée

Bibliographie

- M. Armstrong. Basic topology. Undergraduate Texts in Mathematics. Springer-Verlag, 1983.

- B. Aronov, S. Basu, J. Pach, and M. Sharir, editors. Discrete and Computational Geometry -- The Goodman-Pollack Festschrift, volume 25 of Algorithms and Combinatorics. Springer-Verlag, June 2003.

- M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, Germany, 2nd edition, 2000.

- Björner, Las Vergnas, Sturmfels, White and Ziegler. Oriented Matroids. Cambridge, Second Edition, 1999.

- E. Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge, 2001.

- J. E. Goodman and J. O'Rourke, editors. Handbook of Discrete and Computational Geometry. CRC Press, 2nd Edition, 2004.

- J. L. Gross and T. W.Tucker. Topological Graph Theory Dover Publications, INC, 2001. Originally published: Wiley, 1987

- Allen Hatcher. Algebraic Geometry. Cambridge University Press, 2002.

- J. Matousek. Lectures on Discrete Geometry. Number 212 in Graduate texts in Mathematics. Springer-Verlag, 2002.

- B. Mohar and C. Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. John Hopkins University Press, 2001.

- K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.

- J. Pach and M. Sharir. Combinatorial Geometry and Its Algorithmic Applications. Volume 152 in Mathematical Surveys and Monographs. American Mathematical Society, 2009.

(Cours Info : 3 ECTS)

L'Informatique scientifique par la pratique

(David Naccache)

Ce cours aborde les disciplines scientifiques liées au traitement automatique de l'information à travers la microprogrammation et la mise en oeuvre optimisée.

L'objectif pédagogique du cours est double :

1.  Initier les étudiants aux technologies de conception proches de la machine: matériel et microprogramme.
   Initiation puis maitrise de nouveaux outils et langages assembleur.

2.  Ce faisant familiariser les étudiants avec certains algorithmes communs intervenant en informatique scientifique : compression, ramasse-miettes, hachage géométrique, correction d'erreurs, arithmétique entière, arithmétique en virgule flottante, solution par retraits itérés (backtracking), inférence de type, FFT et déconvolution. Elargissement, par la pratique, de la "culture informatique scientifique" de l'étudiant.

Les étudiants affronteront les contraintes rencontrées lors de programmation de ces algorithmes (e.g. taille de code, complexités mémoire et temps etc) ainsi que les différentes techniques permettant d'adapter les algorithmes à des architectures (e.g. mise en uvre en bit-slice, calcul partagé, évaluation paresseuse etc). A titre de projet les étudiants pourraient mettre en uvre de manière optimisée des algorithmes vus lors ou du cours ou lors d'autres cours dispensés dans le cadre de la formation interuniversitaire en informatique de l'ENS (traitement des images, optimisation de circuits électroniques, cryptographie, compilation etc).

1. Le microprocesseur 68HC05

• Présentation des outils de programmation en assembleur 68HC05. Architecture, Ports, registres, mémoires, ALU.

• TD : conception d'une librairie de calcul sur les nombres flottants en assembleur. Changement de la saturation des points d'une photographie du portique de l'ENS en utilisant une multiplication à virgule flottante arrondie.

2. La compression

• Introduction : Théorie de Shannon. Compression entropique. Compression par les méthodes RLE, LZW et Huffman.

• TD : mise en uvre de RLE, LZW et Huffman sur le 68HC05. Compression de la photographie du portique.

3. La correction d'erreurs

• Introduction : Contrôle des erreurs par codage algébrique. Codes de Viterbi. Turbo codes.

• TD : codeur / décodeur pour les codes de Hamming et de Reed-Solomon sur le 68HC05. Protection par code correcteur de l'image du portique. Bruitage de l'image à différents SNRs, affichage et correction.

4. Arithmétique sur les grands nombres : multiplication et réduction modulaire

• Introduction : Multiplication multi-précision et algorithmes de réduction de Montgomery et de Barrett. Preuve des deux algorithmes et leur analyse. Techniques de multiplication rapide (Solovay-Strassen) et multiplication à faible nombre de changements d'état.

• TD : Multiplication multi-précision et réduction modulaire Montgomery et Barrett sur le 68HC05. Codage de fonctions de calcul RNS (Residue Number System).

5. La cryptographie par la pratique.

• Introduction : Signature et chiffrement, présentation et/ou rappel de RSA.

• TD codage d'un chiffrement RSA et d'une vérification de signature à l'aide de la librairie de calcul sur les grands nombres codée lors du TD précédent. Vérification d'une signature numérique créée sur Mathématica sur l'image du portique.

6. Ramasse-miettes par la pratique.

• Introduction au ramassage de miettes (garbage collection)

• TD : Ramasse-miettes par la méthode mark & sweep. Découpage de l'image du portique en morceaux et assemblage des morceaux en un chemin de moindres mouvements à l'aide du programme de mark & sweep.

7. La machine de Minsky

• Architecture.

• TD : codage d'un simulateur de machine de Minsky et mise en uvre d'un programme très simple sur ce simulateur.

8. La technique des retraits itérés

• Présentation de la technique des retraits itérés.

• TD : Résolution du problème de lasermaze par la technique des retraits itérés. Détection du plus long chemin de reflets dans un extrait de l'image du portique par la méthode des retraits itérés.

9. La transformée de Hough et le hachage géométrique.

• Le problème de la détection de droites, présentation des algorithmes.

• TD : Codage en assembleur de la transformée de Hough. Extraction d'une droite de l'image du portique.

10. FFT et déconvolution. Régularisation de Tikhonov

• TD : Codage en assembleur d'une routine de convolution et de déconvolution. Convolution de l'image du portique avec un filtre gaussien et déconvolution. Essais avec différents SNRs.

Séance finale :

• Exposition des résultats de tous les TDs du module (avec des posters et démonstrations) à l'intention des élèves et chercheurs internes et externes.

Initiation à la cryptologie

(Jacques Stern, Damien Vergnaud)

Ce cours s'adresse aux étudiants ayant un goût pour l'algorithmique, à la fois dans ses aspects mathématiques et dans ses aspects pratiques. Son but est d'enseigner la problématique de la cryptologie, et les principaux outils utilisés par la cryptologie pour proposer des solutions aux problèmes de sécurité.

Ce cours est aussi proposé comme cours de niveau 1 pour le MPRI et en tant que tel sert de préparation au cours de niveau 2 du MPRI.

Le cours est divisé en 6 parties relativement indépendantes, chacune de 4 heures de cours et 4 heures de TD.

• Introduction à la cryptographie

  • Permutations, substitutions, cryptanalyse (types d'attaques).

  • Intégrité, confidentialité, authenticité. One Time Pad.

• Cryptographie symétrique

  • Chiffrement par flot.

  • Chiffrement par bloc.

  • Modes d'opération (CBC, ECB, CTR).

  • Exemples: DES, AES, RC4, A5/1.

  • Hachage, MAC.

• Compléments d'algorithmique

  • Algorithmique des entiers.

  • Arithmétique modulaire.

  • Corps finis.

• Cryptographie asymétrique

  • RSA, Diffie-Hellman, El Gamal.

  • Multiplicativité de RSA (Hastad, attaques multiplicatives).

  • One-way Functions, trappes.

  • Générateurs pseudo aléatoires.

  • Signatures RSA, El Gamal.

• Protocoles

  • Introduction aux preuves à divulgation nulle de connaissance (ZK).

  • Identification, signatures (FS, Schnorr).

• Applications

  • PKI, IPSEC.

  • Canal sécurisé : SSL.

(Cours Info : 6 ECTS)

Pour plus de renseignements sur ce cours MPRI 1-13, consulter sa page sur le site du MPRI : http://mpri.master.univ-paris7.fr/

Initiation à la modélisation et à la simulation numérique

(Benoist Desjardins, Thierry Goudon)

Ce cours a pour objet de présenter certaines équations différentielles issues de la physique et d'expliquer comment l'analyse mathématique guide la mise en oeuvre de méthodes numériques permettant la résolution de ces équations à l'aide de calculs par ordinateurs.
Prérequis : Bases de calcul différentiel, intégration, analyse fonctionelle et curiosité scientifique.

Programme:

• Rappels sur les Equations Différentielles Ordinaires et leur approximation numérique
  (schémas d'Euler, Crank-Nicolson, schémas d'ordre plus élevé, notions de stabilité et consistance).
  

• Phénomènes de transport, méthodes de différences finies et volumes finis
  (notion de décentrement, viscosité numérique, analyse de stabilité L2 et L1).
  

• Phénomènes de diffusion, méthodes de différences finies
  (analyse de stabilité, schémas explicite et implicite, problèmes de convection-diffusion...)
  

• Un exemple issu de la mécanique des fluides : l'équation de Stokes (analyse fonctionnelle du problème :
  point de vue variationnel, point de vue par optimisation ; méthodes numériques : méthodes spectrales, schéma différences finies)
  

• Introduction au calcul haute performance : décomposition de domaines et éléments de parallélisation.

Le cours sera enrichi par des exposés et des projets comprenant un travail de simulation numérique.
L'évaluation sera basée sur une présentation orale.

Voir la page de ce cours  : http://www.math.ens.fr/enseignement/fiche_cours.html?cours=14#

Initiation à la programmation pour pour non-informaticiens (deuxième semestre).

(Damien Vergnaud)

Ce cours est ouvert aux élèves de toutes les disciplines, littéraires comme scientifiques. Aucune connaissance préalable en programmation n'est requise. Le cours n'est pas orienté à priori vers une application particulière. Il s'adaptera aux besoins des élèves. Il sera utile au non informaticien qui aura un jour à programmer rapidement une simulation, mais aussi à toute personne souhaitant comprendre comment sont faits les programmes informatiques.

• Python en ligne de commande (la calculatrice, les variables, les types, ...)
• Programmation (scripts, conditions, boucles, fonctions)
• Calcul scientifique en Python (Scipy/Numpy/Pylab)
• Calcul efficace : programmation vectorielle (comme Matlab)

(Cours Info : 3 ECTS)

Pour plus de renseignements sur ce cours, consulter  : http://www.di.ens.fr/~vergnaud/initPython.html

Intégration et probabilités

(Zhan SHI)

1. Intégration

• • Espaces Mesurés

  • Intégration par rapport à une mesure

  • Construction de mesures

  • Espaces Lp

  • Mesures produits

  • Mesures signées

  • Formule de changement de variables

2. Probabilités

• • Fondements de la théorie des probabilités

  • Indépendance

  • Convergence de variables aléatoires

Interprétation Abstraite : Application à la Vérification et à l'Analyse Statique

(Patrick Cousot, Radhia Cousot)

L'analyse statique de programmes consiste à vérifier statiquement (sans les exécuter) des propriétés dynamiques (à l'exécution) des programmes.

Les classes de propriétés à vérifier sont très diverses comme la sûreté (par exemple, absence d'erreurs à l'exécution), la vivacité (par exemple, garantie de réponse à un signal), la sécurité (par exemple, confidentialité d'informations traitées par un programme), etc.

La grande difficulté pour démontrer automatiquement ces propriétés dynamiques est de trouver les arguments inductifs pour faire la preuve (par exemple, par induction sur le nombre de pas de calcul). Diverses solutions sont possibles : demander à l'utilisateur (méthodes déductives), utiliser un modèle finitaire (vérification exhaustive) ou calculer l'argument inductif par approximation de la sémantique du programme (en utilisant les techniques d'approximation de point fixe de l'interprétation abstraite).

Le cours explore cette dernière technique, en rappelle rapidement les bases, afin d'explorer un certain nombre d'abstractions infinitaires qui permettent de traiter un grand nombre d'applications à systèmes d'états infinis, qu'elles soient émergentes, classiques ou industrialisées

Plan du cours (à titre indicatif) :

• Introduction à l'interprétation abstraite ;

• Domaines abstraits numériques ;

• Domaines abstraits symboliques ;

• Combinaison et raffinement de domaines abstraits ;

• Conception d'un analyseur statique par interprétation abstraite ;

• Analyse statique de programmes séquentiels, procéduraux, récursifs, modularité ;

• Domaines abstraits probabilistes ;

• Vérification de la sécurité de protocoles cryptographiques ;

• Estimation de la précision de logiciels numériques ;

• Analyse statique de programmes parallèles asynchrones ;

• Analyse statique de programmes distribués ;

• Analyse statique de code mobile ;

• Vérification de systèmes complexes intégrés sur puces ;

• Vérification par abstraction paramétrée de prédicats ;

• Vérifications statiques sur des logiciels critiques embarqués temps-réel ;

• Sujets pratiques et théoriques ouverts en analyse statique par interprétation abstraite, perspectives.

Bibliographie :

• B. Blanchet, P. Cousot, R. Cousot, J. Feret, L. Mauborgne, A. Miné, D. Monniaux, X. Rival. A static analyzer for large safety-critical software. PLDI 2003, ACM Press, 2003, pp. 196-207.

• P. Cousot. Semantic foundations of program analysis. In S.S. Muchnick and N.D. Jones, editors, Program Flow Analysis: Theory and Applications, chapter 10, pages 303-342. Prentice-Hall, Inc., Englewood Cliffs, New Jersey, usa, 1981.

• P. Cousot. Verification by Abstract Interpretation. In International symposium on verification (theory & practice) celebrating Zohar Manna's 1000000 2 -th birthday, N. Dershowitz (Ed.), vol. 2472 of Lecture Notes in Computer Science, Springer, Berlin, 2003.

• J. Feret. Dependency Analysis of Mobile Systems. In <em>European Symposium on Programming</em> (ESOP'02). D. Le Métayer (Ed.), vol. 2305 of Lecture Notes in Computer Science, pp. 314--330, Springer, Berlin, 2002.

• A. Miné. A Few Graph-Based Relational Numerical Abstract Domains. In <em>Static Analysis Symposium</em> SAS'02, M. Hermenegildo and G. Puebla (Eds.), LNCS 2477, 117--132, Springer 2002.

(Cours MPRI 2-6 : 6 ECTS)

Introduction à la vision artificielle

(Jean Ponce)

Ce cours présente les principes et les fondations techniques de la vision artificielle, un domaine scientifique dont le but est de doter les ordinateurs de la capacité d'interpréter le contenu des images

Le cours comprend des exercices de programmation en Matlab/Scilab.

Plan :

1. Formation des images : Modèles des appareils de prise de vue, de la lumière et de la couleur.

2. Traitement d'image local : Filtres, détection de contours, caractéristiques visuelles, texture.

3. Groupes de pixels : Méthodes de "clustering", régression, et segmentation.

4. Plusieurs images : Géométrie multi images, stéréo, analyse du mouvement.

5. Analyse de scène : Détection et reconnaissance de visages, sacs de caractéristiques visuelles pour la reconnaissance de catégories d'objets.

Bibliographie :

D.A. Forsyth et J. Ponce, "Computer Vision: A Modern Approach", Prentice-Hall, 2002.

(Cours Info : 4 ECTS)

Langages de programmation et compilation

(Jean-Christophe Filliâtre)

Ce cours présente les principaux concepts des langages de programmation au travers de l'étude de leur compilation, c'est-à-dire de leur traduction vers le langage machine. Les TDs ont pour objectif de programmer certaines des notions vues en cours. L'évaluation comprend un projet consistant en la réalisation d'un petit compilateur.

• Mise à niveau Caml

• Principes de la compilation / Architecture MIPS

• Syntaxe abstraite / Sémantique / Interprète

• Analyse sémantique

• Typage monomorphe

• Polymorphisme / algorithme W

• Propriétés d'un système de types

• Analyse lexicale et syntaxique

• Compilation des langages impératifs

• Tableaux d'activation

• Mode de passage des paramètres

• Compilation des langages fonctionnels

• Fonctions comme valeurs de première classe

• Compilation du filtrage

• Compilation des langages à objets

• Typage statique et typage dynamique

• Représentation des objets et exécution

• Glaneurs de cellules (GC)

• Production de code efficace

• Langages intermédiaires RTL, ERTL, LTL

• Allocation de registres

(Cours Info :6 ECTS)

Pour plus de renseignements sur ce cours, consulter  : http://www.lri.fr/~filliatr/ens/compil/

Langages formels, calculabilité et complexité

(Eugène Asarin)

1: Langages réguliers, leurs propriétés et leur caractérisation par automates, expressions régulières, formules logiques, monoïdes. Langages sans étoile.

Premières notions sur les langages de mots infinis.

2: Grammaires et hiérarchie de Chomski. Langages hors contexte, leurs propriétés, leur caractérisation par automates à  pile

3: Calculabilité (fonctions récursives et Machines de Turing). Problèmes décidables, indécidables, semi-décidables.

4: Complexité en temps et espaces. Bornes de complexité. Classes de complexité (NP, Pspace) et problèmes complets.

(Cours Info : 6  ECTS)

Page du  cours 2011-2012  de M Asarin  sur  : http://www.liafa.jussieu.fr/~asarin/ENS/lf.html

Livre support du cours  : http://www.liafa.jussieu.fr/~carton/Lfcc/

Page du TD de Anne Bouillard  :  http://www.di.ens.fr/~bouillar/enseignement.html

Ancienne page du cours  : http://www.liafa.jussieu.fr/~carton/Enseignement/Complexite/ENS/

Logique

(Martin Hils)

1. Théorie naïve des ensembles

• Théorème de Cantor-Bernstein

• Ordinaux et cardinaux

• Les différentes formes de l'axiome du choix

2. Théorie des modèles

• Langages, structures, formules, théories, modèles

• Théorèmes de complétude et de compacité

• Théorèmes de Löwenheim-Skolem

• Critères d'élimination des quantificateurs

• Une application à l'algèbre : Théorème d'Ax sur les fonctions polynomiales injectives.

3. Récursivité, indécidabilité, incomplétude

• Fonctions récursives

• Arithmétique de Peano, indécidabilité de l'arithmétique

• Théorèmes d'incomplétude de Gödel.

4. Retour à la théorie des ensembles

• Les axiomes de Zermelo-Frankel

• Modèles de la théorie des ensembles et hypothèse du continu

(Cours de Maths :12 ECTS)

Voir la page de ce cours  : http://www.math.ens.fr/enseignement/fiche_cours.html?cours=4

Logique et informatique

(Jean Goubault-Larrecq) 

Ce cours explore les bases du lambda-calcul, un outil inventé par le logicien Alonzo Church dans les années 1930 et qui est aujourd'hui fondamental tant en sémantique des langages de programmation (informatique) qu'en théorie de la preuve (logique).

1. Aspects informatiques:

• Lambda-calcul, langages fonctionnels, sémantique opérationnelle (réduction).

• Expressivité. Combinateurs de point fixe et récursion.

• Terminaison, développements finis, confluence et réductions parallèles.

• Stratégies de réduction: par nom, par nécessité. Standardisation.

• Modèles du lambda-calcul, Pw.

• Calculs à substitutions explicites, machines.

2. Aspects logiques :

• Lambda-calcul simplement typé;

• Correspondance de Curry-Howard entre ce dernier et les preuves en logique minimale propositionnelle;

• Extension à la logique classique, captures de continuations et gestion d'exceptions;

• Arithmétique, le système T;

• Lambda-calcul typé du second ordre : le système F de Girard-Reynolds, correspondance avec la logique intuitionniste d'ordre deux;

• Propriétés de normalisation forte, élimination des détours.

Bibliographie :

• Henk Barendregt. The lambda-calculus, its syntax and semantics. North-Holland, 1984.

• Jean-Louis Krivine. Lambda-calcul, types et modèles. Masson, 1992.

• Jean-Yves Girard, Yves Lafont & Paul Taylor. Proofs and Types. Cambridge University Press 1989.

(Cours Info :6 ECTS)

Plus de renseignements sur ce cours sur :  http://www.lsv.ens-cachan.fr/~goubault/Lambda/loginfoindex.html

Méthodes mathématiques pour les neurosciences

(Olivier Faugeras, Grégory Faye, Jonathan Touboul)

Nous présentons dans ce cours quelques problèmes importants  de modélisation en neurosciences. Ces problèmes nécessitent pour les aborder des outils mathématiques issus de l'analyse fonctionnelle, de la théorie des systèmes dynamiques et du calcul stochastique. Les prérequis sont une bonne connaissance du calcul différentiel et du calcul des probabilités dans le cadre de la théorie de la mesure. Sans trahir la rigueur mathématique, le cours s'efforcera de mettre en valeur l'applicabilité aux neurosciences des concepts présentés.

• Modèles mésoscopiques de certaines structures corticales
        ** Structure anatomique du cortex visuel (aire V1)
        ** Architecture fonctionnelle de V1
        ** Modèles de champs neuronaux
  

• Introduction à la théorie des bifurcations
       ** Dimension 1 (noeud-selle, transcritique, fourche)
       ** Dimension 2 (Hopf)
       ** Variété centrale
       ** Formes normales
       ** Bifurcations équivariantes
  

• Applications : sensibilité à l'orientation des contours visuels, formation de structures corticales et hallucinations visuelles
       ** Le ``ring model'' de perception des orientations des contours visuels
       ** Mécanisme de Turing pour la formation des structures corticales
       ** Modèle de Bressloff-Cowan-Golubitsky pour les hallucinations visuelles
  

• Modèles de neurones
       ** Le modèle de Hodgkin-Huxley sans espace
       ** Modèles simplifiés
       ** Modèles de synapses
       ** Modèles spatiaux

•  Le rôle du bruit
       ** Mouvement Brownien
       ** Équations différentielles stochastiques
       ** Application aux neurones
  

•  Modèles de champ moyen
      ** La théorie de Sompolinsky-Ben Arous-Guionnet des verres de spin
      ** Application aux modèles de neurones à taux de décharge
      ** La théorie de McKean-Tanaka-Sznitman de particules en interaction
      ** Application aux modèles de neurones à potentiels d'action
      ** Application aux masses neurales
  

La page web du cours se trouve(ra) à l'adresse http://www-sop.inria.fr/members/Olivier.Faugeras/MVA/MMN11
L'ancienne se trouve à l'adresse http://www-sop.inria.fr/members/Olivier.Faugeras/MVA/MMN10

Bibliographie :

• Wulfram Gerstner et W. Kistler, Spiking neuron models, Cambridge University Press, 2002.

• Yuri A. Kuznetsov, Elements of applied bifurcation theory.

• Euge ne Izhikevich, Dynamical systems in neuroscience: the geometry of excitability and bursting, MIT Press, 2006.

• Jean-Pierre Françoise, Oscillations en biologie, Springer, 2000.

• Lawrence C. Evans, An introduction to stochastic differential equations, http://math.berkeley.edu/~evans/SDE.course.pdf

• Jean-François Le Gall, Mouvement brownien et calcul stochastique, http://www.dma.ens.fr/~legall/DEA96.pdf

•      G. Bard Ermentrout et D. H. Terman, Mathematical Foundations of Neuroscience
  

Planification de mouvement en robotique et en animation graphique : du continu au combinatoire via la commandabilité des sytèmes

(Jean-Paul Laumond)

La planification de mouvement s'intéresse au calcul automatique de chemins sans collision pour un système mécanique (robot mobile, bras manipulateur, personnage animé...) évoluant dans un environnement encombré d'obstacles. Les méthodes consistent à explorer l'espace des configurations du système : une configuration regroupe l'ensemble des paramètres permettant de localiser le système dans son environnement. Aux obstacles de l'environnement correspondent des domaines à éviter dans l'espace des configurations. La planification de mouvement pour le système mécanique se trouve ainsi ramenée au problème de la planification de mouvement d'un point dans une variété non simplement connexe.

• Introduction : le mouvement en Robotique, en CAO et en Animation Graphique.

• Modélisation du problème de la planification de mouvement

  • L'espace des configurations par l'exemple : trois méthodes de résolution du problème de déplacement d'un polygone en translation.

  • L'apport de la géométrie algébrique réelle : le problème est décidable.

  • L'apport de la topologie algébrique pour le mouvement au contact.

• Les grandes méthodes de résolution

  • Décomposition cellulaire. Exemple du mouvement coordonné de deux disques.

  • Rétraction. Exemple du problème de la manipulation d'objets.

• Les systèmes non holonomes

  • Eléments de géométrie différentielle. Commandabilité. Degré de non holonomie.

  • Chemins optimaux pour robots mobiles de type voiture. La planification de mouvement par algorithme d'approximation de chemins holonomes. Complexité.

  • Systèmes chaînés et commandes sinusoïdales. Systèmes plats et approche géométrique.

  • Un cas d'étude complet : planification et exécution de mouvements pour un chariot à remorque.

• Les nouvelles méthodes par recherche aléatoire.

Bibliographie :

• J.T. Schwarzt, M. Sharir and J. Hopcroft (Eds), Planning, Geometry and Complexity of Robot Motion, Ablex Series in Artificial I ntelligence, Ablex Publishing, 1987.

• J.C. Latombe, Robot Motion Planning Kluwer Academic Publishers, 1991.

• J.P. Laumond (Ed), Robot Motion Planning and Control, Lectures Notes in Control and Information Science, 229, Springer Verlag, 1998 (épuisé mais disponible gratuitement sur http://www.laas.fr/~jpl ).

Protocoles cryptographiques: preuves formelles et calculatoires

(Bruno Blanchet et Stéphanie Delaune)

Les protocoles cryptographiques sont des programmes distribués qui visent à sécuriser des communications et transactions en utilisant des primitives cryptographiques. La conception des protocoles cryptographiques est difficile: de nombreuses erreurs ont été découvertes dans des protocoles après leur publication. Il est donc particulièrement important de pouvoir obtenir des preuves que ces protocoles sont sûrs.

Deux modèles des protocoles ont été considérés : le modèle symbolique et le modèle calculatoire. Nous présenterons ces deux modèles, les techniques de preuves associées, et des résultats qui font le lien entre eux. Nous considérerons aussi leur mise en oeuvre, en montrant un outil de preuve automatique pour chaque modèle, et en les appliquant à la vérification de programmes qui implémentent des protocoles cryptographiques.

Ce cours sera l'occasion d'adapter et d'utiliser des outils formels, comme les calculs de processus, la sémantique, le typage et la logique, au cas particulier de l'étude des protocoles cryptographiques.

1. Modèles des protocoles et des propriétés de sécurité

• a. Exemples (informels) de protocoles et de propriétés de sécurité.

• b. Formalisations des protocoles; exemples d'interprétations: calculatoire et symbolique.

• c. Introduction à un fragment du pi-calcul appliqué; exemples de formalisation de protocoles.

• d. Exemples de primitives cryptographiques; formalisation de leurs propriétés algébriques.

• e. Propriétés de sécurité : secret, authenticité, attaques par devinette, propriétés d'indistinguabilité.

Exercices: modélisation en pi-calcul appliqué, recherche d'attaques simples.

2. Preuves de protocoles dans le modèle symbolique

• a. Problème de déductibilité : le cas d'un attaquant passif. Le problème est complet pour PTIME pour les systèmes locaux.

• b. Indécidabilité de la sécurité dans le cas d'un attaquant actif.

• c. Cas d'un nombre borné de sessions. Contraintes de déductibilité et algorithmes de décision pour les propriétés de traces.

• d. Résultats de combinaison; modularité de la sécurité pour certaines classes de protocoles.

• e. Algorithmes de décision pour l'équivalence statique.

Exercices : Extension à d'autres primitives cryptographiques (les résultats ne sont présentés dans le cours que sur un exemple.

3. Liens entre les modèles calculatoire et symbolique

• a. Full abstraction de l'équivalence statique: le théorème d'Abadi & Rogaway.

• b. Exemples d'extensions à d'autres primitives, avec d'autres hypothèses; attaquant adaptatif.

• c. Énoncé des résultats dans le cas actif: trace mapping et full abstraction de l'équivalence observationnelle.

Exercices : Voir [8]: les pièges et les limites de la méthode. Aussi: des exemples d'attaque calculatoire sur des protocoles prouvés sûrs (dans le monde symbolique), montrant que les diverses hypothèses sont nécessaires.

4. Preuves dans le modèle calculatoire

• a. Indistinguabilité et accessibilité dans le modèle calculatoire; sécurité sémantique, non-malléabilité, relations.

• b. Sécurité prouvée calculatoire : approche directe; hypothèses algorithmiques, preuves par réduction, techniques classiques (hybrides, rembobinage etc...)

• c.Sécurité prouvée calculatoire: approche par jeux; méthodologie générale, exemples, interprétation de résultats

• d. Sécurité des protocoles interactifs (fonctionnalité idéale); méthodologie, illustration sur la mise en accord de clé authentifiée.

Exercices : réductions entre hypothèses algorithmiques, notions de sécurité, primitives simples. Analyse de sécurité de primitives.

5. Automatisation des preuves de protocoles

• a.Dans le modèle symbolique: outil ProVerif

• Formalisation en clauses de Horn; le démonstrateur ProVerif.
• Bi-processus et formalisation des propriétés d'équivalence.

• b.Dans le modèle calculatoire: outil CryptoVerif

• Automatisation des preuves par jeux; survol de la méthode, calcul de processus utilisé pour représenter les jeux, transformation de jeux (transformations syntaxiques et transformations provenant d'hypothèses calculatoires), preuves de propriétés sur le jeu final.
• Introduction et démonstration de l'outil CryptoVerif.

Exercices : Modélisation en clauses de Horn de protocoles et utilisation de Proverif sur des exemples concrets. Manipulation de CryptoVerif.

Pré-requis  : Pas de pré-requis particulier, mais on s'appuiera sur les pré-requis généraux du MPRI (sémantique, logique, typage, ...).

(Cours MPRI 2-30 : 6 ECTS)

Bibliographie  et plus de renseignements sur :  http://mpri.master.univ-paris7.fr/

Reconnaissance d'objets et vision artificielle

(Jean Ponce, Ivan Laptev, Josef Sivic, Cordelia Schmid)

La reconnaissance automatique des objets --et de manière plus générale, l'interprétation de la scène-- figurant dans une photographie ou une vidéo est le plus grand défi de la vision artificielle. Ce cours présente les modèles d'images, d'objets, et de scènes, ainsi que les méthodes et algorithmes utilisés aujourd'hui pour affronter ce défi.

Plan du cours :

- Caractéristiques visuelles : points d'intérêt, régions affines, invariants, descripteurs Sift.

- Détection d'objets et de classes spécifiques : alignement 2D et 3D, méthodes de votes, détection de visages et Adaboost.

- Classification d'images : sacs de caractéristiques visuelles et machines à vecteurs de support, grilles et pyramides, réseaux convolutionnels.

- Détection de catégories d'objets : constellations de caractéristiques visuelles, assemblages de fragments, méthodes de fenêtre glissantes, apprentissage faiblement supervisé de modèles.

- Aller plus loin : analyse de scène, analyse des activités dans les vidéos.

Bibliographie :

• D.A. Forsyth and J. Ponce, ``Computer Vision: A Modern Approach'',Prentice-Hall, 2003.

• J. Ponce, M. Hebert, C. Schmid, and A. Zisserman, ``Toward Category-Level Object Recognition'', Lecture Notes in Computer Science 4170, Springer-Verlag, 2007.

Réseaux de Communication

(François Baccelli, Anne Bouillard, Anna Busic)

Ce cours est une introduction aux réseaux de communication qui consiste en
1. Un ensemble de lectures ;

2. Un cours sur les bases de la simulation à événements discrets ;

3. La réalisation d’un simulateur à événements discrets et l’étude d’un réseau sur la base de ce simulateur.

 I.  Lectures. Les lectures sont centrées sur les thèmes suivants:

 • Accès multiple dans les réseaux locaux (Livre: Multiple Access Protocols, R. Rom et M. Sidi, Springer, 1990).

– Réseaux fixes: Aloha, Ethernet, Protocoles en arbres, TDMA, CSMA ;

– Réseaux sans fils: 802.11, Aloha spatial ;

– Stabilité et instabilité ; Maximisation des débits.

 • Contrôle de congestion (Livre: An Engineering Approach to Computer Networking, Addison-Wesley, 1997.)

 – TCP et ses variantes (Reno, Tahoe, Vegas) ;

 – Représentation par des problèmes d’optimisation ; allocations max-min fair, proportional fair.

 • Routage dans les réseaux IP (Livre: An Engineering Approach to Computer Networking, Addison-Wesley, 1997.)

– Routage IP et algorithme de Dijkstra ;

– BGP ;

– Routage dans les réseaux ad hoc.

II.  Cours d’introduction à la simulation des réseaux. Le cours abordera les questions suivantes

 • Génération de variables aléatoires ;

 • Schémas de Matthes, tables d’événements et simulation à événements discrets ;

 • Intervalles de confiance ;

 • Simulation parfaite.

 III.  Projets. Une liste de projets de simulation sera proposée. Voici quelques exemples: instabilité des réseaux multiclasse ; simulation parfaite de réseaux CSMA ; interaction de flots TCP ; routage opportuniste dans les réseaux ad hoc ; diffusion épidémique dans les réseaux pair à pair ;  réseaux  mobiles aléatoires.

Prérequis. Avoir suivi un premier cours de probabilités.

(Cours Info :6 ECTS)

Statistique

(Gérard Biau)

Objectifs : Ce cours vise à donner aux étudiants les bases fondamentales du raisonnement et de la modélisation statistique. L'accent est particulièrement mis dans cet enseignement sur l'utilisation pratique des nouveaux objets rencontrés.

Prérequis : Une bonne connaissance du calcul des probabilités et de l'algèbre linéaire.

Thèmes abordés :

- Rappels de probabilités, estimation ponctuelle, estimation par intervalles, tests.

- Estimateurs par maximum de vraisemblance.

- Modèle linéaire : estimation, intervalles de confiance et tests.

- Modèles exponentiels, exhaustivité.

(Cours de Maths : 12 ECTS)

Voir la page de ce cours  : http://www.math.ens.fr/enseignement/fiche_cours.html?cours=15

Structures et Algoritmes Aléatoires

(François Baccelli, Pierre Brémaud)

• Variables discrètes, fonction génératrice, simulation de structures aléatoires, évaluation probabiliste d'algorithmes.

• Vecteurs aléatoires avec une densité, fonction caractéristique, simulation.

• Loi forte des grands nombres, grandes déviations et théorème central limite.

• Chaînes de Markov à temps discret, méthode de Monte Carlo, simulation parfaite.

• Simulation à événements discrets.

• Processus ponctuels de Poisson et objets géométriques aléatoires.

• Champs de Gibbs, recuit simulé.

• Graphes aléatoires.

Système digital : de l'algorithme au circuit

(Jean Vuillemin)

Le cours théorique présente la composante matérielle du monde informatique. Des principes de conception et de réalisation des circuits, à diverses applications du calcul numérique haute performance : en physique,  électronique, algèbre et télécommunication. Chaque application va de l’algorithme (logiciel) au circuit (matériel) : mêmes opérations, autres performances.

La partie pratique du cours est un projet, à réaliser par groupes : chaque groupe doit entièrement concevoir un microprocesseur, et le réaliser au moyen de portes logiques élémentaires ;  il faut ensuite simuler  les  portes en fonctionnement, et programmer le microprocesseur pour en faire une montre numérique, simulée en temps-réel.

1.      Circuit digital  synchrone : Circuit combinatoire et portes logiques. Registre et circuit digital synchrone. Réalisation d’un circuit de montre numérique. Complexité et synthèse BDD de circuits.

2.      Nombres binaires : des bits aux entiers 2-adiques ; algèbre et anneau de Boole ; hyper-cube et ensembles d’entiers. Arithmétique 2-adique et circuits en séries. Opérations logiques et ensemblistes sur les entiers : algèbre binaire.

3.      Circuits électroniques : des portes aux transistors ; de la logique à son dessin sur silicium. Schémas électriques et dessin au micron d'un additionneur série.  Mémoires ROM et RAM. Technologies de fabrication : ASIC, FPGA. Lois de Moore.

4.      Arithmétique sur silicium : additionneurs et multiplicateurs, en série et en parallèle ; profondeur minimale. Compromis optimaux entre surface et temps. Unité arithmétique et logique. Division par les poids faibles ; racine 2-adique.

5.      Machines universelles : machine de Turing sur silicium. Microprocesseur programmable à la Church.  Nombre réel calculable, et limites du calcul automatique. Arithmétiques en ligne : réels vs. 2-adiques. Logique programmable FPGA et systèmes dynamiquement reconfigurables.

6.      Physique numérique : algorithme (transformée de Hough rapide) et réalisation d’un circuit d’identification  de lignes droites dans des images digitales haute fréquences du détecteur ATLAS du LHC ; principe et réalisation d’un circuit pour connaitre les flux thermiques d’un microprocesseur en marche, par résolution numérique massivement parallèle de l’équation de la chaleur.

7.      Télécommunications : introduction à la théorie de Shannon, source et canal ; entropie des données, algorithme de Huffman, compression LZW. Contrôle des erreurs ; entropie du bruit ; code de Hamming ; code de Viterbi.

8.      Audio et vidéo : convertisseurs A/D et D/A ; compromis vitesse/résolution. Saisie, codage et transmission des images ; compression sans perte visible à l'œil : images fixes JPEG et séquences vidéo MPEG. Codage MP3 et transmission du son.  

(Cours Info : 6 ECTS)

Pour plus de renseignements sur ce cours, consulter : http://www.di.ens.fr/~jv/HomePage/teaching.html

Systèmes et réseaux

(Marc Pouzet)

Le cours de systèmes  présente les concepts fondamentaux des systèmes d'exploitation, leur utilisation et leur mise en œuvre dans un système UNIX.

Ce cours abordera, en autres, les points suivants :

 - système de fichiers;

- gestion des processus;

- mémoire virtuelle;

- communication et synchronisation entre processus concurrents (mémoire partagée,  signaux, sémaphores, sockets);

- ordonnancement préemptif et non-préemptif; OS temps réel;

- modèles de concurrence de haut niveau.

Les notions introduites seront illustrées par l'écriture d'applications en C ou en Ocaml, en utilisant l'interface POSIX.

(Cours Info : 6 ECTS)

La page du cours : http://www.di.ens.fr/~pouzet/cours/systeme/

Systèmes synchrones

(Marc Pouzet, Jean Vuillemin)

Les langages synchrones ont été crés pour programmer les systèmes réactifs embarqués à la fois très complexes et très sûrs. Ils ont connu, depuis, un succès industriel majeur dans la programmation de systèmes critiques: avions, trains, automobiles, centrales électriques, etc. Le système de commande de vol des Airbus, par exemple, est développé avec l'outil SCADE issu du langage synchrone Lustre.

Ces langages ont évolué sans cesse depuis pour traiter des applications et domaines nouveaux: calcul vidéo intensif (TVHD); grandes simulations (réseaux électriques, réseaux de capteurs); systèmes mixtes continu/discrets (environnement physique, interface analogique/discret en électronique).

Ils sont fondés sur un modèle original dit du parallélisme synchrone qui combine parallélisme et déterminisme. Le programme est décrit dans un langage parallèle de haut niveau mais pour lequel le compilateur garantit des propriété de sûreté fortes: sémantique déterministe, absence de blocage (deadlock), génération de code séquentiel s'exécutant en temps et mémoire bornés, etc. En somme, les langages synchrones permettent de programmer dans un formalisme de haut niveau, le code final embarqué étant produit directement par le compilateur.

Le cours donne une introduction au modèle synchrone et aux principaux langages qui en sont issus. Il présente leurs fondements sémantiques et logiques, les techniques de compilation vers du logiciel et des circuits, leur vérification formelle (par model-checking) et certains travaux de recherche récents. Nous montrerons dans ce cours les liens étroits entre la théorie des langages synchrones et la théorie des langages fonctionnels typés.

Pas de prérequis mais il est recommandé d'avoir suivi les cours de M1 "compilation" et "sémantique des langages de programmation"

Pour plus de renseignements sur ce cours, consulter sa page sur le site du MPRI :  http://mpri.master.univ-paris7.fr/

Théorie de l'information et codage

(Marc Lelarge)

- Notions de base :
Entropie, information mutuelle, suites typiques, inégalité de Fano.

- Compression de données :
Codage de source, inégalité de Kraft, codages de Huffman, Ziv-Lempel, théorie de la distorsion.

- Capacité d'un canal :
Théorème de Shannon.

- Codes correcteurs d'erreur :
codes linéaires, codes cycliques, codes de Hamming, BCH, Reed-Solomon.

Bibliographie :

- R.J. McEliece, The Theory of Information and Coding, 1982.

- T. Cover, J. Thomas, Elements of Information Theory, Wiley, 1991.

- C. Shannon, A Mathematical Theory of Communication, 1948.

- http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf

Plus de renseignements sur  :  http://www.di.ens.fr/~lelarge/

(Cours Info : 6 ECTS)

1 L'intégration d'étudiants français ou étrangers peut aussi s'envisager en deuxième année de scolarité, c'est-à-dire à l'entrée du master : le diplôme de l'ENS est alors délivré au terme des deux années du master (M1 et M2).