Master Mathématiques et applications, Parcours : Informatique et Mathématiques discrètes (IMD)

Tronc commun

• Algorithmique(SINCC3A, 3ECTS)

  Intervenant : Victor Chepoi

  • Mise à niveau:
    1. Algorithmes de graphes: parcours, plus court chemin, arbres couvrants, flots
    2. programmation linéaire: méthode simplex, dualité, modélisation des problèmes NP complèts comme programmes linéaires en nombres entiers;
  • Plutôt P:
    1. Diviser-pour-règner: multiplications des entiers, élément k minimal, transformée rapide de Fourier;
    2. Programmation dynamique: distance d'édition et distance d'édition en espace linéaire, structure secondaire d'un ARN, stable max d'un arbre;
    3. Algorithmes gloutons. Matroïdes et algorithmes gloutons. Axiomatiques des matroïdes par bases, circuits, fonction de rang;
    4. Méthode locale: recuit simulé, configurations stables dans les réseaux de Hopfield, mariage stable, coupe maximum d'un graphe (algo facteur 2);
  • Plutôt NPC:
    1. Algorithmes d'approximation: facteur 2 pour VERTEX COVER facteur 2 et 4/3 pour ordonnancement des tâches, facteur 2 NextFit et 3/2 FirstFitDecreasing pour BinPacking. FPTAS pour le  Sac à Dos. PTAS pour ordonnancement des tâches.
    2. Largeur arborescente d'un graphe. Algorithmes à paramètres exactspour VERTEX COVER dans des graphes de largeur arborescente bornée.
    3. PSPACE: QSAT et Planification ((s,t)-Reachability) sont dans PSPACE (theoreme de  Savitch);
    4. Randomisation (rappels): analyse de la complexité en esperance pour Quicksort, algorithmes d'approximation pour CoupeMax et MaxSAT (par randomisation et programmation linéaire). Dérandomisation pour MaxSAT. Comptage approximatif et  schéma d'approximation randomise FPTRAS pour  les comptage #DNF.
  • Thèmes complémentaires:
    • Algorithmes géométriques: diagrammes de Voronoi par diviser pour règner et par balayage, triangulations de Delaunay méthode incrémentale randomisée;
    • Algorithmes en ligne et compétitivité. Analyse en compétitivité de la k-pagination, le list accessing problem, et les k serveurs sur un arbre;
    • VC-dimension et le théorème des epsilon-réseaux et le PAC learning.

• Complexité (SINCC3B, 3ECTS)

  Intervenants : Nathan Lhote

  • Mise à niveau : calculabilité et décidabilité : machines de Turing, thèse de Church, notion de réduction
  • Les classes P, NP et au delà : P, NP, problèmes fortement NP-complets, hierarchie polynomiale, compelxité en espace, complexité descriptive.
  • Approximation et complexité ; classes d'approximation, résultats de non approximabilité, réductions pour l'approximation et problèmes complets.
  • Complexité paramétrée : FPT et kernelisation.
  • Éventuellement : complexité du comptage.

   

• Automates (SINCC4B, 3ECTS)

  Intervenant : Benjamin Monmege

  • Mise à niveau : Automates finis et langages réguliers
  • Logiques FO et MSO sur les mots finis et infinis
  • Théorème de Büchi : équivalence automates finis et logique MSO
  • Automates de Büchi : propriétés de clôture, de décision, lien avec MSO
  • Automates d’arbres : propriétés de clôture, de décision, logique MSO sur les arbres
  • Logiques temporelles (LTL, CTL), application au model-checking
  • Automates alternants : équivalence avec les automates finis, application à LTL

• Logique (SINCC4A, 3 ECTS)

  Intervenant : Étienne Miquey

  • Mise à niveau :
    • Formules : calcul propositionnel, calcul des prédicats, modèles
    • Preuves : règles et arbres de déduction, résultats de correction, complétude et incomplétude
  • Logiques du second ordre
  • Calcul des séquents
  • Théorème d’élimination des coupures et applications.
  • Lambda-calcul, lambda-calcul typé, correspondance de Curry-Howard
  • Système F

• Modèles de calcul et systèmes dynamiques (SMACK2A, 3ECTS)

  Intervenant : Étienne Moutot, Kévin Perrot

  • Modèles de calcul, systèmes dynamiques (voir le chapitre 1 du cours de l'EJCIM 2017 pour plus de précisions sur la partie automates cellulaires/pavage)
    • Automates cellulaires : équivalence des définitions locale et topologique, réversibilité, théorème du jardin d'Éden et de l'équilibre, décidabilité de ces propriétés en 1D et indécidabilité en 2D.
    • Pavages par tuiles de Wang et sous-shifts (de type fini) : indécidabilité du domino problem, apériodicité, arécursivité.
    • Réseaux d'automates booléens : dynamique et structure, expressivité, théorème des points fixes, influence des modes de mise à jour (déterministes et non déterministes), théorèmes de convergence au regard des cycles d'interactions.

• Fondements mathématiques de la cryptographie (SMACK3A, 2ECTS)

  Intervenants : Jacinto Joaquin Rodrigues

  Le but de ce cours est de fournir les outils mathématiques nécessaires pour comprendre les bases de la cryptographie moderne ainsi que pour étudier et implémenter les cryptosystèmes classiques.

  Contenus :

  • Arithmétique modulaire, symbole de Legendre et Jacobi, tests de primalité (Rabin-Miller, Baillie–PSW), logarithme discret.
  • Cryptographie symétrique et asymétrique. Échange de clés de Diffie-Hellman, cryptosystème ElGamal, RSA.
  • Cryptanalyse : Baby Step Giant Step, algorithme rho Pollard, algorithme de factorisation de Pollard.
  • Sujets avancés : Cryptographie sur les courbes elliptiques, cryptographie sur les réseaux, codes correcteurs d'erreurs.

• Algorithmique distribuée (SINCB5G, 2ECTS)

  Intervenants : Corentin Travers

  • Modèle passage de messages et réseaux de communication sur des graphes
  • Élection dans un anneau : LeLann Chang Roberts et adaptation
  • Élection dans les réseaux généraux
  • Impossibilité de l’élection dans l’anneau anonyme même avec des algorithmes probabiliste
  • Utilisation de la notion de revêtement pour les résultats d’impossibilité d’élection dans les réseaux généraux
  • Delta+1 coloration dans les anneaux

   

Mathématiques discrètes

• Autour des mathématiques de Paul Erdös

  Intervenant : Lionel Nguyen Van Thé

  Paul Erdös a laissé une empreinte unique sur les mathématiques actuelles. Ce cours aura pour but d'en présenter quelques extraits, et de se servir de cette trame pour présenter plusieurs méthodes et résultats désormais classiques en mathématiques discrètes. Les thèmes abordés seront extraits de la liste suivante.

  1. Théorème de Ramsey sur l'apparition des structures régulières dans les hypergraphes, versions classiques finie et infinie. — Démonstration du théorème de Ramsey infini. — Déduction du théorème de Ramsey fini par compacité/Lemme de König. — Démonstration directe du théorème de Ramsey fini et borne supérieure via récurrence double. — Borne inférieure via méthode probabiliste. — Conjectures et résultats récents.
  2. Théorème d’Erdős-Szekeres sur l’apparition de sous-suites monotones de longueur n dans toute suite finie de réels suffisemment longue. — Démonstration par le théorème de Ramsey pour les paires, borne supérieure correspondante. — Borne exacte - Preuves d’Erdös-Szekeres, de Seidenberg, et via le théorème de Dilworth.
  3. Théorème d’Erdős-Szekeres sur l’apparition de polygones en position convexe de taille n dans tout ensemble fini de points du plan suffisemment grand. — Démonstration par le théorème de Ramsey pour les parties à 4 éléments, borne supérieure correspondante. — Démonstration par les sous-suites convexes et concaves. — Conjecture 2^{n−2}+1.
  4. Extensions du théorème de Ramsey — Théorème de Paris-Harrington et indépendance vis-à-vis de l’arithmétique de Peano. — Théorème d’Erdős-Rado. — Cardinalités supérieures et indépendance vis-à-vis de la théorie des ensembles. — Dimension infinie. — Théorie de Ramsey structurale. — Graphes et nombres chromatiques.
  5. Progressions arithmétiques - En route vers la conjecture d’Erdös-Turán. — Théorème de Hales-Jewett. — Théorème de Rado. — Théorème de van der Waerden.
  6. Combinatoire additive — Sous-ensembles A de N tels que A + A est petit - Ensembles de Sidon. — Sous-ensembles A de N tels que A + A est gros - Bases additives.

• Calcul et théorie de l'information quantique

  Intervenants : Giuseppe Di Molfetta, Ravi Kunjwal

  This introductory course will cover the fundamentals of the interdisciplinary field of quantum information science in three parts :

  1. introduction the basic principles of quantum theory in finite dimensions,
  2. introduction to the basics of quantum information theory as a generalization of classical information theory, and
  3. introduction to the basics of quantum computing in the language of quantum circuits.

  This course aims at providing solid foundations for taking up more specialized courses in quantum information science as well as for conducting research projects on related topics. The mathematical prerequisites for this course are linear algebra and probability theory, although all relevant concepts will be introduced as required.

  The course will be taught in English and will largely follow the textbook of Nielsen and Chuang, "Quantum Computation and Quantum Information", Cambridge University Press.

• Dynamique symbolique

  Intervenants : Pierre Arnoux, Pierre Guillon

  • L'objectif du cours est de présenter les bases de la dynamique symbolique, qui consiste à étudier des ensembles de suites (bi)infinies à valeur dans un alphabet fini. Une des motivation est l'étude de systèmes dynamiques discrets via leurs trajectoires dans une partition finie de l'espace. En dimension 1, les notions de substitutions peuvent donner des liens avec des algorithmes de fractions continues. En dimension 2, elle permettent des constructions hiérarchiques suffisamment complexes pour faire appel à des notions de calculabilité.

    Plan du cours:

    1. Dynamique symbolique 1D :
       • Mots finis et infinis, espaces de shift
       • Dynamiques topologique : récurrence, minimalité; codage d'un système dynamique
       • Complexité, entropie, liens avec la périodicité; mots sturmiens
       • Sous-shifts de type fini, systèmes sofiques, liens avec les automates finis
       • Substitutions, systèmes substitutifs et S-adiques; pavages substitutifs en dimension 1
    2. Dynamique symbolique 2D :
       • Pavages apériodiques, substitutifs
       • (in)décidabilité de problèmes algorithmiques
       • Complexité de motifs, conjecture de Nivat

   

• Modèles de calcul naturel

  Intervenants : Giuseppe Di Molfetta, Kévin Perrot, Enrico Porreca, 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.

• Théorie de l'information, algorithmique, cryptographie et codage

  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

• Topologie algèbrique discrète

  Intervenants :  Dimitri Ara, Alexandra Bac, Aldo Gonzales, Emmanuel Godard

  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

  Revêtements et applications
  Retour sur l'homotopie
  Théorème fondamental des revêtements
  Borsuk-Ulam
  Nombre chromatique des graphes de Knesser

Algorithmique et combinatoire

• Algorithmes pour l'optimisation

  Intervenants : Yann Vaxès, Bertrand Estellon, Basile Couëtoux, Guyslain Naves

  L'option s'intéresse aux méthodes d'optimisation combinatoire, qui est la partie de la recherche opérationnelle qui traite des problèmes d'optimisation dans un domaine discret. Il s'agit alors de trouver une solution optimale parmi un nombre fini mais très grand de solutions. Nous étudions à la fois des problèmes bien résolus pour lesquels il existe des algorithmes polynomiaux, une description polyédrale de l'enveloppe convexe des solutions et des théorèmes minmax. Nous abordons aussi plusieurs techniques algorithmiques pour traiter les problèmes d'optimisation combinatoire NP-difficiles - algorithmes d'approximation, approche polyédrale, programmation linéaire et en nombres entiers. Enfin, nous donnons des exemples d'utilisation de ces techniques pour modéliser et résoudre des problèmes d'optimisation rencontrés en pratique.

• Algorithmique d'énumération

  Intervenants : Nadia Creignou, Oscar Defrain, Frédéric Olive, Simon Vilmin

  En algorithmique d'énumération, le but est de lister efficacement toutes les solutions à un problème, typiquement en garantissant un petit délai entre solutions consécutives : réponses à une requête, clusters dans un réseau, modèles d'une formule logique, etc. L'objectif de ce cours est d'introduire les concepts généraux de l'énumération, de présenter quelques techniques algorithmiques importantes, ainsi que leur impact dans des domaines variés de l'informatique comme la logique propositionnelle, la théorie des graphes, des hypergraphes, des bases de données, des treillis ou encore des matroides. 

  Plan du cours :

  1. Concepts généraux de l'énumération : définitions, complexités, réductions.
  2. Techniques algorithmiques : backtrack, saturation, supergraph.
  3. Applications : logique, graphes, hypergraphes, bases de données, treillis et matroides.

  La dernière partie pourra être articulée vers différents domaines selon les années, les intervenants, et les sensibilités des étudiants. Aucun pré-requis n'est nécessaire ; toutes les notions utilisées dans le cours seront définies et expliquées.

• Algorithmique distribuée avancée

  Intervenants : Arnaud Labourel et l'équipe DALGO

  Le but de cet enseignement est de présenter les différents modèles de calcul distribué, ainsi que des résultats de calculabilité et de complexité associés. Un des objectifs sera en autres de montrer comment des entités avec des capacités limitées (en termes de calcul, mémoire, ...) peuvent collaborer afin de réaliser des tâches complexes. L'enseignement fera le tour des tâches distribués les plus courantes - consensus et élection mais aussi calcul d'arbre couvrant, d'ensembles indépendants maximaux, de coloration de graphes, rassemblement d'agents mobiles, formation de motif, ... Un accent sera mis sur les techniques de preuves d'impossibilité et des bornes inférieures de complexité en termes de nombre de rondes, de messages ou de déplacements.

  Exemples de modèles de calcul avancés :

  • mémoire partagée, compare&swap, test&set, transactions
  • réseaux de communication
  • réseaux dynamiques, adversaire de messages
  • agents mobiles
  • matière programmable Exemples de problèmes -
  • Algorithme de 3-coloration en O(log^n) rondes et borne inférieure en Ω(log^ n) à l'aide de la théorie des nombres de Ramsey
  • Impossibilité du consensus à l'aide de preuves s'appuyant sur des notions de topologies

• Ensembles ordonnés en combinatoire, géométrie, logique

  Intervenants : François Brucker, Oscar Defrain, Luigi Santocanale

  Ce cours vous permettra d'apprécier et maitriser la théorie des ensembles ordonnés et d'explorer les nombreuses applications, en combinatoire, géométrie, logique et programmation. Le cours vous présentera d'abord les résultats fondamentaux de la théorie, pour ensuite se concentrer sur des aspects plus pointus choisis en fonction des intérêts des étudiants.

  Plan du cours :

  (A) Fondements

  1. Ensembles ordonnés et treillis : définitions élémentaires
  2. Largeur d'un ensemble ordonné et partitions en chaînes (théorème de Dilworth)
  3. Ensembles ordonnés série parallèle (optionnel)
  4. Familles d'ensembles fermés sous l'intersection (familles de Moore), opérateurs de clôture, connexions de Galois
  5. Treillis distributifs et modulaires. Principe d'inclusion-exclusion, formule d'inversion de Moebius
  6. Caractérisations locales des treillis (semi)distributifs et (semi)modulaires (optionnel)
  7. Treillis distributifs et ensembles ordonnés finis, théorème de dualité de Birkhoff

  (B) Applications

  1. Treillis distributifs sur objets combinatoires- c-orientations des graphes, couplages des graphes bipartis planaires, tensions des graphes, pavages de dominos, treillis de chemins
  2. Matroïdes simples et treillis géométriques. Géométries convexes, antimatroïdes, treillis semidistributifs
  3. Treillis semidistributifs sur objets combinatoires- arbres binaires et permutations
  4. Hiérarchies
  5. Algèbres de Boole, de Heyting, ouverts d'un espace topologique, frames ; théorèmes de dualité
  6. Elements de la théorie des domaines

• Modèles et algorithmes de l'IA : des contraintes à l'incertain

  Intervenant : Christophe Gonzales

  L'objectif de cette option est de présenter des problématiques et modèles d'IA tournant autour des contraintes (CSP, WCSP, SAT, max-SAT) mais également de modèles graphiques comme les réseaux bayésiens, de sensibiliser à certaines propriétés de ces modèles (par exemple les classes polynomiales) et d'étudier les algorithmes exploités en IA pour les résoudre efficacement.

• Théorie métrique des graphes

  Intervenants : Jérémie Chalopin, Victor Chepoi et Yann 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.

  1. Plongements isométriques dans des hypercubes et des produits de graphes
  2. Graphes médians, graphes bridged et la méthode "local vers global"
     - Equivalence entre les graphes médians, les complexes cubiques CAT(0) et les domaines de structures d'événements. - Equivalence entre graphes bridged et complexes simpliciaux systoliques
  3. 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
  4. Plongement l_1 à faible distorsion et théorème de Bourgain. Applications algorithmiques
  5. 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

• ASP : fondements théoriques, calculs et applications

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

  L'ASP est un paradigme de représentation et de raisonnement sur les connaissances, apparu il y a une trentaine d'années suite à l'idée de la programmation logique. Il connaît actuellement un développement important de par son riche pouvoir à la représentation des connaissances et l'existence de solveurs efficaces pour la recherche des solutions. Le but de cette option est d'étudier l'ASP sous ses angles théoriques, calculatoires, et pratiques. Le cours contiendra principalement les notions suivantes :

  1. Fondements théoriques
     • Programmation logique
     • Sémantique des modèles stables, non-monotonie
     • Extension aux classes stables
     • Extension aux extra-modèles stables
  2. Calcul des modèles stables
     • Solveurs de type branch and bound
     • Solveurs basés sur la recherche de conflits
  3. Applications
     • ASP en pratique
     • Méthodologies de développement

• Automates et jeux

  Intervenants : Benjamin Monmege

  1. Automates et jeux (contenu variable - méthodes formelles appliquées à la vérification, à la synthèse et à la sécurité) OU
  2. Automates et vérification ET Jeux et synthèse

• Introduction aux logiques modales et applications

  Intervenants : Nicola Olivetti, Raphaëlle Crubillé

  Le but de ce cours est introduire les logiques modales, un cadre Fondamental de formalismes utilisés pour différents types de Raisonnement, représentation des connaissances et modélisation des Systèmes. Les logiques modales sont introduites par leur axiomatisation et la Sémantique de Kripke. On aborde les questions calculatoires, Décidabilité et complexité de ces logiques et on présente des systèmes De preuve qui fournissent des procédures de décision. On présente une application des logiques modales au raisonnement épistémique. On traite ensuite la notion d'équivalence de modèles et la notion de Bisimulation. Finalement on présente deux extensions de la logiques Modales adaptées pour représenter et vérifier des propriétés des systèmes- la logique dynamique de Hennnessy-Milner et la logique modale avec Operateurs de point fixe.

• Réalisabilité classique

  Intervenants : Étienne Miquey, Laurent Regnier, Lionel Vaux

  On commencera par rappeler les principes de la réalisabilité intuitionniste dans le cadre de l'arithmétique du second ordre, la présentation de la machine de Krivine pour le lambda-calcul avec continuations et son utilisation pour étendre la réalisabilité intuitionniste à la logique classique.

  On passera ensuite aux résultats de base de la théorie : réalisation du schéma de récurrence, terme de stockage, réalisation des formules du premier ordre de l'arithmétique.

  Si le temps le permet on abordera les extensions au cadre de la théorie des ensembles et l'on verra comment la réalisabilité peut être vue comme une extension du forcing permettant de construire des modèles inédits de ZFC.

• Sémantique dénotationnelle et logique catégorique

  Intervenants : Raphaëlle Crubillé, Federico Olimpieri, Tito Nguyễn, Luigi Santocanale

  L'objectif de ce cours est de donner une introduction à la sémantique dénotationnelle, une approche mathématique pour formaliser mathématiquement le comportement des programmes à l'exécution. Le cours intègrera par ailleurs une introduction à la théorie des catégories, et présentera les outils catégoriques nécessaires pour aborder la littérature récente en sémantique dénotationnelle.

  Plan du cours:

  Préambule: sémantique ensembliste du lambda-calcul

  (A) Sémantique catégorique

  1. Introduction aux catégories: catégories cartésiennes. Foncteurs, transformations naturelles, adjonctions.
  2. Catégories cartésiennes fermées: définition, interprétation du lambda-calcul.
  3. Catégories monoïdales: définition, théorème de cohérence, catégories symétriques monoïdales fermées, logique linéaire et ses modèles.

  (B) Sémantique dénotationnelle

  1. Domaines de Scott
  2. Espaces cohérents: fonctions stables, fonctions linéaires, structure de modèle de logique linéaire
  3. Sémantique quantitative: modèle relationnel, modèle relationnel pondéré, interprétation du choix probabiliste.