| [M1 QDCS] Advanced C++ programming |
|---|
| Coordinator : Joël Falcou |
| This module aims to provide an advanced understanding of the C++ language and associated software development techniques. The focus will be on the modern version of the language (C++14/17) and its implications on the usual software engineering techniques: meta-programming, functional programming, advanced object model. |
| Prerequisites: Algorithmics, basic knowledge of C or C++ |
| Language : English |
| [M1 QDCS] Object-oriented programming |
| Coordinator : Patrick Amar |
| The objective of the course is to deepen the knowledge of software design and programming in an object-oriented language through the study of abstract data structures and the C++ language.
The course will cover the following topics, among others: - Multiple derivation, genericity (class patterns), memory management. - Standard library of generic classes (stl): lists, queues, hash tables, vectors, etc. - The practical part, in the form of a supervised project, allows students to design a software package in which the knowledge acquired in the other modules is put to use: mainly graph theory, artificial intelligence and computer graphics. |
| Prerequisites: Bachelor level programming and algorithms. |
| Language : English |
| [M2 QDCS] Distributed computing with mobile agents |
| Coordinator : Evangelos Bampas |
|
The mobile agent paradigm has been proposed since the 90s as a concept that facilitates various fundamental networking tasks, such as fault tolerance, network management, and data acquisition. Mobile agents serve as a natural model for the fundamental computing entities of systems with inherent mobility (mobile code, malware propagation, web crawlers, etc.) and, as such, they have found application as a software design paradigm for various networked systems. A second perspective on the mobile agent paradigm is as a model for robots that operate and move in continuous spaces, with typical applications in the fields of artificial intelligence, robotics, and control. The distributed algorithms community has taken a strong interest both in software agents and in robots, developing a rich literature and an active research field. After presenting the two main model categories of robots (Look-Compute-Move) and of software agents, we will treat the fundamental algorithmic problems of the field, such as pattern formation by groups of robots, gathering, rendez-vous, exploration, and the detection of dangerous nodes in a network. The unifying theme of the course is the design and analysis of algorithms which will allow the agents to collaborate and solve problems, despite their limited communication capabilities, their limited knowledge of the domain in which they move, and, in some cases, the asynchronicity of the system or the presence of faults. |
| Prerequisites: Basic notions of algorithms, graph algorithms and complexity |
| Language : English |
| [M2 QDCS] GPU programming |
| Coordinator : Oguz Kaya |
| The computational power of graphics processing units (GPU) have revolutionized artificial intelligence, data science, and scientific computing as they enable the solution of real-world problems at an unprecedented scale. This course aims to give a deep understanding of parallel programming tools and principles for getting the maximum performance out of GPUs. We start with the very basics of GPU programming involving the GPU architecture and single program multiple thread (SPMT) model and develop parallel programs using the concepts of warps/blocks/grids. We then discuss advanced optimization topics including shared memory, coalescing, occupancy, performance profiling, etc. |
Prerequisites:
|
| Language : English |
| [M2 QDCS] Scheduling and runtime systems |
| Coordinator : Lima Pilla Laércio |
| This module focuses on the efficient management of parallel system resources (computation, memory, network, etc.) used for scientific computing and massive data processing, as accessed through runtime systems and other software components.
The following topics will be studied during the course: - basic scheduling concepts, management of shared computational resources, - dynamic load balancing and work-stealing, - scheduling in heterogeneous computational systems, - task graph scheduling and scientific workflows, - resource management in Big Data systems. |
Prerequisites:
|
| Language : English |
| [M2 QDCS] Stochastic optimisation |
| Coordinator : Abdel Lisser |
| This course aims to present optimisation problems where decisions are made in the presence of uncertainty. These are problems where all or a subset of the parameters are represented by random variables, following probability laws that are known in advance. The course is based on the theoretical foundations of stochastic optimisation, the different models of randomness and risk as well as the associated solution methods. The interaction between stochastic optimisation and stochastic games will also be discussed. Examples of applications arising from industrial problems will be given to illustrate the different parts of the course. This module will cover the following topics: - Modelling of optimisation problems with uncertainty. - Linear stochastic two-level problems with recourse. - Multi-level linear stochastic problems with recourse. - Sampling methods and approximations. - Introduction to stochastic problems with probability constraints. - Interactions between stochastic game theory and stochastic optimization. |
| Prerequisites: Linear programming; basics of probability |
| Language : English |
| [M1 QDCS] Modeling and optimization of discrete systems |
| Coordinator : Abdel Lisser |
| A wide variety of optimisation problems are discrete in nature and can be formulated and solved using combinatorial optimisation methods, such as crew planning, power generation planning, telecommunications, and cutting problems, to name but a few. Combinatorial optimisation problems are those in which mathematical techniques are applied to find optimal solutions within a finite set of possible solutions. The set of possible solutions is usually defined by a set of constraints, and this set is too large for an exhaustive search. Well-known examples of combinatorial optimisation are the knapsack problem and the travelling salesman problem. At the end of this module, the student should be able to : - analyse and model a combinatorial optimisation problem in the form of a linear program or a graph, - apply different relaxation methods for solving combinatorial optimisation problems in order to obtain good quality bounds, - Formalise and solve a dynamic optimisation problem, - master the basics of complexity and reduction problems, - use exact separation and evaluation methods known as Branch & Bound, - mastering cutting plane algorithms |
| Prerequisites: Linear programming, basic knowledge in algorithmics and linear algebra. |
| Language : English |
| [M1 QDCS] Game, learning, and optimisation of complex systems |
| Coordinator : Abdel Lisser |
| Over the past 10 years, many important connections between optimization, game theory and learning theory have been discovered. This course will explore these links, discuss some of the fundamental topics in each area and how ideas from each area can inform each other. This module will cover the following topics: - Regret minimisation, example of bandit algorithms. - Zero sum games. Nash equilibria, the minimax theorem. - Nash equilibria in bimatrical games. - Games with several players. - Nash equilibrium and optimality conditions. - Submodularity with links to game theory and learning. |
Prerequisites:
|
| Language : English |
| [M1 QDCS] Introduction to quantum algorithms and programming |
| Coordinator : Benoît Valiron |
| The objective of this course is to understand how quantum algorithms work, analyzing their strengths and limitations. First, we will introduce the concepts behind quantum computation and study the standard computational model: circuit families and the quantum co-processor model. We will discuss the structure of quantum algorithms and the resulting programming model. We will then study the most well-known quantum algorithms: Grover, Shor, etc. Finally, we will discuss the medium-term applications of quantum computation, in particular in the context of machine learning. |
| Prerequisites: Basic knowledge in algorithmic/programming and computer architecture |
| Language : English |
| [M2 QDCS] Advanced quantum computing and error correction |
| Coordinator : Renaud Vilmart |
|
Advanced quantum computation models, such as the graphical language ZX calculus: formalism; universality; completeness; verification; optimisation; surface codes. Quantum error correcting codes: Recap of classical error-correcting codes, Hamming code, notion of generating matrices and parity. LDPC codes and iterative decoding. Reminder on Pauli operators, notion of stabilizing quantum codes, CSS codes, example of Shor and Steane codes, quantum MDS codes. Homological interpretation of CSS codes, example of the Kitaev toric code, quantum LDPC codes, decoding, Tillich-Zémor construction. The course will end with recent results on the construction of families of quantum LDPC codes of quasi-linear minimum distance. |
Prerequisites:
|
| Language : English |
| [M2 QDCS] Quantum processor simulation |
| Coordinator : Marc Baboulin |
|
In this course we introduce the linear algebra tools necessary to understand the state of the art of quantum processor simulation via a classical HPC system. We first recall the stakes surrounding quantum computing in relation to high performance computing. We provide a recap of the quantum circuit model. We will then study two complementary simulation methods, both based on tensor manipulation. We extend these techniques to approximate simulation of quantum computation, with error quantification. Finally we will present a linear algebra approach to the Clifford group representation and its application to simulation. |
Prerequisites:
|
| Language : English |
| [M1 MPRI] Foundations of quantum information |
| Coordinator : Pablo Arrighi |
In this course, we will focus on understanding the quantum nature of information, through the multiple theorems that characterize it. We will illustrate them with applications in quantum cryptography and communications, quantum error correction and quantum simulation.
The following points will be presented:
|
| Prerequisites: All of the necessary reminders will be given. However, make sure you do like linear algebra: vectors, matrices, inner product, norm. |
| Language : English |
| [M2 QDCS] Recent trends in parallel, distributed, and quantum computing |
| Coordinator : Janna Burman |
| This module aims to describe recent advances in distributed, parallel and quantum computing. Its precise content evolves over time, as it consists of seminars given by researchers and developpers at the cutting edge. The module is particularly recommended for students who want to keep abreast of current algorithmic developments and plan to continue their studies to a PhD. |
| Prerequisites: : Basic knowledge of quantum, distributed and parallel computing. |
| Language : English |
| [M1 QDCS] High performance computing |
| Coordinator : Oguz Kaya |
| The goal of this course is to acquire competence in developing fast parallel programs that are capable of exploiting modern parallel computer architectures for solving large-scale real-world problems. We first focus on parallel programming on a multi-core machine using OpenMP and discuss loop parallelization, scheduling and task-based parallelization techniques as well as atomic operations, race conditions, and false sharing. We then investigate the parallelization within a single core by using vectorization techniques and instruction level parallelism. Finally, we discuss performance issues related to the memory hierarchy and ways to improve data access. |
Prerequisites: :
|
| Language : English |
| [M1 QDCS] Self-stabilising distributed algorithms |
| Coordinator : Janna Burman |
| Self-stabilisation is a versatile technique used to overcome any transient failure in a system. The focus of this module is on distributed systems such as the Internet, networks of mobile agents or sensors, and their applications such as the Internet of Things, the Cloud, Bitcoin, etc. Failures and dynamic evolution are the norm in such systems and become more likely at large scales. This could be due to changes in the communication topology, corruptions of the volatile memory of components, etc. Such failures can put the system at an arbitrary configuration (state) at any time during an execution. However, as soon as the failures and dynamic evolutions cease, a self-stabilising algorithm brings the system to a correct operation, without resetting and without an external intervention.
In this module, after recalling the basics of distributed algorithms, we study how the self-stabilising techniques are used to make current distributed systems robust. |
| Prerequisites: : Basic notions of algorithms and complexity. |
| Language : English |
| [M1 QDCS] Parallel algorithms |
| Coordinator : Oguz Kaya |
| The goal of this course is to provide an adequate theoretical background for the design and analysis of parallel algorithms in different parallel computing environments. The course starts with the introduction of an ideal parallel machine (parallel random-access-machine, or PRAM), then focuses on designing various optimal algorithms and analyzing their complexity in this setting. Then, distributed-memory parallel architectures with different communication networks are introduced. Finally, the parallelization of many well-known fundamental algorithms are discussed. |
| Prerequisites: : Basic algorithmic skills; Programming knowledge; basic understanding of a computer architecture. |
| Language : English |
| [M1 QDCS] Robust distributed algorithms |
| Coordinator : Janna Burman |
| Distributed algorithms are the basis of distributed systems and applications, such as the Internet, the Internet of Things, the Cloud, Bitcoin, etc. In addition to the difficulties induced by the geographical distribution and the dynamical evolution of their components, these real systems are subject to failures: crashes, memory corruption, behaviour of malicious participants, etc.
In order to guarantee the correct operation of such systems, a major challenge is to know how to manage both the dynamics and its failures, which multiply with large scale deployments. This module presents a major technique using replication to tolerate a bounded number of failures, by completely masking them.
The objectives of this module are to: - give the basics of distributed algorithms, - understand the problems that arise when designing a robust distributed system and to give solutions to these problems, - address the notions of proof of distributed algorithms and complexity analysis, - make students aware of the fault tolerance aspect, - introduce the replication technique, followed by consensus. |
| Prerequisites: : Basic notions of networking, systems, algorithms and complexity. |
| Language : English |
| [M2 QDCS] Natural algorithms |
| Coordinator : Janna Burman |
| Nature has developed distributed algorithms (without centralized control), which are efficient and require little resources and energy. Traditional networking has sometimes been inspired by them. This module is devoted to the study of algorithms related, in one way or another, to natural phenomena. They are based on distributed models using processors that are very limited in resources and in computing and communication capacities.
For example, in the population protocol model, agents, whether fixed or mobile, anonymous and undistinguishable, with limited memories, interact in pairs in an unpredictable and asynchronous manner. Another example is micro-biological distributed systems, such as bacterial and viral cultures. These are again very limited systems, in which algorithms are developed to perform computations (microbiological circuits) or regulate self-administered drugs. One of the objectives of the module will be to understand how purely computational problems (aggregation, synchronisation, coordination, communication) can be solved in such models with limited resources. |
| Prerequisites: Basic notions in algorithms and complexity. |
| Language : English |
| [M1 IoT] MPI programming |
| Coordinator : Marc Baboulin |
The focus of this course is the parallel programming in distributed memory systems, with the message-passing paradigm using the MPI library.
|
Prerequisites:
|
| Language : English |