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 problématiques actuelles.

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 ne saurait prétendre couvrir sur un seul semestre. Mais tous les chemins commencent par un premier pas, et nous nous assurerons de maîtriser d’abord les notions les plus fondamentales. Le programme envisagé est le suivant :

  • La correspondance de Curry-Howard, cuite dans son jus.
  • Théories de types et avènement des assistants à la preuve.
  • Les éléments d’une refondation des mathématiques : état de l’Art.

Références bibliographiques :

Outre la page de WikiPedia pour les impatients (https://fr.wikipedia.org/wiki/Correspondance_de_Curry-Howard) :

  • Intuitionistic Type Theory. P. Martin-Löf. 1980.
  • Proofs and Types. J.-Y. Girard, Y. Lafont, P. Taylor. 1987.
  • Lambda-calcul : types and modèles. J.-L. Krivine. 1990.
  • Homotopy Type Theory. Collectif. http://homotopytypetheory.org/book/.

Plus en suivant ce lien : https://perso.ens-lyon.fr/philippe.audebaud/PnP/

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 to multiple precision integer arithmetic, floating-point arithmetic, finite fields arithmetic.
  2. Linear algebra over a field
    – Matrix/vector product, naive matrix/matrix product
    – Row echelon form & applications : kernel, image, rank, determinant, linear system solving, etc.
    – Fast matrix/matrix product : Strassen ; fast inversion/determinant.
    – Structured matrices: circulant, Hankel, Toeplitz, Cauchy, and related algorithms.

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 et de sept séances de TPs. Les TPs auront pour but l’initiation
la programmation parallèle et distribuée par passage de messages
(MPI). Un petit projet de programmation est organisé sous forme de
devoir à la maison.

Plan indicatif des cours :

  • Modèle théorique des réseaux de tri
  • Modèle théorique des PRAMs
  • Algorithmique sur anneau et grille de processeurs: produit matrice-vecteur,
    produit matrice-matrice, stencil 2D, etc.
  • Algorithmique distribuée: modèles, élection, consensus, détection de
    terminaison
  • Ordonnancement de graphes de tâches avec et sans communications,
    avec ou sans contraintes de ressources: complexité, algorithmes
    d’approximations et heuristiques
  • Analyse de dépendance et parallélisation automatique
  • Exemple d’algorithme pour GPU

La note de contrôle continu est établie à partir d’un partiel organisé
en milieu de semestre, du devoir à la maison de programmation, et d’un
examen final.

Géométrie discrète et images numériques

Programme de l’UE

L’objectif de ce cours est d’introduire les notions de base d’analyse et de traitement d’images. Après quelques séances durant lesquelles on se focalisera sur des problèmes de représentation de données, on se focalisera plus particulièrement sur des problèmes algorithmiques et théoriques liés à l’analyse géométrique de formes numériques. Ainsi, on sera amené à s’intéresser des outils de géométrie discrète, de géométrie algorithmique voire d’arithmétique et de combinatoire.

Le cours sera accompagné de séances de TP ayant comme objectif de s’intéresser à l’implémentation de certains outils théoriques présentés dans le cours.

Plan indicatif:

  • Représentation images/formes
  • Traitement et analyse d’images (filtrage, segmentation)
  • Géométrie discrète pour l’analyse de formes
  • Géométrie algorithmique et structures de données

Pré-requis: Des connaissances élémentaires en algorithmique

Livres:

  • « Géométrie discrète et images numériques », D. Coeurjolly, A. Montanvert and J.-M. Chassery, Ouvrage collectif, Traité IC2, Hermès, 416 pages, 2007
  • « Computational Geometry: Algorithms and Applications », Mark de Berg, TU Eindhoven (the Netherlands) Otfried Cheong, KAIST (Korea),Marc van Kreveld, Mark Overmars, Utrecht University (the Netherlands), Springer-Verlag

Fiche d’évaluation

Intervenants

Complexité algorithmique

Programme de l’UE

What computing resources do we need to solve a computational problem? The computational complexity theory studies this question from a structural point of view. Building up on the Turing machine model, we will discover and study deterministic and nondeterministic complexity classes, space and time complexity and hierarchy, completeness, randomized algorithms classes, boolean circuits and counting classes.

 

Bibliography:

Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak (mostly chapters 1 to 7)

more about computational complexity

 

De quelles ressources avons nous besoins pour résoudre un problème, faire un calcul ? La théorie de la complexité algorithmique étudie ce problème d’un point de vue structurel. En nous appuyant sur le modèle des machines de Turing, nous étudierons les classes de complexité déterministes et non déterministes, en temps et en espace, les hiérarchies entre ces classes, les problèmes complets, les algorithmes et classes probabilistes, les classes définies par les circuits ainsi que quelques notions sur les classes de comptage.

 

Bibliographie :

Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak, principalement les chapitres 1 à 7

Pour en savoir plus sur la théorie de la complexité algorithmique

https://fr.wikipedia.org/wiki/Théorie_de_la_complexité_(informatique_théorique)

Page du cours (for 2013-2014)

Intervenants

  • Omar Fawzi, MdC ENS Lyon