## M1 entrance requirementsThe 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.
- 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.
- Identifiers, scope of identifiers, assignments, data types, functions, parameters passing, static/dynamic binding, objects (methods, classes, inheritance).
Sethi, “Programming languages (2nd edition)“
- Analysis of algorithms (runtime complexity, amortized analysis, O, o, Θ)
- Sorting, heaps, priority queues, hash tables, strings/patterns search,
- Elementary algorithms on trees and graphs (traversal, shortest path)
- Divide and conquer, greedy algorithms, dynamic programming
Cormen, Leiserson, Rivest, “Introduction to algorithms”
- Regular expressions, finite automata and basic theorems
- Context free languages and basic theorems
Aho Ullmann, “The theory of Parsing, Translation and Compiling, volume 1”
- Basic knowledge on architectures
- General knowledge on Unix (shell, pipes, files, processes, redirections)
- Basic functions of an operating system: files, device management, scheduling
Patt, Patel, “Introduction to Computing Systems” Chapters 1 et 4. Welsh, Dalhemier, Kaufman. “Le systeme linux” Chapter 4.
- Relational model, relational algebra
- Standard use of a data base management system
Abiteboul, Hull, Vianu, “Foundations of databases” Chapter 3, 7.
- Propositional logic: syntax, semantics, truth tables, proofs, completeness
- First order logic: terms, substitutions, models
- Turing machines, computability, examples of undecidable problems.
- Complexity classes: P, NP and co-NP
Stern, “Fondements mathématiques de l' informatique”
- Simple notions of probabilities
- Induction principle, structural induction
- Basic notions on formal power series
- Basic notions on orderings
Cormen, Leiserson, Rivest, “Introduction to algorithms”
- Implementation of a programming project, using the standard development tools.
## M2 entrance requirementsStudents 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: ## General requirements
- 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. - Identifiers, scope of identifiers, assignments, data types, functions,
parameters passing, static/dynamic binding, objects (methods, classes, inheritance), modules, separate compilation. - Semantics of programming languages and some proofs of programs techniques.
Fixed points (Tarski for the set lattice). - Implementation of a significant programming project.
- Data structures, abstract approach: compute on data types using their interfaces instead of theire representations.
Abstract data types for lists, stacks, queues, trees, graphs. - 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. - 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) - 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). - Flow algorithms, duality
- And/or graphs, reachability
- Compression
- Regular expressions, finite automata and basic theorems
- Context free languages and basic theorems
- compiling (parsing LL/LR, Lex, Yacc, attributes, intermediate code, code generation, register allocation, elementary optimisations, rudiments of abstract interpretation)
- typing (elementary typing systems, type inference à la ML, modules)
- General knowledge on Unix (shell, pipes, files, processes, redirections)
- Basic functions of an operating system: files, device management, scheduling
- Advanced functions of an operating system: virtual memory, processes, architecture of an OS.
- Concurrent programming (semaphore, monitor, etc.)
- Propositional logic: syntax, semantics, truth tables, proofs, completeness
- First order logic: terms, substitutions, models, completeness, Gödel's theorems, resolution.
- Turing machines, computability, examples of undecidable problems.
- Complexity classes: P, NP and co-NP, reductions.
- Simple notions of probabilities
- Induction principle, structural induction
- Basic notions on formal power series
- Basic notions on orderings, lexicographic composition.
## Additional entrance requirements for specific modulesSpecific 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. |