Offre de cours

Des descriptifs détaillés des unités d’enseignement se trouvent en bas de page.

Première année

Le premier semestre permet d’acquérir les premières connaissances fondamentales et compléter ou renforcer ses acquis de licence. Il est composé de :

  • deux Unités d’Enseignement obligatoires (COMPLEX, MODEL) qui permettent d’acquérir les connaissances indispensables en théorie de la complexité (décidabilité, classes de complexité, algorithmes d’approximation) ainsi que les paradigmes de l’algorithmique mathématique (algorithmes fondamentaux de l’algèbre linéaire, CRT et évaluation/interpolation, opérateurs arithmétiques et transformées de Fourier);
  • trois Unités d’Enseignement à choisir librement sous les contraintes suivantes :
    • au moins deux parmi les Unités : PPAR, ARCHI1, NOYAU et QCLG :
      PPAR introduit les concepts fondamentaux de la programmation parallèle pour le calcul haute-performance (qui sont des pré-requis pour le M2),
      ARCHI1 introduit les concepts de l’architecture des ordinateurs et
      NOYAU étudie le fonctionnement des noyaux des systèmes d’exploitation;
      QCLG introduit les concepts de base de l’informatique quantique qui est amenée à jouer un rôle important en cryptographie dans les années à venir;
    • au plus une parmi les Unités : BDA (Bases de Données Avancées), MOGPL (Modélisation et probas-stats), PR (Programmation Répartie).

Les Unités apparaissant en couleur ci-dessus sont celles dont le cours est dispensé en anglais (les échanges en TD et TP peuvent se dérouler en français).

Le second semestre permet d’approfondir les notions introduites au premier semestre et d’introduire celles nécessaires à la poursuite en M2, notamment en cryptologie et en algorithmique numérique. Il est composé de :

  • une Unité d’Enseignement Projet obligatoire : il s’agit d’un temps fort de la formation où les étudiants travaillent en équipe sur un projet ambitieux, tout au long du semestre sous l’encadrement d’un enseignant-chercheur, enseignante-chercheuse, chercheuses ou chercheur de notre équipe pédagogique ;
  • au moins trois Unités d’Enseignements parmi ANUM (Algorithmique Numérique), FLAG (Fondements de l’Algorithmique Algébrique), CRYPTO1 (Introduction à la cryptologie moderne) — toutes ces unités dispensent des enseignements qui sont des pré-requis pour le deuxième année de master — ainsi que ARCHI2 (architecture des noyaux des systèmes multi-processeurs) ;
  • au plus une Unité d’Enseignement parmi ARCHI2, PNL (Programmation au coeur du noyau Linux) et SAS (Sécurité et Administration des Systèmes) et QIIntro (Introduction à l’information quantique).

Les Unités apparaissant en couleur ci-dessus sont celles dont le cours est dispensé en anglais (les échanges en TD et TP peuvent se dérouler en français).

Deuxième année

Le troisième semestre permet de renforcer les acquis de première année tout en préparant les étudiants à la recherche de stage et l’insertion professionnelle. Il est composé de cinq Unités d’Enseignements,

  • au moins quatre parmi AFAE (Arithmétique flottante et erreurs d’arrondis), CRYPTO2 (Cryptologie Avancée), HPCA (calcul haute performance avancé), POSSO (Systèmes algébriques et cryptologie multivariée post-quantique) et SCA (Attaques par Canaux Auxiliaires). Ces cinq Unités sont au coeur disciplinaire de notre formation ;
  • au plus une Unité à choisir librement parmi celles proposées dans le master d’Informatique de Sorbonne Université.

Le dernier semestre est dédié au stage que les étudiantes et étudiants peuvent réaliser dans l’industrie du numérique comme dans le monde académique. Ce stage donne lieu à la rédaction d’un rapport ainsi qu’à une soutenance orale.

Descriptif des unités d’enseignement

Cliquer sur l’UE pour afficher le descriptif.

COMPLEX (Complexité, algorithmes randomisés et approchés) — CODE UE : MU4IN900
Dans cette UE, nous nous intéresserons aux ressources de calcul (essentiellement, le temps de calcul) nécessaires pour résoudre les problèmes algorithmiques. Nous tâcherons en particulier de distinguer les problèmes dits « faciles », que l’on peut résoudre avec une quantité raisonnable de ressources (problèmes dont la complexité est une fonction polynomiale de la taille du problème), des problèmes dits « difficiles », qui sont hors de portée des ordinateurs existants.

Nous introduirons les classes de complexité fondamentales P et NP et nous définirons la NP-complétude. La plupart des problèmes algorithmiques rencontrés en pratique sont « difficiles ». Nous nous intéresserons alors aux compromis et relations entre différents « modes » de calculs : que se passe-t-il si l’on s’autorise à utiliser des algorithmes probabilistes, si l’on est satisfait de solutions approchées plutôt qu’exactes, si l’on est satisfait d’un algorithme qui marche seulement pour la plupart des entrées possibles, mais pas pour toutes ? Ce cours introduira des techniques d’algorithmes d’approximation et de randomisation permettant de contourner la difficulté de résolution des problèmes difficiles, et permettant ainsi leur application en pratique avec des temps de calcul raisonnables. Ces techniques seront illustrées en TD et en TME-projet sur un éventail de problèmes concrets relevant des diverses spécialités du master.

  • Modèle d’un ordinateur ; machines de Turing.
  • Classes de complexité et réductions.
  • Méthodes arborescentes.
  • Algorithmes approchés avec garantie de performance.
  • Algorithmes probabilistes (Las Vegas, Monte Carlo)
  • Algorithmes probabilistes de graphes.
  • Algorithmes algébriques probabilistes (Tests de primalité ; tests d’identité polynomiale).
  • Algorithmes probabilistes pour des variantes du problème SAT.
  • Classes de complexité probabiliste (BPP, ZPP, RP, PP)

Évaluation : Petit projet (20%), Examen réparti 1 (40%), Examen réparti 2 (40%)

MODEL (Numerical and Symbolic Algorithms Modeling) — CODE UE : MU4IN901
Ce cours propose une introduction aux algorithmes fondamentaux d’algèbre linéaire avec une arithmétique approchée ou exacte. Les techniques classiques, telles que l’élimination de Gauss, la méthode des moindres carrés, la SVD, la FFT sont étudiées ainsi que des méthodes dédiées aux systèmes linéaires creux ou structurés faisant appel à une modélisation algébrique. Une étude fine des analyses de complexité des algorithmes, naïfs ou plus avancés, sera aussi étudiée.

Ce cours trouve des applications dans de nombreux domaines de l’informatique (cryptographie, calcul haute performance, big data, recherche opérationnelle, imagerie, etc.)

  • Résolution de systèmes linéaire exacte ou approchée
  • SVD et FFT
  • Complexité et algorithmes non naïfs de multiplication d’entiers, de polynômes et de matrices
  • Réductions à la multiplication de matrices, résolution de systèmes linéaires structurés et creux
  • Évaluation : Quiz (20%), Petit projet (20%), Examen réparti 1 (30%), Examen réparti 2 (30%)

PPAR (Parallel Programming) — CODE UE : MU4IN903
Le calcul scientifique « haute-performance » (High-Performance Computing, HPC) nécessite à la fois une grande puissance de calcul, donc des machines massivement parallèles, et des programmeurs formés à leur utilisation. Ce cours introduit les outils et techniques « standards industriels » largement utilisés dans le calcul haute performance. Dans le langage C, il présente la programmation parallèle sur des clusters de serveurs de calculs à l’aide de bibliothèques MPI, ainsi que la programmation multithread sur les CPU multi-cœurs à l’aide d’OpenMP. Enfin, le cours présente les techniques permettant l’exploitation du parallélisme à l’intérieur d’un seul coeur (vectorisation, ‘exploitation des instructions SIMD dans les CPU contemporains). En outre, le cours aborde des problèmes algorithmiques récurrent dans la programmation parallèle et le calcul scientifique. Une attention particulière est portée à la façon dont des problèmes matériels de bas niveau (cache, pagination, prédiction de branchement, …) affectent les performances et comment les contourner. Enfin, le cours présente des modèles de performance ainsi que des techniques pour comprendre et anticiper le temps d’exécution de programmes parallèles réels.

Evaluation : deux projets conséquents (33% chacun) + examen final sur table (33%).

ANUM1 (Numerical Algorithms) — CODE UE : MU4IN910
This course is the natural continuation of the numerical part of MODEL course. It is a question of supplementing the knowledge in mathematical tools and algorithms in order to be able to solve concrete problems and of large sizes. We will study in particular algorithms and their implementation frequently used in the field of scientific computing and data science. The applications will be very diverse and may change each year: for example, we will see applications in finance (calculation of the price of options), in simulation of structures for 3D printing, in imaging (image compression), in deep learning (stochastic gradient algorithm), etc. We will endeavor for each algorithm to propose versions allowing an efficient implementation on parallel machines. The algorithms will be coded in MATLAB.

– Floating-point arithmetic and rouding error analysis

– Matrix computation

– Introduction to continuous optimization

– Interpolation and approximation

– Numerical differentiation et integration

– Monte Carlo method

Grades will be computed as follows: exam 1 (40%), exam 2 (40%), praticals (20%).

FLAG (Fondements de l’algorithmique algébrique) — CODE UE : MU4IN902
Dans cette unité d’enseignement, nous étudions des algorithmes fondamentaux pour calculer efficacement avec des objets algébriques (matrices, polynômes) qui sont apparaissent fréquemment en cryptographie et calcul haute-performance. Il s’agit d’aborder les opérations de base dans les corps finis, les calculs avec les polynômes et séries formelles, les opérations d’algèbre linéaire, la résolution de systèmes linéaires structurés, et la résolution de systèmes polynomiaux à deux variables. Nous finissons avec une introduction aux codes correcteurs d’erreurs de Reed-Solomon et certains de leurs algorithmes de décodage. La théorie des codes correcteurs forme une des applications naturelles des notions vues dans cette unité d’enseignement. Au coeur du calcul formel, ces notions sont également fortement utilisées dans diverses branches de la cryptologie.

Évaluation : tests (30%), projet (35%), examen final (35%)

CRYPTO1 (Cryptologie 1) — CODE UE : MU4IN904
Ce cours présente les bases de la cryptologie moderne, c’est-à-dire les techniques de chiffrement, de signature numérique, etc. permettant entre autre de garantir la confidentialité et l’integrité des communications. Au menu : chiffrement symétrique (« à clef secrète »), systèmes de chiffrement par bloc, survol de l’AES, modes opératoires pour le chiffrement, fonctions de hachage cryptographiques. Cryptographie à clef publique : présentation du chiffrement et de la signature RSA, discussion des algorithmes de factorisation des grands entiers. Introduction au problème du logarithme discret et à ses applications (chiffrement Elgamal, signature DSA, …). Le cours se conclut par une séquence de cryptanalyse, avec la présentation d’attaques marquantes, notamment basées sur l’utilisation des réseaux euclidiens.

Evaluation : partiel (33%) + examen final (33%) + un TP géant qui dure tout le semestre

AFAE (Floating-point arithmetic and error analysis) — CODE UE : MU5IN950
This course is at the intersection of algorithmic and mathematics. One of the goals is to master the concepts related to rounding errors and their consequences as well as learning how to perform an analysis of the numerical quality of scientific code. We will present the floating-point arithmetic (IEEE 754 standard) and its consequences for numerical results of scientific computing codes as well as theory and practice of methods of estimating or increasing the accuracy of computed results in general using in particular interval arithmetic, discrete stochastic arithmetic and compensated methods. A presentation of the theory for computing elementary functions will also be proposed.

HPCA (Advanced high-performance computing and programming many core architectures)
Two thirds of this course are dedicated to CUDA programming (Part I). One third of this course is dedicated to large problems solving with multi-node architecture (Part II).

This Part I introduces GPU programming using CUDA API and then provides a large number of examples that will make the reader more and more comfortable with the hardware and the API used. The purpose is to give the technical background that opens scaling up applications to a large public of students, researchers, and engineers.

Modern computers have an increasing number of computing units. To take advantage of this parallelism, it is therefore necessary to use and implement algorithms with a high level of concurrency. In this Part II, different techniques for solving hollow linear systems that benefit from such a feature are presented. In particular, domain decomposition methods and multigrid methods that have an optimal asymptotic cost are detailed.

Here is a link to the detailed syllabus