| [MPRI] Langages de programmation et de compilation |
|---|
| Coordinator : Thibaut Balabonski |
|
Learning Objectives: Deconstruct the mechanisms of high-level programming languages in terms of elementary operations. Become familiar with symbolic manipulation of programs for interpretation, analysis, or translation purposes.
Description: This course addresses the core of the compilation process, namely the translation of high-level programs into more elementary programs. The starting point will be the structured representation of the program obtained after the syntactic analysis. The end point will be a directly executable program, for example in assembly language. The course also presents techniques for program analysis and optimization, and discusses the relevant aspects of architecture and systems.
Topics include: - Control structures; - Functions; - Data types and structures - Functional programming; - Object-oriented programming; - Memory management - Register allocation. The course leaves a large part to programming in the OCaml language. The practical classes incrementally lead to the construction of a compiler for a realistic language. |
| Prerequisite: Syntactic analysis, general culture of programming languages, OCaml programming. |
| Language : French |
| [MPRI] Lambda-calculus |
| Coordinator: Thibaut Balabonski |
| Learning objectives : To learn the theoretical tools to formalize and understand the behaviour of programs, through the lambda-calculus in particular (a function-based computational model that lies at the core of functional programming languages) and its different semantics. Description: This course presents the lambda-calculus, a formalism describing the notion of a computable function in the same way as Turing machines do. It goes on to explain how this formalism and its variants can be used to formally describe the behavior of programs. We will present the notions of large-step semantics, expressed only in terms of the results obtained, and of small-step semantics, which detail the different execution steps. We enter the details of the reasoning techniques associated with these formalisms, i.e. the ways in which we can state and prove properties concerning the execution of a program or the correction of a transformation. This course is related to the Compilation and Rewriting courses. |
| Prerequisite: Logic, recurrence, general culture of programming languages. |
| Language : English |
| [MPRI] Introduction to Proof Assistants |
| Coordinator: Burkhart Wolff |
|
This course is an introduction to the theory and practice of Coq and Isabelle/HOL interactive proof systems. Description: - logical framework: simply typed lambda-calculus, higher order logic; - modeling and proofs: algebraic types, inductive definitions, recursive definitions and termination, induction; - proof tools: architecture of a proof assistant, elementary tactics. |
| Prerequisite: logic, recurrence. |
| Language : English |
| [MPRI] Introduction to deductive proof of programs |
| Coordinator: Andrei Paskevich, Julien Signoles |
| The objective of this course is to introduce formal specification and deductive verification of programs through the use of Why3 and Frama-C tools. |
| Prerequisite: Logic, programming. |
| Language : English |
| [MPRI] Automata and Applications |
| Coordinator: Kim Nguyen |
|
Learning objectives: to study the various forms of automata, including tree automata and their relationship to logics. Description: This course presents various extensions to word automata, classically used in syntactic analysis. It focuses on tree automata and regular tree languages. It also presents connections between logic and automata : the way in which the latter offers decision procedures for the former. Finally, the course shows how automata can be used in practical cases e.g. for the sake of typing procedures, filtering compilation or validation of XML or JSON documents. Topics covered: - Recap on finite word automata and regular languages; - Tree automata and regular tree languages; - Logic, automata and their relations; - Alternating automata; - Constrained automata; - Tree transducers. |
| Prerequisite: Bachelor level knowledge of formal languages (grammars, word automata, regular expressions). Programming in a high-level language (OCaml, Java or Python). |
| Language : English |
| [MPRI] Complexity, decidability, models of computation |
| Coordinator: Benjamin Hellouin |
|
- Classes in space (and a bit more); - Notion of computational model, Turing-universality, universal machines; - Simple randomized complexity classes, approximation classes & inclusions; - Reachability problems, P-completeness; - Semi-decidability, proofs by injection of universal computation. |
| Prerequisite: A basic complexity course such as the "Theoretical Computer Science" course of the L3 Computer Science / Math-info of Paris Sud. Deterministic and non-deterministic Turing machines, P, NP and PSPACE classes, notions of reduction and completeness (at least NP-completeness), undecidability (halting problem). |
| Language : English |
| [MPRI] Combinatorics and Algebraic Computation |
| Coordinator : Florent Hivert, Nicolas Thiéry |
| This course is an introduction to mathematical tools for symbolic computation and combinatorics, with applications for example in cryptography cryptography or to software random testing. We will adopt an effective approach by focusing on both algorithms and their implementations in computing systems. |
| Prerequisite: 3rd year Bachelor Algorithms course, 2nd year Linear Algebra course, Maths for Computer Science. |
| Language : English |
| [MPRI] Probabilistic Algorithms and Games |
| Coordinator: Joanna Tomasik, Johanne Cohen |
|
Objective: to develop skills in the area of discrete optimization. The course presents algorithms that solve problems beyond class P and those problems belonging to class P whose exact solution is too costly in practice. The time efficiency is obtained through probabilities. On the other hand, the results are not necessarily exact. This course deals with the notions of adversary and searching the state space. - Introduction to probability theory; - Interpretation of the results of a randomized algorithm (statistical evaluation of the performance: central limit theorem, confidence interval); - Optimization algorithms without performance guarantees, i.e. heuristic algorithms (the concept of the state space and the corresponding search: Hill Climbing, simulated annealing with its underlying Markov chain); - Techniques for accelerating heuristics: evolutionary algorithms (genetic algorithms); - Online algorithms: design of algorithms when the input is revealed as it is received (the secretary problem, the ski rental problem, etc.); - Introduction to game theory (games, Nash equilibria, potential game, computation of equilibria, application of the concept of Nash equilibrium in machine learning in adversarial networks). |
| Prerequisite: |
| Language : French |
| [MPRI] Graph Algorithms |
| Coordinator: François Pirot |
|
Content:
The objective of the course is to present the main structural results and algorithms on graphs, in connection with the concrete situations in which they are used. The following points will be studied: - Graph coloring, number/chromatic index; - Cycle and path problems, Eulerian paths, Hamiltonian cycles; - Couplings (algorithms, structural results, couplings in bipartite graphs, minimum cover per vertex); - Connectedness (edge/vertex connectedness, Menger theorem); - Planar graphs; - Theory of minors and their applications (FPT, tree decomposition). |
| Prerequisite: Algorithms, graph algorithms, complexity. |
| Language : English |
| [MPRI] Advanced Algorithms |
| Coordinator: Arpad Rimmel, Marc-Antoine Weisser |
| Content: In this course, students will learn to appreciate optimization problems and determine the best approaches to deal with them. The notions of complexity and polynomial reductions will be seen and practiced. Some algorithmic solution techniques will be presented that solve difficult problems (approximation, approximation scheme, heuristics). This course will be based on the modeling of concrete problems. |
| Prerequisite: A basic complexity course. |
| Language : French |
| [MPRI] Foundations of Quantum Information |
| Coordinator: Pablo Arrighi |
|
Content: 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 & communications, quantum error correction and quantum simulation. The following points will be presented: - postulates, no-cloning, no-distinguishability; - density matrices and quantum operations; - Dirac and Coecke notations; - superdense-coding protocols, teleportation, QRAC, BB84 key sharing...; - non-signalling vs. locality, Bell inequalities, certified randomness ; - state decomposition theorems and operators ; - fundamental theorem of quantum error correction ; - Hamiltonian quantum simulation ; - digital quantum simulation by quantum walks and quantum cellular automata. |
| Prerequisite: All of the necessary reminders will be given. However, make sure you do like linear algebra: vectors, matrices, inner product, norm. |
| Language : English |
| [ANO] MPI Programming |
| Coordinator: Nicolas Dupin |
| >>> |
| [QDCS] Initiation to quantum algorithms and programming |
| Coordinator: Benoît Valiron |
| >>> |
| Language : English |
| [QDCS] Robust distributed algorithms |
| Coordinator: Janna Burman |
| >>> |
| Language : English |
| [QDCS] Parallel Algorithms |
| Coordinator: Oguz Kaya |
| >>> |
| Language : English |
| [MPRI] Introduction to Research |
| Coordinator: Philippe Schnoebelen |
| >>> |
| Language : English |
| 2 elective courses |
|
UFR List >>> UFR Timetable >>> ENS List >>> ENS Timetable >>> |