Course offerings

Detailed descriptions of the teaching units can be found at the bottom of this page.

First year

The first semester is dedicated to acquiring basic knowledge at the core of the program, and to complementing and strengthening background knowledge from undergraduate studies. It consists in:

  • two mandatory courses (COMPLEX, MODEL) which provide essential knowledge in complexity theory (decidability, complexity classes, approximation algorithms) as well as the main paradigms of mathematical algorithms (core algorithms of linear algebra, Chinese Remainder techniiques and evaluation/interpolation, arithmetic operators and Fourier transforms);
  • three courses to choose freely under the following constraints:
    • at least two among the units : PPAR, ARCHI1, NOYAU and QCLG :
      PPAR introduces fundamental concepts of parallel programming for high-performance computing (pre-requisite for second year),
      ARCHI1 introduces concepts from computer architecture;
      NOYAU studies the mechanisms of operating system kernels;
      QCLG introduces the basic concepts of quantum information/computing, which is bound to play an important role in cryptography in the near future;
    • At most one course among: BDA (Advanced Data Bases), MOGPL (Modelling, probability, statistics), PR (distributed algorithms).

Above, the course acronyms appearing in color are those whose lectures are in English (tutorial and practical sessions remain available in French).

The second semester goes deeper into the notions introduced during the first semester and introduces notions necessary towards the second year notably concerning cryptology and numerical algorithms. It consists in:

  • a mandatory Project, which is a strong component of the degree where students work in small teams on ambitious projects, all along the semester, under the supervision of a teacher-researcher from the team of instructors of this degree;
  • at least three courses among ANUM (numerical algorithms), FLAG (fundamentals of algebraic algorithms), CRYPTO1 (introduction to modern cryptology) — all these courses contain parts which are prerequisites for the second year of the degree — and ARCHI2 (architecture of kernels of multi-processor systems)
  • at most one teaching unit among ARCHI2, PNL (linux kernel programming) and SAS (system security and administration) and QIIntro (Introduction to quantum information).

Above, the course acronyms appearing in color are those whose lectures are in English (tutorial and practical sessions remain available in French).

Second year

The third semester of the degree strengthens the knowledge and skills acquired in the first year, while also preparing students to their internship and job search and work. It consists in five courses:

  • At least four among AFAE (floating-point arithmetic and rounding errors), CRYPTA (advanced cryptology), HPCA (advanced high-performance computing), POSSO (algebraic system solving and multivariate post-quantum cryptolography), and SCA (side-channel attacks). These four courses are at the core of the themes studied in this degree.
  • At most one course to choose freely among those offered in the Computer Science Master's degree of Sorbonne University.

The fourth and last semester is dedicated to a long student internship, which is conducted either in industry or in a public research laboratory. The intern has to write a report and prepare an oral presentation of the work at the end of the internship.

Descriptions of teaching units

Clicking on a unit name will show the description.

COMPLEX (Complexité, algorithmes randomisés et approchés) — CODE UE : MU4IN900
In this course, we will focus on the computational resources (essentially, the computational time) needed to solve algorithmic problems. In particular, we will try to distinguish between so-called "easy" problems, which can be solved with a reasonable amount of resources (problems whose complexity is a polynomial function of the problem size), and so-called "hard" problems, which are beyond the reach of existing computers.

We will introduce the fundamental complexity classes P and NP and define NP-completeness. Most algorithmic problems encountered in practice are "hard". We will be interested in the trade-offs and relationships between different computational "modes": what happens if we allow ourselves to use probabilistic algorithms, if we are satisfied with approximate rather than exact solutions, if we are satisfied with an algorithm that works only for most but not all possible inputs? This course will introduce techniques of approximation and randomization of algorithms that allow to circumvent the difficulty of solving hard problems, and thus allow their use in practice with reasonable computation times. These techniques will be illustrated in tutorials and in lab-projects on a range of concrete problems from the various specialties of the master.

  • Model of a computer; Turing machines.
  • Complexity classes and reductions.
  • Tree methods.
  • Approximation algorithms with performance guarantee.
  • Probabilistic algorithms (Las Vegas, Monte Carlo)
  • Probabilistic graph algorithms.
  • Probabilistic algebraic algorithms (primality tests; polynomial identity tests).
  • Probabilistic algorithms for variants of the SAT problem.
  • Probabilistic complexity classes (BPP, ZPP, RP, PP)

Evaluation: Small project (20%), Mid-term exam (40%), Final exam (40%)

MODEL (Numerical and Symbolic Algorithms Modeling) — CODE UE : MU4IN901
The course provides an introduction to fundamental linear algebra algorithms with approximate or exact computation. Classical techniques, like Gaussian elimination, least-square approximation, SVD, FFT, are studied together with dedicated methods to sparse and structured linear systems using algebraic modeling. In-depth complexity analyses of naive and more advanced algorithms are also studied.

This finds applications in many areas of computer science (cryptography, high-performance computing, big data, operational research, imagery, etc.).

  • Exact and approximate linear system solving
  • SVD and FFT
  • Complexity and non-naive multiplication algorithms for integers, polynomials and matrices
  • Reductions to matrix multiplication, structured and sparse linear system solving
  • Evaluation: Quizzes (20%), Small project (20%), Mid-term exam (30%), Final exam (30%)

PPAR (Parallel Programming) — CODE UE : MU4IN903
Large-scale computations require both a massive amount of computing hardware, which is thus necessarily parallel, and programmers with a specific training to exploit it.  This course introduces students to the industry-standard tools and techniques  used in High-Performance Computing using the C programming language. It presents message-passing programming of computer clusters using MPI libraries, multi-thread programming of multi-core CPUs using OpenMP and vectorization (the exploitation of SIMD instructions in contemporary CPUs). In addition, the courses discusses algorithmic issues in parallel programming (how to do THAT in parallel?), how low-level hardware issues (cache, paging, branch prediction, ...) affect  performance and to to maneuver around them. Finally, the course presents performance models as well as techniques to understand and anticipate the running-time of actual parallel programs.

Evaluation: two large parallelization projects (33% each), final exam (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
In this course, we study fundamental algorithms for efficient computations with algebraic objects such as matrices and polynomials which arise frequently in cryptography and high-performance computing . We tackle basic operations in finite fields, computations with polynomials and formal power series, linear algebra operations, structured linear system solving, and polynomial system solving in two variables. We conclude the course with an introduction to Reed-Solomon error correcting codes and some of their decoding algorithms. Coding theory is one of the natural fields of application of the notions studied in the course, which are at the core of computer algebra and also central in various areas of cryptology.

Evaluation : tests (30%), project (35%), final exam (35%)

CRYPTO1 (Cryptologie 1) — CODE UE : MU4IN904
This course presents the basics of modern cryptology: encryption, digital signature, etc. These techniques guarantee the confidentiality and integrity of day-to-day online communications. On the menu: symmetric ("secret key") encryption, block ciphers, overview of the AES, operating modes for encryption, cryptographic hash functions. Public key cryptography: presentation of RSA encryption and signature, discussion of large integer factorization algorithms. Introduction to the discrete logarithm problem and its applications (Elgamal encryption, DSA signature, ...). Description of the TLS and SSH protocols that combine all the above. The course concludes with a multi-week cryptanalysis sequence, including the presentation of significant attacks, notably based on the use of Euclidean networks.

Evaluation : midterm + final exam (33% each) + online practical work (33%)

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