The MPRI master is open to all students holding a Bachelor (or equivalent). The entrance requirement are, in short the Bachelor program of the main universities/grandes écoles.

Programming

1. General knowledge of an imperative language (C, C++), a functional language (Ocaml), an object oriented language (C++, Java) and an in-depth knowledge of one of these programming languages.
2. Identifiers, scope of identifiers, assignments, data types, functions, parameters passing, static/dynamic binding, objects (methods, classes, inheritance).

Bibliography :

Sethi, “Programming languages (2nd edition)“
Chapters 1,2, 3.1 à 3.4, 4.1 à 4.4, 5.1 à 5.5, 6.1 à 6.4, 7.1 à 7.3, 8.

Algorithmics

1. Analysis of algorithms (runtime complexity, amortized analysis, O, o, Θ)
2. Sorting, heaps, priority queues, hash tables, strings/patterns search,
3. Elementary algorithms on trees and graphs (traversal, shortest path)
4. Divide and conquer, greedy algorithms, dynamic programming

Bibliography :

Cormen, Leiserson, Rivest, “Introduction to algorithms”
Chapters 1, 2, 5, 7, 8, 11, 12, 13, 16, 17, 18, 23, 25, 26, 34.

Formal languages

1. Regular expressions, finite automata and basic theorems
2. Context free languages and basic theorems

Bibliography

Aho Ullmann, “The theory of Parsing, Translation and Compiling, volume 1”
Chapter 2, sections 1,2,3,4.1 à 4.3,5.2,6.1 à 6.3.

Architecture and operating systems

1. Basic knowledge on architectures
2. General knowledge on Unix (shell, pipes, files, processes, redirections)
3. Basic functions of an operating system: files, device management, scheduling

Bibliography :

Patt, Patel, “Introduction to Computing Systems” Chapters 1 et 4. Welsh, Dalhemier, Kaufman. “Le systeme linux” Chapter 4.

Data bases

1. Relational model, relational algebra
2. Standard use of a data base management system

Bibliography :

Abiteboul, Hull, Vianu, “Foundations of databases” Chapter 3, 7.

Logic and computability

1. Propositional logic: syntax, semantics, truth tables, proofs, completeness
2. First order logic: terms, substitutions, models
3. Turing machines, computability, examples of undecidable problems.
4. Complexity classes: P, NP and co-NP

Bibliography :

Stern, “Fondements mathématiques de l' informatique”
Chapitre 2 ( parag. 1,2,4,5), 4, 5 (parag. 1,2), 6 (parag. 1,2)

Mathematics

1. Simple notions of probabilities
2. Induction principle, structural induction
3. Basic notions on formal power series
4. Basic notions on orderings

Bibliography :

Cormen, Leiserson, Rivest, “Introduction to algorithms”
Chapters 3, 4 and 6.

Programming Projects

1. Implementation of a programming project, using the standard development tools.

Students can be hosted directly at the M2 level, provided that they followed a M1 or equivalent in some other school or university in France or abroad. The admission is subject to the approval of the studies committee. Here are the requirements for entering directly at the M2 level:

Programming

1. General knowledge of an imperative language (C, C++), a functional
   language (Ocaml), an object oriented language (C++, Java) and an in-depth
   knowledge of one of these programming languages.
2. Identifiers, scope of identifiers, assignments, data types, functions,
   parameters passing, static/dynamic binding, objects (methods, classes,
   inheritance), modules, separate compilation.
3. Semantics of programming languages and some proofs of programs techniques.
   Fixed points (Tarski for the set lattice).
4. Implementation of a significant programming project.

Algorithmics

1. Data structures, abstract approach: compute on data types using their interfaces instead of theire representations.
   Abstract data types for lists, stacks, queues, trees, graphs.
2. Analysis of algorithms notations O,o, Θ, Ω, partition induction,
   analyses in the worst case and in the average case of the quicksort.
   Proof principles: assertions, pre and post conditions, invariants termination.
3. Search and sort algorithms, merge sort, heapsort, quicksort, decision trees and optimality.\\Sequential search and binary search, representation of search dictionnaries:\\binary search trees, self-balanced trees, red-black trees,
   hash methods (separate chaining,linear hash, double hashing)
4. Graph algorithms.
   Graph traversal: breadth-first (topological sort, shortest path), depth-first (strongly connected components), covering trees of minimum weight: Prim, Kruskal. shortest paths: transitive closure, dynamic programming (Floyd-Marshall).
5. Flow algorithms, duality
6. And/or graphs, reachability
7. Compression

Formal languages

1. Regular expressions, finite automata and basic theorems
2. Context free languages and basic theorems

Languages

1. compiling (parsing LL/LR, Lex, Yacc, attributes, intermediate code, code generation, register allocation, elementary optimisations, rudiments of abstract interpretation)
2. typing (elementary typing systems, type inference à la ML, modules)

Operating systems

1. General knowledge on Unix (shell, pipes, files, processes, redirections)
2. Basic functions of an operating system: files, device management, scheduling
3. Advanced functions of an operating system: virtual memory, processes, architecture of an OS.
4. Concurrent programming (semaphore, monitor, etc.)

Logic and computability

1. Propositional logic: syntax, semantics, truth tables, proofs, completeness
2. First order logic: terms, substitutions, models, completeness, Gödel's theorems, resolution.
3. Turing machines, computability, examples of undecidable problems.
4. Complexity classes: P, NP and co-NP, reductions.

Mathematics

1. Simple notions of probabilities
2. Induction principle, structural induction
3. Basic notions on formal power series
4. Basic notions on orderings, lexicographic composition.

Specific additional entrance requirements may be set, within a limited framework, for each level 2 module. Such additional entrance requirements will then be specified within the description of each level 2 module.