M1 2017-2018

Désolé, cet article est seulement disponible en English.

Information M2 – 2017/2018

List of courses (for full description follow the link CRxx):

  • CR01: Optimal Decision Making and Online Optimization, Panayotis Mertikopoulos and Bruno Gaujal.
  • CR02: Computational Geometry, Monique Teillaud and Olivier Devillers.
  • CR03: Hard lattice problems, Damien Stehlé.
  • CR04: Automata, coinduction, and relation algebra, Damien Pous.
  • CR05: Monadic Second Order Logic, Automata, Expressivity and DecidabilityMatteo Mio and Denis Kuperberg.
  • CR06: Implicit Computational Complexity, Patrick Baillot and Olivier Laurent.
  • CR07: Models of concurrency, categories, and games, Pierre Clairambault and Glynn Winskel.
  • CR08: Scheduling at scale, Yves Robert.
  • CR09: Advanced Topics [Lire la suite…]

Apprentissage

Désolé, cet article est seulement disponible en English.

Gestion et Fouille de Données

Gestion et Fouille de Données

Ce cours est offert au second semestre du M1.

Descriptif du cours :

  • Bases de données – Modèle relationnel, calcul relationnel, SQL – Algèbre, équivalence algèbre/calcul, indexation et optimisation – Dépendances fonctionnelles, axiomatisation, relations d’Armstrong – Dépendances d’inclusion, data exchange, chase, réécriture de requête
  • Fouille de données – Introduction à la fouille de données (motifs ensemblistes et algorithmes/explorations classiques) – Fouille de motifs sous-contraintes:  étude et exploitation des   propriétés des contraintes – Langage de motifs plus sophistiqués (concepts formels, séquences, graphes, graphes dynamiques, …) – (Bi-|Co-)Clustering – Ouverture vers les [Lire la suite…]

Systèmes distribués

Distributed Systems

Course offered in the second semester of M1.

Course contents:

  • Introduction – Distributed System Modelization – Communication Protocol
  • Classic Algorithms – Wave Algorithms – Transversal Algorithms – Leader Election – Mutual Exclusion
  • Fault Tolerance – Fault Tolerance introduction – Self-stabilization
  • Advanced Algorithms – k-clustering in distributed systems – Clock synchronization in distributed systems
  • Practical Sessions – Introduction to Erlang

Sémantique et Vérification

Sémantique et Vérification

Ce cours est offert au second semestre du M1.

du cours :

  • Ordres et topologies. . Points fixes. . Approximations et correspondances de Galois. . Sémantique d’un langage impératif d’ordre supérieur
  • Systèmes de transitions étiquetées . équivalences, bisimulation
  • Logiques modales et verification . logique de Hennessy-Milner . LTL, CTL

Preuves et programmes

Preuves et programmes

Ce cours est offert au second semestre du M1.

Contenu du cours :

Raisonner et programmer sont les deux côtés d’une même pièce.

L’épine dorsale de cette relation est la découverte d’une correspondance très forte entre des énoncés simples (calcul propositionnel) et des termes d’un modèle de calcul (λ-calcul). C’est la correspondance de Curry-Howard (1980).

En 2006, suite aux travaux de Voevodsky sur l’univalence (basée sur la théorie de l’homotopie), une nouvelle révolution est en marche. qui permet désormais de *faire des mathématiques en programmant*.

C’est un sujet qu’aucun format de cours [Lire la suite…]

Géométrie computationnelle et images digitales

Image processing, digital and computational geometry

Course offered in the second semester of M1.

Objectives of the course:

The objective of this course is to introduce fundamental notions of image processing, digital geometry and computational geometry.  The first lectures will be dedicated to image processing (filtering, smoothing, morphological mathematics, ..) and shape representation. Then, we will focus on theoretical and algorithmic issues involved in the analysis of digital shapes. During this analysis of  digital geometry processing tools, we will have to present and integrate some tools from various fields: discrete mathematics, combinatorics, arithmetics, computational geometry, ..

[Lire la suite…]

Complexité algorithmique

Computational Complexity

Course offered in the second semester of M1.

Overview of the course:

Computational complexity aims to classify computational problems depending on the resources they need. One studies various modes of computation such as deterministic, randomized, nondeterministic or quantum and compares resources such as time or space needed to solve algorithmic problems. The objective of this course is to give a broad understanding of the notions used to classify computational problems. About half of the course is dedicated to studying basic complexity classes defined using Turing machines. We introduce (or study deeper) notions that are [Lire la suite…]

Cryptographie et sécurité

Cryptography and Security

Course offered in the second semester of M1.

Course contents:

This course is an introduction to the different facets of modern cryptography.

The following topics will be addressed:

  • Symmetric cryptography Pseudo-random number generators Pseudo-random functions Message Authentication Codes Stream ciphers and block ciphers Security against chosen plaintext/ciphertext attacks Hash functions
  • Asymmetric cryptography Discrete logarithm, decision Diffie-Hellman Factoring, RSA problem Key exchange Digital signatures Public-key encryption The random oracle methodology
  • Other topics possibly covered: Zero-knowledge proofs Secret sharing Yao’s garbling circuits

Calcul formel

Computer Algebra

Course offered in the second semester of M1.

contents:

This class shall survey some of the central topics of computer algebra: arithmetics, effective linear algebra, polynomial system solving.

The following topics will be studied:

  1. Arithmetic(s) — mostly polynomial. – Representation of polynomials, linear operations (addition, evaluation). – Multiplication : schoolbook method, Karatsuba method, Toom-Cook method Fast Fourier Transform. – Division : schoolbook method, Newton method, recursive division – GCD : Euclidean algorithm, extended GCD, application to CRT; introduction to fast GCD. – Fast multiple point evaluation, fast interpolation, fast CRT. – Introduction [Lire la suite…]

Théorie de l’Information

Désolé, cet article est seulement disponible en English.

Optimisation et Approximation

Désolé, cet article est seulement disponible en English.

Algorithmique et Programmation Parallèles et Distribuées

Algorithmique et Programmation Parallèle et Distribuée

Cours du M1 2015-2016, premier semestre.

Programme de l’UE :

Le parallélisme est devenu incontournable en informatique, le moindre processeur étant multi-cœurs. Cette UE a pour objet la conception d’algorithmes parallèles et distribués efficaces, et aborde leur mise en œuvre pratique sous forme de TPs. Les séances de cours auront pour objet les modèles théoriques utilisés pour la conception et l’analyse des algorithmes et l’étude de problèmes algorithmiques particuliers (complexité, définition et analyse d’algorithmes, algorithmes d’approximations, etc.). Les quatorze séances de cours seront accompagnées de sept séances de TDs [Lire la suite…]

Évaluation de Performance et Réseaux

Évaluation de Performances des Réseaux

Cours du M1 2015-2016, premier semestre.

Présentation du cours :

Ce cours de 1er semestre du M1 Informatique Fondamentale est consacré à l’évaluation de performances des réseaux de communication. Il est accessible à tout étudiant ayant des connaissances de bases en probabilités. Des connaissances de bases en systèmes/réseaux sont conseillées mais pas indispensables. Le thème de l’évaluation de performances recouvre beaucoup de points de vue, comme la conception de modèles mathématiques (avec très souvent des probabilités), l’analyse de ces modèles (mathématiquement ou par simulation), la mise en place de protocoles [Lire la suite…]