M2 IMD - Contenus des cours d'option

Les intervenants et contenus de cours décrits ci-dessous sont indicatifs, susceptibles d'être adaptés chaque année en fonction du public et des disponibilités des intervenants.

Mathématiques discrètes

Théorie de l'information

Intervenants : Stéphane Ballet, Alexis Bonnecaze, David Kohel

Les outils mathématiques utilisés en cryptographie et codage évolue pour s'adapter à la puissance des ordinateurs et des services demandés.  C'est particulièrement vrai en ce qui concerne la cryptographie asymétrique dont la sécurité repose sur la difficulté de résoudre certains problèmes. L'introduction des courbes elliptiques a permis de réduire la taille des clés tout en gardant un niveau de sécurité identique. Les pairings ont permis d'obtenir de nouvelles primitives cryptographiques et ont en particulier amené la cryptographie basée sur l'identité. Le futur est actuellement principalement incarné par des outils basés sur des propriétés de la physique quantique.

L'objectif de ce cours est de présenter ces outils théoriques ainsi que leurs applications en cryptographie et codage, et de s'intéresser à certaines implémentations en langages Sage, Magma et C.

Plan du cours :

  • Introduction
  • Problèmes difficiles (DLP, factorisation, CDH, DDH, etc)
  • Courbes elliptiques pour la cryptographie
  • Pairings et IDBased crypto
  • Introduction à la cryptographie post-quantique
  • Introduction au codes correcteurs d'erreurs quantiques

Calcul naturel

Intervenants : Pablo Arrighi, Giuseppe Di Molfetta, Kévin Perrot, Sylvain Sené

Cette UE vise à donner aux étudiants qui la suivent une "culture" dans le domaine du calcul naturel, à la frontière des mathématiques discrètes et de l'informatique (fondamentale). Nous y introduirons certains des principaux modèles classiques du domaine comme les automates cellulaires et plus largementles réseaux d'automates, ainsi que les piles de sable. Par ailleurs, une partie de cette UE visera à présenter les fondamentaux de l'informatique et de l'information quantiques. La présentation de ces différents domaines du calcul naturel permettra aussi d'établir des liens que les mathématiques discrètes et l'informatique entretiennent avec d'autres disciplines, comme la biologie et la physique.

Topologie algèbrique discrète - topologie algorithmique

Intervenants :  Dimitri Ara, Alexandra Bac

Introduction

  •   Topologie algébrique : du continu au discret

Les fondements

  • Espaces topologiques, complexes simpliciaux et cubiques
  • Bases du langage des catégories
  • Un peu d’algèbre homologique
  • Homologie singulière
  • Invariance par homotopie
  • Suite exacte de Mayer-Vietoris et calculs

Homologie simpliciale et cubique

  • Esquisse de comparaison avec l’homologie singulière
  • Ouverture vers les groupes d’homotopie

Vers la géométrie discrète :

  • Notions de géométrie discrète (objets binaires et leur topologie, complexes associés)

Calcul de l’homologie singulière :

  • soit par des approches algébriques (forme normale de Smith)
  • soit approches combinatoires (théorie de Morse discrète)
  • soit en combinant les deux (homologie effective - basée sur la notion de réduction ... là on est proche des catégories)

Persistance homologique

Systèmes dynamiques et théorie de Ramsey

Intervenants : Guillaume Theyssier, Pierre Arnoux, Kevin Perrot, Sylvain Sené, Lionel Nguyen Van Thé

Dynamique symbolique 1D : sous-décalages, sofiques, SFT, représentation par graphes, lien avec la combinatoire des mots, représentation matricielle, propriétés dynamiques topologiques, entropie topologique.

Dynamique symbolique 2D : pavages apériodiques, hiérarchie, problème du pavage du plan, simulation Turing, indécidabilité, systèmes substitutifs.

Ouverture sur thématiques avancées : dynamique symbolique mesurée, dynamique symbolique sur les groupes, dynamique directionnelle et automates cellulaires.

Théorème de Ramsey, fini et dénombrable.

  • Applications : Théorèmes d'Erdos-Szekeres sur les sous-suites monotones, et sur les polygones convexes du plan.
  • Bornes : Bornes sup et double récurrence, borne inf et méthode probabiliste.

Théorèmes de partition en théorie des nombres :

  • Théorème de Schur.
  • Théorème de Rado sur les systèmes d'équations régulières par partitions.
  • Théorème de van der Waerden, via le théorème de Hales-Jewett.

Théorie de Ramsey euclidienne :

  • Ensembles de Ramsey du plan: Tout ensemble de Ramsey est sphérique.
  • Nombre chromatique du plan. Prétexte de ce probème pour évoquer la pertinence de l'axiomatique de la théorie des ensembles.

Théorie de Ramsey infinie : (le but de cette partie sera surtout de poursuivre la réflexion sur la pertinence de la théorie des ensembles en tant que cadre axiomatique)

  • Théorème de Hindman, via les ultrafiltres.
  • Théorème de Galvin-Prikry.
  • Le rôle de l'axiome du choix et des axiomes de détermination.

Algorithmique et combinatoire

Fondements de la PPC et SAT

Intervenant : Philippe Jegou

Cette option traite des fondements de la programmation par contraintes (PPC) et de la résolution de SAT. Elle couvre les aspects allant des algorithmes, architectures et fondements théoriques des solveurs SAT et CSP, jusqu'à l'étude des classes polynomiales dans ces deux formalismes.

Les points abordés portent sur :

  • classes polynomiales ("tractable classes") pour SAT, CSP et au-delà ;
    • classes définies par restrictions de langages,
    • classes définies par décomposition de graphes et hypergraphes (exploitation des résultats sur les problèmes exprimables en MSO sous l'hypothèse de largeurs bornées)
    • classe hybrides
  • architecture des solveurs :
    • algorithmes de résolution
    • algorithmes de propagation
    • heuristiques
    • clauses et no-goods learning
    • notion de redémarrage avec preuve de complétude
  • méthodes de résolution pour l'optimisation dans les formalismes VCSP, MaxSAT, WMaxSAT,
    • méthodes complètes (B&B et ses optimisations)
    • méthodes incomplètes (recherche locale, recherche tabou, algorithmes génétiques,...)
    • algorithmes de propagations de pondérations

Algorithmique distribuée

Intervenants : J. Chalopin, S. Das, E. Godard, D. Imbs, A. Labourel

L'objectif de ce cours est de présenter des problèmes fondamentaux d'algorithmique distribuée, ainsi que des résultats de calculabilité et de complexité associés. On utilisera des méthodes algorithmiques pour résoudre ces problèmes classiques et des méthodes combinatoires et topologiques pour montrer des résultats d'impossibilité et des bornes inférieures de complexité

Modèlisation des Systèmes Distribués

  • Panorama des systèmes distribués
  • Calculabilité distribuée
  • Équivalence entre modèles
  • Vers un modèle unifié ?

Systèmes à passages de messages

  • Modèles de communication
  • Algorithmes pour la diffusion et l'élection
  • Algorithmes probabilistes pour les réseaux anonymes

Mémoire partagée

  • Impossibilité du consensus sans attente
  • Modèle du snapshot itéré et impossibilité du k-consensus
  • Diffusion tolérante aux défaillances
  • De la mémoire partagée aux réseaux dynamiques

Agents mobiles

  • Modèles et mesures de complexité
  • Exploration et rendez-vous

Selon les années et les intervenants, l'importance relative de ces différents thèmes pourra varier.

Optimisation combinatoire

Intervenants : B. Couëtoux, G. Naves et Y. Vaxès

Un problème d'optimisation combinatoire est caractérisé par un espace de solutions très grand mais que l'on peut décrire de manière compacte, comme l'ensemble des couplages, des st-chemins, des arbres couvrants ou des cycles hamiltoniens d'un graphe ou encore l'ensemble des permutations de n entiers. Une fonction objectif permet d'évaluer la qualité de chacune des solutions de l'espace de recherche. Résoudre un problème d'optimisation combinatoire c'est trouver une solution qui minimise ou maximise la fonction objectif. De nombreux problèmes aussi bien pratiques que théoriques se formulent de cette manière.

L'objectif du cours est de présenter quelques idées fondamentales qui permettent de concevoir des algorithmes efficaces pour résoudre de façon exacte ou avec une garantie de performance des problèmes d'optimisation combinatoire.

On insistera en particulier sur les notions suivantes :

  1. L'approche polyédrale consiste à représenter chaque solution de l'espace de recherche par son vecteur caractéristique et à étudier l'enveloppe convexe de ces vecteurs. Si celle-ci peut-être décrite de façon compacte (par exemple, par un nombre d'inégalités polynomial dans la taille de l'entrée du problème) alors la programmation linéaire permet d'obtenir un algorithme de résolution efficace.
  2. Une telle description vient souvent avec un résultat de type min-max qui permet de définir l'optimum du problème de minimisation que l'on cherche à résoudre comme l'optimum d'un autre problème de maximisation (ou l'inverse). La dualité de la programmation linéaire fournit un tel résultat. Elle est à la base de la conception de nombreux algorithmes efficaces (polynomial) de résolution exacte ou approchée via la méthode primale-duale.
  3. Même lorsqu'une représentation polyédrale compacte n'est pas disponible, en particulier pour les problèmes NP-difficiles, l'approximation de l'enveloppe convexe par des inégalités linéaires, appelées coupes, permet de fournir des bornes cruciales pour la résolution pratique des problèmes NP-difficiles par des méthodes de type séparation-évaluation-coupes (branch-and-cut). Nous illustrerons chacune de ces notions ou approches sur différents problèmes classiques : couplage, flot et coupes, arborescence, TSP, indépendant commun à deux matroïdes, arbre et réseau de Steiner, problème de localisation, etc.

Selon les années et les intervenants, la liste des problèmes étudiés et l'importance relative des différentes notions pourra varier.

Prérequis: Un intérêt pour les structures discrètes, la programmation linéaire et l'algorithmique. Toutes les notions utilisées dans le cours seront définies et expliquées.

Théorie métrique des graphes

Intervenants : J. Chalopin, V. Chepoi et Y. Vaxès

L'objectif du cours est de présenter les résultats principaux de la théorie métrique des graphes et des liens existant entre cette théorie et d'autres domaines comme la théorie géométrique des groupes ou la théorie de la concurrence.  On présentera des méthodes algorithmiques, combinatoires, géométriques et topologiques.

Plongements isométriques dans des hypercubes et des produits de graphes

Graphes médians, graphes bridged et la méthode "local vers global"

  • Équivalence entre les graphes médians, les complexes cubiques CAT(0) et les domaines de structures d'événements.
  • Équivalence entre graphes bridged et complexes simpliciaux systoliques

Graphes et espaces hyperboliques au sens de Gromov

  • Métrique d'arbres et 0-hyperbolicité
  • Définitions et caractérisations de l'hyperbolicité
  • Propriétés algorithmiques des graphes hyperboliques
  • Problème du mot dans les groupes hyperboliques

Plongement l_1 à faible distorsion et théorème de Bourgain. Applications algorithmiques

Graphes de Helly et enveloppes injectives

Selon les années et les intervenants, l'importance relative de ces différents thèmes pourra varier.

Prérequis : Un intérêt pour la combinatoire, les structures discrètes et l'algorithmique. Toutes les notions utilisées dans le cours seront définies et expliquées.

Méthodes formelles

Modélisation et simulation à événements discrets

Intervenants : L. Brenner, I. Demongodin, C. Frydman, A. Hamri

Ce cours porte sur les méthodes de spécification des systèmes complexes et les formalismes à événements  discrets. Afin de maîtriser la spécification comportementale de ces systèmes, ce cours présente les formalismes permettant une spécification de haut niveau. Il fournit les bases théoriques en modélisation, analyse, simulation à événements discrets pour les domaines de l’informatique et des systèmes dynamiques complexes.

Plan de cours :

Présentation de divers formalismes à événements discrets avec et sans représentation du temps :

  • DEVS : Discrete EVent System Specification
  • RdP : Réseaux de Petri

Théorie des automates : extensions et applications

Intervenants : N. Baudru, S. Fratani, B. Monmege, JM Talbot, PA Reynier, M. Shirmohammadi

L’objectif du cours est de présenter une ou plusieurs extensions du modèle classique des automates finis, en insistant sur les résultats positifs obtenus pour cette extension, les applications visées par cette extension, ainsi que les enjeux actuels.

  • Automates pondérés : équivalences entre automates et logiques, résultats de décidabilité, modèles pour les arbres et pour les mots, automates  probabilistes
  • Transducteurs : modèles unidirectionnels et bidirectionnels, modèle des SST, déterminisation et fonctionnalité
  • Ordre supérieur : langages indexés, langages d’ordre supérieur, automates à piles de piles

Selon les années et les intervenants, la liste des problèmes étudiés et l'importance relative des différentes notions pourra varier.

Prérequis: Un intérêt pour les automates, la logique et l’algorithmique. Toutes les notions utilisées dans le cours seront définies et expliquées.

Sémantique dénotationnelle

Intervenants : Emmanuel Beffara, Myriam Quatrini, Laurent Regnier, Lionel Vaux

Dans une première partie le cours présente la sémantique dénotationnelle à partir de la notion d'espace cohérent, qui est à l'origine de la logique linéaire, dont on étudiera les propriétés. On présentera notamment le calcul des séquents de la logique linéaire, ainsi que la notion de réseau de preuve, qui fournit une approche asynchrone de l'élimination des coupures. On termine le cours par une ouverture à des sujets plus contemporains.

Plan :

  1. Le modèle cohérent du λ-calcul.
  2. Logique linéaire : calcul des séquents et élimination des coupures.
  3. Réseaux de preuve et séquentialisation : le cas multiplicatif.
  4. Exponentielles dans les réseaux.
  5. Prolongements (au choix, en fonction du temps et des intervenants) :
    1. Au-delà du cas purement fonctionnel : opérateurs de contrôle ; concurrence.
    2. Sémantique quantitative et développement de Taylor.
    3. Focalisation et recherche de preuve.
    4. Ludique.

ASP : fondements théoriques, calculs et applications

Intervenants : Eric Würbel, Belaid Benhamou, Vincent Risch

ASP est un paradigme de représentation et de raisonnement sur les connaissances, apparu il y a une vingtaine d'années, et qui connaît actuellement un développement important de par l'existence de solveurs efficaces. Le but de cette option est d'étudier ASP sous ses angles théoriques, calculatoires, et pratiques.

  • fondements théoriques :
    • modèles stables, non-monotonie
    • equilibrium logics, équivalences de programmes
    • sémantiques modales
  • calcul des modèles stables :
    • solveurs de type branch and bound
    • solveurs basés sur la recherche de conflits
  • applications :
    • ASP en pratique
    • méthodologies de développement