Offre de cours

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%)

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%)

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%).

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%).

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%)

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

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.

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

Systems of polynomial equations encode a wide variety of problems in engineering and computing sciences such as robotics and cryptography since they easily encode Euclidean geometric and arithmetic properties. Their use in cryptography, for designing post-quantum encryption and signature schemes is motivated by the NP-hardness of solving systems of polynomial equations.

This course focuses on algebraic methods for solving such systems of equations with a view towards applications in post-quantum cryptography and algebraic cryptanalysis.

A first period is devoted to introduce basic notions and Buchberger-style algorithms, introducing Gröbner bases and their properties. A second period is devoted to techniques for analyzing the complexity of Gröbner basis algorithms. A third period introduces linear algebra-based Gröbner bases algorithms. The last period covers applications in post-quantum cryptography.

Exercise sessions are scheduled and computer sessions organized in order to help the student to better assimilate the contents of the course.

L’UE SCA (Side-Channel Attacks) s’intéresse à toutes les attaques par canaux auxiliaires d’implémentations d’algorithmes cryptographiques, et plus particulièrement de l’AES, qui constitue un fil rouge pour le module. Les principaux types d’attaques considérés sont les attaques par analyse de consommation et les attaques par faute. Les attaques de Timing sont également abordées en cours. L’UE accorde une place importante aux travaux pratiques (28h), qui sont complétés par 20h de cours.

Les thèmes abordés en cours sont les suivants :

– Sécurité embarquée et attaques matérielles

– Attaques par analyse de consommation

– Attaques par faute

– Attaque par analyse de timing

– Contre-mesures logicielles face aux attaques

– Évaluation de fuites secrètes

Les travaux pratiques comprennent les points suivants :

– Analyse de traces de consommation, lien entre consommation et instructions exécutées

– Attaque d’un code (récupération d’un mot de passe) par analyse simple de consommation

– Lien entre consommation et données manipulées par un programme

– Attaque de l’AES par analyse différentielle de la consommation

– Implantation d’un schéma de protection pour l’AES

– Attaques par faute sur simulateur

Evaluation : 50% pour les TPs et 50% par un examen.

Ce cours de cryptographie explore les concepts, protocoles et techniques plus avancés dans le domaine de la sécurité de l’information, en étudiant des résultats récents de cryptographie classique et post-quantique. Il présente notamment les signatures numériques et les preuves à divulgation nulle de connaissance, le calcul réparti sécurisé, les signatures fondées sur le calcul réparti sécurisé « dans la tête », la cryptanalyse fondée sur les réseaux euclidiens, des algorithmes de chiffrement par blocs et leurs techniques de cryptanalyse, et une introduction à la cryptographie post-quantique.

Volume horaire : 18h CM, 18h TD, 18h TP

Modalités d’évaluation : deux examens répartis (un « partiel » + un « final ») et une note de TP, qui comptent pour 35%, 35% et 30% respectivement. Les TME ont lieu en-ligne sur une plate-forme que nous avons développée.